Instructor: Hemanshu Kaul

Office: 234B, Engineering 1
Phone: (312) 567-3128
E-mail: kaul [at] math.iit.edu

Time: 3:15pm, Tuesday & Thursday.
Place: 103, Engineering 1 Bldg.

Office Hours: 2pm-4pm, Wednesday, walk-ins, and by appointment.
Problem sessions on Mondays at 5:40pm.

• Friday, 5/4 : Class notes for Cryptography have been uploaded below.


• Tuesday, 4/24 : Check out these short descriptions of many public-key cryptosystems.
• Thursday, 4/19 : Check out the many proofs of Quadratic Reciprocity Law.


• Thursday, 4/12 : Exam #2 has been scheduled for Thursday, April 26th (see below). Note that the last homework for the topics in the Exam will be due on the Thursday (4/19) before the Exam. I will put up the solutions online the same day so that you have enough time to practice for the exam. I will be available on Monday (4/23) and Wednesday (4/25) for consultation, make appointments if possible.
• Tuesday, 4/10 : A letter to the students.


• Tuesday, 3/20 : Problem Sessions have been scheduled for Mondays at 5:40pm. This week, since Monday is already past, we will meet tomorrow at 4:30pm.


• Thursday, 2/22 : Exam #1 has been scheduled (see below). Note that the last homework for the topics in the Exam will be due on the Thursday (3/1) before the Exam. I will put up the solutions online the same day so that you have enough time to practice for the exam. I will also be available all day on Monday (3/5) for consultation.
• Wednesday, 2/21 : Handouts with examples and comments for past several sections have been uploaded below. Also, new Select Solutions continue to be uploaded. Be sure to use all of these as study-aids.
• Wednesday, 2/7 : Select Solutions for the first two HWs are up. Please read the note at the beginning of Select Solutions #1.
• Wednesday, 1/31 : You can substitute one problem from "optional exercises" for two of the homework problems. In particular, you can substitute Optional Exercise #3 for any two problems in Homework #2. Follow the explicit instructions for optional exercises given with each HW.
• Tuesday, 1/30 : All students, especially those considering graduate studies, should try to solve the "Optional Exercises" in the assignments. As usual, ask me for hints if you get stuck.
  Also, its important to solve all the assigned exercises, not just those included for submission in the homework.
• Thursday, 1/17 : There will be no class on Tuesday, 1/23 due to conference travel. This class will be made up via exam scheduling.
• General: Check this webpage regularly for homework assignments, announcements, etc.

• Exam # 1 : Tuesday, March 6th during class. Topics: All sections up to and including Section 5.3.
• Exam # 2 : Thursday, April 26th. Topics: All topics covered from February 27th till April 17th (including both these lectures)- namely, topics from sections 5.4, 6.1, 6.2, 7.2, 7.3, 8.1, 8.2, 8.3, 9.1, 9.2, 9.3.
• Final Exam : Tuesday, May 8th, 8:00am-10am. Topics: Everything done during the semester up to 4/26.

