Instructor: Hemanshu Kaul

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

Time: 1:50pm, Tuesday & Thursday.
Place: 102, Engineering 1 Bldg.

Office Hours: Noon-1pm Tuesday and Thursday, walk-ins, and by appointment. Emailed questions are also encouraged.

• Tuesday, 2/5 : Dates and Syllabi for Exam #1 and Exam #2 have been announced below.


• Tuesday, 1/15 : Check this webpage regularly for homework assignments, announcements, etc.

• Exam # 1 : Thursday, March 7th. Topics: Everything covered in class, textbook, and HWs that corresponds to topics in HW#1 to HW#6.
• Exam # 2 : Tuesday, April 16th. Topics: Everything covered in class, textbook, and HWs that corresponds to topics in HW#7 to HW#10.
• Final Exam : Thursday, May 9th, 2pm-4pm. Topics: All topics studied during the semester.

• Supplementary Exercises. This file containing interesting problems from outside the textbook will be updated throughout the semester. Most of them will assigned in your HWs.
  
  
• Optional Exercises. This file containing challenging problems from outside the textbook will be updated throughout the semester. These problems should be attempted only if you have finished all the homework problems, or if you need a problem more challenging than the HW problems.
  
  
  
Note: The Section and Exercise numbers below refer to the 6th edition of the textbook.
`Supplementary Exercises" refers to the problems in the eponymous document above.


• Homework #1 : Due Thursday, 1/24. Select solutions distributed in class on Thursday, 1/24.
  Suggested Problems: Section 1.1: #1ce, #3, #10. Section 1.2: #3acde, #5. Section 2.2: #3, #5. Supplementary Exercises: #3.
  Written Problems: Section 1.1: #10a, #14. Section 1.2: #5a, #6. Section 2.2: #3c, #4. Supplementary Exercises: #1.
  


• Homework #2 : Due Thursday, 1/31. Select solutions distributed in class on Tuesday, 2/5.
  Suggested Problems: Section 2.3: #2bc, #6c, #9, #14c, #15, #20d, #23. Section 2.4: #2d, #4c, #5a, #10c. Supplementary Exercises: #3, #5, #7.
  Written Problems: Section 2.3: #13, #19b, #20f. Section 2.4: #4b, #6, #11. Supplementary Exercises: Submit two of the following {#4, #6, #8} .
  


• Homework #3 : Due Thursday, 2/7. Select solutions distributed in class on Thursday, 2/14.
  Suggested Problems: Section 2.5: #2b, #3b, #6. Section 3.1: #3c, #4, #6c, #9, #11, #17. Supplementary Exercises: #9, #12.
  Written Problems: Section 2.5: #3c. Section 3.1: #3d, #6b, #16. Supplementary Exercises: #10, #11.
  


• Homework #4 : Due Thursday, 2/14. Select solutions distributed in class on Thursday, 2/14.
  Suggested Problems: Section 3.2: #3, #7, #9a, #12b, #27. Section 3.3: #10, #18a, #21a, #22, #26ab. Supplementary Exercises: #12, #14.
  Written Problems: Section 3.2: #4c, one of {#8, #12c}. Section 3.3: #12, #13, #24, #25. Supplementary Exercises: #15, #16.
  


• Homework #5 : Due Thursday, 2/21. Select solutions distributed in class on Thursday, 2/21.
  Suggested Problems: Section 4.2: #5, #9. Section 4.3: #2abc, #5b, #7, #16, #28.
  Written Problems: Section 4.2: #3, #12a, #13, #15. Section 4.3: #5a, #17b, #19a. Supplementary Exercises: #17a.
  


• Homework #6 : Due Thursday, 2/28. Solutions distributed in class on Thursday, 2/28.
  Suggested Problems: Section 4.4: #2, #4ab, #5, #9, #19, #20b. Section 5.2: #9, #10b, #14, #19, #21.
  Written Problems: Section 4.4: #6, #11, #17. Section 5.2: #5, #13, #15a, #18a. Supplementary Exercises: #18, #19.
  


• Homework #7 : Due Thursday, 3/14. This HW is longer than usual as it is based on 3 lectures, make sure you start on it right after the Exam. Solutions distributed in class on Tuesday, 3/26.
  Suggested Problems: Section 5.3: #5, #7, #13. Section 5.4: #2, #3, #4.
  Written Problems: Section 5.3: #6, #10a, #12, #18. Section 5.4: #5b, #7b, #8. Supplementary Exercises: #13, #20.
  


• Homework #8 : Due Thursday, 3/28. You have two weeks to complete this HW, get started early. Solutions distributed in class on Thursday, 3/28.
  Suggested Problems: Section 6.1: #1, #2, #3, #6, #10ac, #12a. Section 6.2: #4c, #7. Supplementary Exercises: #21, #22.
  Written Problems: Section 6.1: #7b, #16, #20, #22, #23b. Section 6.2: #2, #4b, #5, #6, #8b.
  


• Homework #9 : Due Thursday, 4/4. Solutions distributed in class on Tuesday, 4/9.
  Suggested Problems: Section 7.2: #3, #4d, #7a, #11a, #13. Section 7.3: #3, #5, #8a. Section 7.4: #1, #4, #5. Supplementary Exercises: #23, #24.
  Written Problems: Section 7.2: #4e, #10, #14. Section 7.3: #4, #10. Section 7.4: #10a, #11. Supplementary Exercises: #25.
  


• Homework #10 : Due Thursday, 4/11. Solutions to be distributed in class on Thursday, 4/11.
  Suggested Problems: Section 8.1: #2ab, #6a, #7, #10b. Supplementary Exercises: #26a.
  Written Problems: Section 8.1: #3, #4, #5, #6c, #12b. Supplementary Exercises: #26b.
  


• Homework #11 : Due Thursday, 4/25. Solutions distributed in class on Thursday, 4/25.
  Suggested Problems: Section 8.2: #3, #4b, #9, #12. Section 9.1: #5, #10.
  Written Problems: Section 8.2: #1b, #7, #10. Section 9.1: #2, #6, #9. Supplementary Exercises: #27.
  


• Homework #12 : Due Thursday, 5/2. Strict Deadline due to Final Exam. Select solutions distributed in class on Thursday, 12/2.
  Suggested Problems: Section 9.2: #3, #5, #12, #14a, #17. Section 9.3: #4, #5b, #6, #7, #8, 9, #10a, #11, #12ab. Supplementary Exercises: #28.
  Written Problems: Section 9.2: #4a, #7, #11a, #14b. Section 9.3: #3b, #15.
  

• Note : All Theorems/ Rules/ Properties/ Corollaries stated in the log below are proved in class unless stated otherwise.
  
  
• Tuesday, 1/15 : Well-Ordering Principle and its applications to proofs by contradiction - no integer in (0,1), Archimedean Property, First and Second Principles of Induction and their applications. (From Section 1.1, and elsewhere)
• Thursday, 1/17 : Course requirements and aim: Handouts with Course Information, Advice for doing HW, `What this course is really about'. Applications of WOP and Induction: Factorial, Binomial coefficients, Pascal's Rule, Binomial Theorem, Division Algorithm. (From Sections 1.2 and 2.2)
• Tuesday, 1/22 : Division Algorithm and its applications, Divisibility and its properties, Common divisors and greatest common divisor, 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. (From Sections 2.2 and 2.3)
• Thursday, 1/24 : Euclid's lemma, Alternate definition of gcd, Lemma for Euclidean Algorithm, Euclidean Algorithm, Blankinship's method, Running time of EA, Expressing gcd(a,b) as ax+by, gcd of integers with a common factor, lcm(a,b). (From Sections 2.3 and 2.4, and elsewhere)
• Tuesday, 1/29 : lcm(a,b), Relationship between lcm and gcd, gcd and lcm for more than two integers, Linear diophantine equations - geometric intuition, existence and characterization of solutions, Examples for solving diophantine equation (with additional constraints). (From Sections 2.4, 2.5, and elsewhere)
• Thursday, 1/31 : Prime and composite numbers, existence of prime factors of positive integers, Useful corollaries of Euclid's Lemma for primes, Fundamental Theorem of Arithmetic - existence and uniqueness, Canonical prime factorization of a positive integers, Four proofs of irrationality of sqrt(2). (From Sections 2.5, 3.1, and elsewhere.) HANDOUT for another proof of irrationality of sqrt(2).
• Tuesday, 2/5 : gcd, lcm, and their relationship using Fundamental Theorem of Arithmetic, Algorithms to find primes and prime factorizations - a short discussion, 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).
• Thursday, 2/7 : Arbitrarily long but finite a.p.s of primes, Linear and Non-linear functions for generating primes, There is no a.p. consisting of only primes, 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, some elementary bounds on p_n. (From Sections 3.2, 3.3, and elsewhere). HANDOUT for large counterexamples. Read about Fermat's Last Theorem.
• Tuesday, 2/12 : 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 and their applications, Cancelation laws for congruence relations. (From Sections 3.3, 4.2). HANDOUT for Section 4.2.
• Thursday, 2/14 : Cancelation laws for congruence relations, Basis representation theorem (existence and uniqueness), Binary exponential algorithm, Congruent values of a polynomial with integral coefficients and their applications to divisibility tests for 9 and 11. (From Sections 4.2, and 4.3). HANDOUT for Section 4.3.
• Tuesday, 2/19 : Divisibility test 11, Linear congruence and its relation to linear diophantine equation, Existence and the number 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. (From Sections 4.3 and 4.4). HANDOUT for Section 4.4.
• Thursday, 2/21 : Chinese remainder theorem and the formula for unique solution for system of linear congruences, Solutions for linear congruences in two variables, Proof for Simultaneous solution for two linear congruences in two variables, Fermat's little theorem and its two different proofs. (From Section 5.2 and elsewhere). HANDOUT for Section 5.2.
• Tuesday, 2/26 : Lemma and example to show the converse does not hold, Pseudoprimes and their infinitude, Pseudoprimes to the base a, Carmichael numbers, Constructing pseudoprimes, Various possible converses to Fermat's little theorem and why they are not true, Correct Converse to Fermat's theorem (proof in HW#6), Carmichael number's are square-free, A sufficient condition for Carmichael numbers, (story of 1729). (From Section 5.2 and elsewhere).
• Thursday, 2/28 : Wilson's theorem, Application of Fermat's and Wilson's Theorems to solving certain quadratic congruences, Fermat's method for factorization. (From Sections 5.3 and 5.4). HANDOUT for Section 5.3
• Tuesday, 3/5 : Fermat's method for factorization, Generalized Fermat's method for factorization, Fermat-Kraitchik Method for factorization. Number-Theoretic Functions, tau(n), sigma(n). (From Sections 5.4 and 6.1). 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/7 : Exam #1.
• Tuesday, 3/12 : 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), Description of the divisors of mn using products of divisors of m and n. (From Section 6.1). HANDOUT for Section 6.1.
• Thursday, 3/14 : Inverting the formula for f from F using Mobius inversion formula, Mobius function and its multiplicativity. (From Section 6.2). HANDOUT for Section 6.2.
  Discussion of Exam #1 solutions and performance. Advice on better study habits and improved preparation for the exams.
