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.
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.
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
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)
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.)
Do the two exercises given in class on the Jacobi symbol
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:
Do the two exercises given in class on the Jacobi symbol
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.
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
Read Chapter 5
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 Chapter 4
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