• Tuesday, 1/16 : Assignment 1
• Thursday, 1/18 : Assignment 2
• Homework #1 : Section 1.1: 1c, 10, 14; Section 1.2: 3d; Section 2.2: 3c; Supplementary Exercises: 1, 4, 5. Due Tuesday, 1/30. Select Solutions #1.
• Thursday, 1/18 : Assignment 3
• Homework #2 : Section 2.3: 2bc, 13, 15, 19bd, 20df, 23; Supplementary Exercises: 6. Due Thursday, 2/1. Select Solutions #2.
• Tuesday, 1/30 : Assignment 4
• Thursday, 2/1 : Assignment 5
• Homework #3 : Section 2.4: 4b, 5a, 6, 11; Section 2.5: 3c; Section 3.1: 3d, 6b, 16; Supplementary Exercises: 8, 10, 11. You can submit Optional Exercises# 4 and/ or 5 as a replacement for two homework exercises each from the book only. Due Thursday, 2/8. Select Solutions #3.
• Tuesday, 2/6 : Assignment 6
• Thursday, 2/8 : Assignment 7
• Homework #4 : Section 3.2: 4ac, 8, 12bc; Section 3.3: 12, 18a, 24, 25; Supplementary Exercises: 13, 15, 16. You can submit Optional Exercises# 6 and/ or 7 as a replacement for two homework exercises (each part counts separately) each from the book only. Due Thursday, 2/15. Select Solutions #4.
• Tuesday, 2/13 : Assignment 8
• Thursday, 2/15 : Assignment 9. Also, be sure to read Example 4.8 on page 77 to see how properties of congruences can simplify finding the solutions of a linear congruence.
• Homework #5 : Section 4.2: 12a, 13, 15; Section 4.3: 5a, 19, 28; Section 4.4: 6, 9, 11; Supplementary Exercises: 17a, 18. Due Thursday, 2/22. Select Solutions #5.
• Tuesday, 2/20 : Assignment 10
• Thursday, 2/22 : Assignment 11
• Homework #6 : Section 4.4: 17; Section 5.2: 5, 13, 15a, 18a; Section 5.3: 6, 10a, 12, 18; Supplementary Exercises: 19 (INSTEAD of 21), 20. You can submit Optional Exercise #8 as a replacement for two homework exercises (each part counts separately) from the book only. Due Thursday, 3/1. Because of the Exam on 3/6, this will be a strict deadline. Select Solutions #6.
• Tuesday, 2/27 : Assignment 12
• Thursday, 3/1 : Assignment 13
• Thursday, 3/8 : Assignment 14
• Homework #7 : Section 5.4: 5b, 7b, 8; Section 6.1: 7b, 16, 20, 22. 23b; Section 6.2: 2, 4b, 5, 6, 8b; Supplementary Exercises: 22. Due Thursday, 3/22. (delayed due to Exam and Spring Break; longer than usual as it covers three lectures and has an extra week for completion). Select Solutions #7.
• Tuesday, 3/20 : Assignment 15
• Thursday, 3/22 : Assignment 16
• Homework #8 : Section 7.2: 4e, 7a, 10, 14; Section 7.3: 4, 10; Section 7.4: 10a, 11; Supplementary Exercises: 26, 27. Due Thursday, 3/29. Select Solutions #8.
• Thursday, 3/29 : Assignment 17
• Homework #9 : Section 8.1: 3, 4, 5, 6c, 12b; Section 8.2: 1b, 4a; Supplementary Exercises: 28b, 29. Due Thursday, 4/5. Select Solutions #9.
• Thursday, 4/5 : Assignment 18: Section 8.2: 6, 7, 9, 10, 12; Section 8.3: 2ab, 8, 10 [note that 8 and 10 give a simple alternate proof for non-existence of primitive roots]; Section 9.1: 1, 2, 5, 6, 7, 9, 10, 12.
• Homework #10 : Section 8.2: 7, 9, 10, 12; Section 8.3: 2b, 8ac, 10; Section 9.1: 2, 6, 9, 10. Due Thursday, 4/12. Select Solutions #10.
• Thursday, 4/12 : Assignment 19
• Homework #11 : Section 9.2: 4a, 7, 11a, 14b; Section 9.3: 2, 3b, 7, 8, 15; Supplementary Exercises: 30. Due Thursday, 4/19. Because of the Exam on 4/26, this will be a strict deadline. Select Solutions #11.