• Tuesday, 3/26 : Proof of MIF, Converse of the construction of multiplicative function F (f is multiplicative iff F is multiplicative), Example of a conjecture thats false in general but true up to n=10 billion, Euler's phi function - for primes, powers of primes, multiplicativity, formula in terms of prime factorization. (From Sections 6.2 and 7.2). HANDOUT for Section 7.2.
• Thursday, 3/28 : Counting argument in the proof of multiplicativity of phi, even value of phi and application to proof of infinitude of primes, Gauss' formula for n in terms of phi function, phi function as a summation, Euler's generalization of Fermat's little theorem, Apllying Euler's Theorem to find for every odd number n coprime to 5 a number k divisible by n with all digits of k equal to 1. (From Sections 7.2, 7.3 and 7.4, and elsewhere). HANDOUT for Sections 7.3 and 7.4.
• Tuesday, 4/2 : Euler's theorem - proof using Fermat's theorem, Applying Euler's theorem to - short proof of CRT, find digits of a high power, and to find for every odd number n coprime to 5 a number k divisible by n with all digits of k equal to 1; Direct proof of Euler's theorem as a generalization of the proof of Fermat's theorem. Order of a modulo n - basic properties, when does order of a modulo n exist and when does it not exist. (From Section 7.3, 8.1, and elsewhere). No HANDOUT for today's lecture. See previous handout for Section 7.3.
• Thursday, 4/4 : order of a modulo n - divisibility condition on the exponents, i congruent to j modulo order of a iff a^i congruent to a^j modulo n, order of power of a in terms of order of a, Primitive root of n. (From Sections 8.1 and 8.2). HANDOUT for Sections 8.1 and 8.2.
• Tuesday, 4/9 : 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, Exact number of solutions for functional congruence with f(x) = x^d - 1, An alternate proof of Wilson's theorem. (From Section 8.2). HANDOUT for Section 8.2 (part 2).
• Thursday, 4/11 : the number of incongruent integers of order d modulo p, number of primitive roots of p, Discussion of: 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. (From Sections 8.2, 8.3, 9.1). No HANDOUT for today's lecture. Examples done in class are enough..
• Tuesday, 4/16 : Mid-term Exam #2.
• Thursday, 4/18 : 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 with proof, Applying Euler's criterion, Legendre symbol and its relation to Euler criterion, its multiplicativity and other elementary properties, simple formula for number of solutions of a standard quadratic congruence, formula for (-1/p), a simpler proof for infinitude of primes of the form 4k+1, (a/p) sum up to 0 that leads to - number of quadratic residues equals the number of a quadratic non-residues, description of quadratic residues as even powers a primitive root of p, a primitive root can not be a quadratic residue. (From Sections 9.1, 9.2, and elsewhere). HANDOUT for Sections 9.1, 9.2 and 9.3.
• Tuesday, 4/23 : (a/p) sum up to 0 that leads to - number of quadratic residues equals the number of a quadratic non-residues, description of quadratic residues as even powers a primitive root of p, a primitive root can not be a quadratic residue, Statement of QRL, applying QRL to calculate (a/p), the general method for finding (a/p) using prime factorization of a, Gauss Lemma (another way of calculating (a/p)), applying Gauss lemma, formula for (2/p) using GL. (From Section 9.3). No HANDOUT for today's lecture. See previous Handout.
• Thursday, 4/25 : Proof of Quadratic Reciprocity Law. Discussion of Exam #2 solutions and scores. (From Section 9.3 and elsewhere). HANDOUT for Section 9.3 (II).
  Check out the many proofs of Quadratic Reciprocity Law.
• Tuesday, 4/30 : Discussion of Exam#2 solutions (conclusion). Cryptosystems and public-key cryptosystems, RSA cryptosystem - setup and the underlying mathematics, 3 main attacks on the RSA cryptosystem. (From Sections 10.1, 10.3, and elsewhere). Survey of Attacks on RSA Cryptosystem.
• Thursday, 5/2 : 3 main attacks on the RSA cryptosystem, Discrete log problem, ElGamal Cryptosystem - setup, encryption and decryption, and the underlying math, Digital signatures and a modification of the ElGamal cryptosystem. (From Sections 10.1, 10.3, and elsewhere). Survey of Attacks on RSA Cryptosystem. Rough CLASS NOTES on Cryptography.