# Math 410     Topics in Number Theory     Fall 2013

## Instructor: Sunil Chebolu

• Office: Stevenson 337
• Email: szchebol@ilstu.eduz (with the two "z"'s removed)
• Office Hours: By appointment
• Class meeting time:
• STV 132 6:00 - 8:50 PM
• Text: Factorization and Primality Testing, by David M. Bressoud (Springer, UTM)

Announcements:

• (July 20) More than 99.9 % of the people in the world never get this privilege of taking a graduate course in Number Theory. You are so unique! Congratulations!

Project Ideas: I will collect here some ideas for in-class projects, some of these were also mentioned in class. These will be assigned to students on a first-come-first-serve basis.

• Carmichael Numbers
• Yao's Millionaire Problem
• Fast Multiplication Using the Chinese Remainder Theorem (See Page 412 of Hungerfords' Abstract Algebra: An Introduction.)
• Euler's refutation of Fermat's claim: "2^32+1 is a prime" (An excellent reference for this beautiful analysis of Euler is Dunham's Journey Through Genius.)
• Lucas-Lehmer primaility test; see wiki link posted above.
• Musical actions of Dihedral groups (reserved for Sara, if she is interested)
• Try to factor some big number using the quadratic sieve. To this end, you will have to implement the Quadratic Sieve algorithm using some software; maple, sage etc.
• Tonneli-Shanks Algorithm (This needs Quadratic Reciprocity Law)
• The unbelievable Polynomial
• Factoring numbers using Continued fractions (Chapters 10-12) (Two students can share this lengthy topic.)
• Symmetry in Music (reserved for Christina, if she is interested)

Presentations: You have 30 minutes to do your presentation on the topic assigned to you. It may not be possible to give all the details in 30 minutes. So please make sure you convey the big picture and key ideas. Your presentation should be clear, coherent, and well organized.

• December 5, 2013 and finals week.
• 6:00 - 6:30 : Christina Henry Symmetry in Music
• 6:30 - 7:00 : Sara Leigh: Musical Actions of Dihedral groups
• 7:00 - 7:30 : Wasem Yaji: Bhaskara-Brouncker Algorithm (see Chapter 10)
• 7:30 - 7:45 : BREAK
• 7:45 - 8:15 : Jeff Hempstead: Tonelli-Shanks Algorithm (see wiki link above)
• 8:15 - 8:45 : Maria Veja: Solvay-Strassen Primality test. (see wiki link above)
• 8:45 - 9:15 : David Mendell: Lucas-Lehmer Primality test. (see wiki link above)

• October 17, 2013
• 6:00 - 6:30 : Christina Henry and David Mendell: Yao's Millionaire Problem.
• 6:30 - 7:00 : Jeff Hempstead: Applications of the Chinese Remainder Theorem
• 7:00 - 7:30 : Maria Veja: 2^32+1 is not a prime
• 7:30 - 8:00 : Wasem Yaji: Charmichael numbers.
• 8:00 - 8:30 : Hasan Cheema: Strong Psuedoprimes.
• 8:30 - 9:00 : Sara Leigh: The Music of Primes

## Homework

• due Dec 5
• due Nov. 21
• weekend movie: The Proof
• Read Chapter 14 (Skip Sections 14.4 and 14.5)
• Solve the following problems: 13.20, 13.22, 13.23, 13.24. (Turn in 13.23 and 13.24 for grading)
• 6 is a congruent number. Use this fact and other results stated in lecture to find 10 rational points on the Elliptic curve y^2= x^3- 36 x.

• due Nov. 14
• weekend movie: An evening with Leonhard Euler
• Read Chapter 13 (Note: we are skipping Chapters 10, 11, and 12 on Continued Fractions)
• Solve the following problems: 9.1, 9.2, 9.3, 9.8, 9.10, 9.11, 9.12, 9.16 (Most of these are quick if you invoke the appropriate theorems.) Turn in problems 9.10 and 9.12 for grading. (For problem 9.10, I want you to use the new Primality test discussed in Section 9.4)

• due Nov. 7
• weekend movie: The music of Primes
• Solve the 3rd congruence in problem 8.15 (Turn this one for grading).

• due Oct 31
• Bedtime reading: Pomerance's article on "The tale of two sives"
• Read Chapter 8 thoroughly. You can skip section 8.3
• Do problems 8.6, 8.13, 8.14, 8.15 (Just solve the 3rd congruence), 8.16 (This one I did in class; see reciprocity lecture notes)

• due Oct 24
• Take-home exam is due on Oct 24th.
• Turn in the following problems: (These are from last week.)
1. Do the two exercises given in class on the Jacobi symbol
2. Solve the inverse reciprocity problem for a = 7. That is, find all primes p for which 7 is a perfect square mod p.
• MOST IMPORTANT ASSIGNEMENT: Read, Read, Read, Read Chapter 8. This chapter will give us the first efficient algorithm for factoring large composite numbers.

• due Oct 17
• Complete the homework problems from last week if you haven't done them already.
• Master Cipolla's algorithm for finding square roots mod p. (Read your notes and also the handout given in class).
• Turn in the following problems:
1. Do the two exercises given in class on the Jacobi symbol
2. Solve the inverse reciprocity problem for a = 7. That is, find all primes p for which 7 is a perfect square mod p.
• Work on the take-home midterm due on Oct 17th.
• Prepare for your project presentations on Oct 17th.

• due Oct 10
• Read Chapter 7 again. (Skip the book's proof of Quadratic Reciprocity if you followed the proof I gave in class.)
• Read Eistein's proof of Quadratic Reciprocity. (see handout given to you for this)
• Do problems 7.1, 7.4, 7.7, 7.8, 7.16, 7.17.
• Work on the take-home midterm due on Oct 17th
• Prepare for your project presentations on Oct 17th. (Please let me know if you need more than 30 minutes.)

• due Oct 3
• Read Chapter 7 (This has the Quadratic Reciprocity Law which is probably the most important theorem in number theory. Gauss called it The Golden Theorem.)
• Do problems 6.2, 6.3, 6.6, 6.8, 6.10, 6.13, 6.21
• Prepare for your project presentations on Oct 10th.

• due Sep 26
• Do problems 5.1, 5.3, 5.6, 5.7, 5.10, 5.12, 5.13, 5.19, 5.20
• Factor the number 21 using the 3 factorisation algorithms of Chapter 5.
• Read the handout on detecting perfect squares. I urgue you to execute that algorithm on a small number.

• due Sep 19
• Do problems 4.3, 4.4, 4.14, 4.18, 4.20
• Turn in problems: 4.2, 4.9, 4.11 (consider only the first 3 equations), 4.17, proof of the High school lemma mentioned in class. (Feel free to use mathematical software for calculations.)

• due Sep 12
• Read the PDF slides of "Number Theory resolves a problem in a divorce" posted above. (THIS IS VERY VERY IMPORTANT!)
• Do problems 4.3, 4.4, 4.14, 4.18, 4.20, 4.17
• Turn in problems: 3.3, 3.8, 4.1, 4.2, 4.9, 4.11 (I want crystal clear and well organized solutions. You are allowed to use a scientific calculator if necessary.)

• due Sep 5
• Read Chapter 3 and do the following problems
• 3.1, 3.2, 3.3, 3.8, 3.18
• Programming exercises (do them in your favourite language) 3.4, 3.11, 3.12, 3.14, 3.16

• due Aug 29
• Read the first two chapters and do the following problems:
• 1.2, 1.3, 1.4, 1.9 (compute the gcd also using the binary gcd method), 1.14
• 2.1, 2.3, 2.16
• Give proofs of all the 4 lemmas stated in class.
• Prove that N < log_2(ab), where N is the number of steps in computing the gcd of a and b.

• due Aug 22
• Read the first 5 chapters of David Burton's number theory book. FREE PDF COPY OF THIS BOOK