• Tuesday, 1/16 : Well-Ordering Principle and its applications to proofs by contradiction, Archimedean Property, First and Second Principles of Induction and their applications, Factorial. (From Section 1.1 and elsewhere)
• Thursday, 1/18 : Binomial coefficients, Pascal's Rule, Binomial Theorem, Division Algorithm and its applications, Divisibility and its properties, Common divisors and greatest common divisor. (From Sections 1.2, 2.2, and 2.3)
• Thursday, 1/25 : gcd(a,b) as a linear combination of a and b and its corollaries, Relatively prime integers - characterization in terms of linear combination of 1 and its corollary, Euclid's lemma, Alternate definition of gcd, Lemma for Euclidean Algorithm. (From Sections 2.3 and 2.4)
• Tuesday, 1/30 : Euclidean Algorithm, Blankinship's method, gcd of integers with a common factor, lcm(a,b), Relationship between lcm and gcd, Linear diophantine equations - geometric intuition, existence and characterization of solutions. (From Sections 2.4, 2.5, and elsewhere)
• Thursday, 2/1 : Finished the proof for diophantine equations, examples for diophantine equation, Prime and composite numbers, prime factors of positive integers, Useful corollaries of Euclid's Lemma, Fundamental Theorem of Arithmetic - existence and uniqueness, Canonical prime factorization of a positive integers, Four proofs of irrationality of sqrt(2), Algorithms to find primes and prime factorizations - a short discussion. (From Sections 2.5, 3.1, and elsewhere). HANDOUT for another proof of irrationality of sqrt(2).
• Tuesday, 2/6 : gcd, lcm, and their relationship using Fundamental Theorem of Arithmetic, Sieve of Erastothenes and the corresponding lemma, Infinitude of primes and Euclid's proof method, Arbitrarily long gaps between primes, Two approaches to studying prime numbers, Discussion of Arithmetic Progressions and Primes: Infinitude of primes of form 4n+3 (application of Euclid's proof method), Dirichlet's Theorem (no proof), No infinite a.p. consists solely of primes, arbitrarily long but finite a.p.s of primes. (From Sections 3.2, 3.3, and elsewhere). HANDOUT for large counterexamples.
• Thursday, 2/8 : Non-linear functions for generating primes, No non-constant polynomial with integral coefficients takes only prime values, The prime number theorem and its corollaries, Riemann Hypothesis as relating \pi(x) and Li(x), Bounds on P_n in terms of earlier primes and in terms of just n, Bertrand's Conjecture and its application to bounding P_n, Twin prime conjecture and Goldbach's conjecture, Congruence relation, Characterization of congruence relation in terms of equal remainders, Basic properties of congruence relation. (From Sections 3.2, 3.3, 4.2, and elsewhere). HANDOUT for Section 4.2.
• Tuesday, 2/13 : Basic properties of congruence relation and their applications, Cancelation law for congruence relations, Basis representation theorem (proof of uniqueness), Binary exponential algorithm, Congruent values of a polynomial with integral coefficients and their applications to divisibility tests. (From Sections 4.2, and 4.3). HANDOUT for Section 4.3.
• Thursday, 2/15 : Check digits, Linear congruence and its relation to linear diophantine equation, Existence and the count of solutions of a linear congruence, Multiplicative inverse and how to find it using EA or Blankinship's method, System of simultaneous linear congruences and how to transform it into the standard form, Chinese remainder theorem. (From Sections 4.3, and 4.4). HANDOUT for Section 4.4.
• Tuesday, 2/20 : Solutions for linear congruences in two variables, Simultaneous solution for two linear congruences in two variables, Fermat's little theorem and its two proofs, Lemma and example to show the converse does not hold, Pseudoprimes and their infinitude, Pseudoprimes to the base a, Carmichael numbers. (From Sections 4.4 and 5.2). HANDOUT for Section 5.2.
• Thursday, 2/22 : Constructing pseudoprimes, Converse to Fermat's theorem, Carmichael number's are square-free, A sufficient condition for Carmichael numbers, Wilson's theorem. (From Sections 5.2 and 5.3). HANDOUT for Section 5.3.
• Tuesday, 2/27 : Application of Fermat's and Wilson's Theorems to solving certain quadratic congruences (and its application to "infinitude of primes of form 4k+1"), Fermat's method for factorization, Generalized Fermat's method for factorization. (From Sections 5.3 and 5.4). No HANDOUT for Section 5.4: Just understanding the examples done in class will be enough for the HW problems. (Examples 5.2, 5.3, and 5.4).
• Thursday, 3/1 : Fermat-Kraitchik Method, Number-theoretic functions, tau(n), sigma(n), Positive divisors of an integer in terms of its prime factorization, Formulas for tau(n) and sigma(n) using the prime factorization of n, Formula for product of divisors of n, Multiplicative functions, tau and sigma are multiplicative, General construction for multiplicative function (F) using another multiplicative function (f). (From Sections 5.4 and 6.1). HANDOUT for Section 6.1.
• Tuesday, 3/6 : Mid-term Exam #1.
• Thursday, 3/8 : Description of the divisors of mn using products of divisors of m and n, Proof for the general construction for multiplicative function (F) using another multiplicative function(f), Inverting the formula for f from F using Mobius inversion formula, Mobius functions and its multiplicativity, Proof of MIF, Converse of the construction of multiplicative function F (f is multiplicative iff F is multiplicative), A conjecture with humongous counterexample. (From Sections 6.1 and 6.2). HANDOUT for Section 6.2.
• Tuesday, 3/20 : Euler's phi function - for primes, powers of primes, multiplicative (and the counting argument in the proof), formula in terms of prime factorization, even value and application to proof of infinitude of primes. (From Section 7.2). HANDOUT for Section 7.2.
• Thursday, 3/22 : Gauss' formula for n in terms of phi function, phi function as a summation, Euler's generalization of Fermat's little theorem - proof using Fermat's theorem, application to CRT, etc. (From Sections 7.3 and 7.4, and elsewhere). HANDOUT for Sections 7.3 and 7.4.
• Tuesday, 3/27 : Applying Euler's theorem to find digits of a high power, direct proof od Euler's theorem as a generalization of the proof of Fermat's theorem, order of a modulo n - basic properties, divisibility condition on the exponents, when does i congruent to j imply a^i congruent to a^j. (From Sections 7.3 and 8.1, and elsewhere). No HANDOUT for today's lecture. See previous handout for Section 7.3 and the next handout for Section 8.1.
• Thursday, 3/29 : i congruent to j modulo order of a iff a^i congruent to a^j modulo n, order of a power of a, primitive root of n, Characterization of positive integers coprime to n in terms of the powers of a primitive root of n, the number of primitive roots of n, how to find all primitive roots of n given one primitive root, Lagrange's theorem for the number of solutions of a polynomial congruence. (From Sections 8.1 and 8.2). HANDOUT for Sections 8.1 and 8.2.
• Tuesday, 4/3 : Exact number of solutions for functional congruence with f(x) = x^d - 1 and its application to proving Wilson's theorem, the number of incongruent integers of order d modulo p, how to find all integers of order d modulo p given one primitive root of p or one integer of order d, number of primitive roots of p. (From Section 8.2). HANDOUT for Section 8.2.
• Thursday, 4/5 : Smallest primitive root of a prime and related conjectures, Powers of 2 greater than 4 have no primitive roots, Complete characterization of n that have primitive roots (without proof), quadratic congruences, reduction of a general quadratic congruence to the simplest form and the relation between their solutions, x^2 congruent to a modulo p has either no solutions or exactly two solutions (their relation), Definition and characterization of quadratic residues and nonresidues using Euler criterion, Legendre symbol and its relation to Euler criterion. (From Sections 8.2, 8.3, 9.1, and 9.2). No HANDOUT for today's lecture. Examples done in class are enough. .
• Tuesday, 4/10 : Applying Euler's criterion, Legendre symbol and its multiplicativity and other elementary properties, simple formula for number of solutions of a simplified quadratic congruence, formula for (-1/p), a new proof for Theorem 5.5, New proof for infinitude of primes of the form 4k+1, (a/p) sum up to 1 that leads to a description of quadratic residues as even powers a primitive root of p, Computational evidence for Quadratic Reciprocity law (QRL). (From Sections 9.1, 9.2, and elsewhere). No HANDOUT for today's lecture. Examples done in class are enough. Look at the next lecture's handout..
• Thursday, 4/12 : Statement of QRL, applying QRL, Gauss Lemma (another way of calculating (a/p)) and the idea underlying its proof and proof of QRL, applying Gauss lemma, formula for (2/p) using GL, Short proof using GL for 'infinitude of primes of the form 8k-1', Sophie Germain primes and the formula for their primitive root. (From Sections 9.2, 9.3, and elsewhere). HANDOUT for Sections 9.1, 9.2 and 9.3.
• Tuesday, 4/17 : Sophie Germain primes and the formula for their primitive root (remember to finish the proof of case 2), General statement of QRL and its proof - extension of the argument of Gauss' Lemma, and the geometric argument connecting sum of quotients to lattice points. (From Sections 9.2 and 9.3, and elsewhere). HANDOUT for Section 9.3 (II).
• Thursday, 4/19 : Solving quadratic congruences modulo product of distinct primes, modulo powers of a n odd prime, modulo powers of 2, modulo a composite number, Cryptosystems and public-key cryptosystems, RSA cryptosystem - setup and the underlying mathematics. (From Sections 9.4, 10.1, and elsewhere). CLASS NOTES on Cryptography.
• Tuesday, 4/24 : Example for RSA, Discrete log problem, ElGamal Cryptosystem - setup, encryption and decryption, and underlying math, Digital signatures and a modification of the ElGamal cryptosystem, with an example. (From Sections 10.3, and elsewhere). CLASS NOTES on Cryptography.
• Thursday, 4/26 : Exam #2 .
• Tuesday, 5/1 : Continued Fractions and Wiener's attack on RSA cryptosystem. Survey of Attacks on RSA Cryptosystem, Introduction to Continued Fractions.
• Thursday, 5/3 : Discussion of Exam #2 problems and Final exam syllabus.

• Different Areas of Number Theory
• Wikipedia : Number Theory
• Mathworld : Number Theory Dictionary
• Planet Math : Number Theory
• Math Atlas : Number Theory
• Ask Dr. Math
• Primes Page