Instructor: Hemanshu Kaul

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

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

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

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


• Thursday, 8/26 : HW#1 has been uploaded below.
  Please make a note of the 'Important Policy' stated in the Homework section below.


• Tuesday, 8/24 : Check this webpage regularly for homework assignments, announcements, etc.

• Exam # 1 : Thursday, October 14th. Topics: Everything covered in class up to and including the lecture on Thursday, September 30th. This corresponds to material covered in HW#1 to HW#6.
• Exam # 2 : Tuesday, November 23rd. Topics: Everything covered in class from Tuesday, October 5th to Thursday, November 11th (including both days). This corresponds to material covered in HW#7 to HW#11.
• Final Exam : Thursday, Dec 9th, 10:30am-12:30pm. Topics: All topics studied during the semester, except cryptosystems in the last class.

• Supplementary Exercises. This file containing interesting problems from outside the textbook will be updated throughout the semester.
  
  
• 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.
  
  
  
• Homework #1 : Due Thursday, 9/2. Select solutions distributed in class on Thursday, 9/2.
  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, 9/9. Select solutions distributed in class on Tuesday, 9/14.
  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, 9/16. Select solutions distributed in class on Tuesday, 9/21.
  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, 9/23. Select solutions distributed in class on Thursday, 9/23.
  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, 9/30. Select solutions distributed in class on Thursday, 9/30.
  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, 10/7. Because of the Exam on 10/14, this will be a strict deadline. Solutions distributed in class on Thursday, 10/7.
  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 Friday, 10/22 in my mailbox by 4pm. 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 Thursday, 10/28.
  Suggested Problems: Section 5.3: #5, #7, #10a, #13. Section 5.4: #2, #3, #4. Section 6.1: #1, #2, #3, #6, #10ac, #12a. Supplementary Exercises: #21, #22.
  Written Problems: Section 5.3: #6, #12, #18. Section 5.4: #5b, #7b, #8. Section 6.1: #7b, #16, #20, #22, #23b. Supplementary Exercises: #13, #20.
  


• Homework #8 : Due Thursday, 10/28. Solutions distributed in class on Thursday, 10/28.
  Suggested Problems: Section 6.2: #4c, #7. Supplementary Exercises: #22.
  Written Problems: Section 6.2: #2, #4b, #5, #6, #8b.
  


• Homework #9 : Due Thursday, 11/4. Solutions distributed in class on Thursday, 11/4.
  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, 11/11. Solutions distributed in class on Thursday, 11/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, 11/18. Strict Deadline due to Exam#2 on Tuesday, 11/23. Solutions distributed in class on Thursday, 11/18.
  Suggested Problems: Section 8.2: #3, #4b, #9, #12.
  Written Problems: Section 8.2: #1b, #7, #10. Supplementary Exercises: #27.
  


• Homework #12 : Due Thursday, 12/2. Strict Deadline due to Final Exam. Select solutions to be distributed in class on Thursday, 12/2.
  Suggested Problems: Section 9.1: #5, #10. 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.1: #2, #6, #9. 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, 8/24 : Course requirements and aim: Handouts with Course Information, Advice for doing HW, `What this course is really about'. 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, 8/26 : Applications of WOP and Induction: Factorial, Binomial coefficients, Pascal's Rule, Binomial Theorem, Division Algorithm. (From Sections 1.2 and 2.2)
• Tuesday, 8/31 : 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, 9/2 : 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. (From Sections 2.3 and 2.4, and elsewhere)
• Tuesday, 9/7 : gcd of integers with a common factor, 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. (From Sections 2.4, 2.5, and elsewhere)
• Thursday, 9/9 : Examples for solving diophantine equation (with additional constraints), 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, 9/14 : 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, 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, some elementary bounds on p_n. (From Sections 3.2, 3.3, and elsewhere). Read about Fermat's Last Theorem.
. (From Sections 3.2, 3.3, and elsewhere).
• Thursday, 9/16 : 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, Non-linear functions for generating primes. (From Sections 3.2, 3.3, and elsewhere). HANDOUT for large counterexamples.
• Tuesday, 9/21 : Congruence relation, Characterization of congruence relation in terms of equal remainders, Basic properties of congruence relation and their applications, Cancelation laws for congruence relations, Basis representation theorem (existence and uniqueness). (From Sections 4.2 and 4.3). HANDOUT for Section 4.2.
• Thursday, 9/23 : Basis representation theorem (uniqueness), Binary exponential algorithm, Congruent values of a polynomial with integral coefficients and their applications to divisibility tests for 9 and 11, Check digits, Linear congruence and its relation to linear diophantine equation, Existence and the number of solutions of a linear congruence. (From Sections 4.2, 4.3, and 4.4). HANDOUT for Section 4.3.
• Tuesday, 9/28 : 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, Chinese remainder theorem, Solutions for linear congruences in two variables, Simultaneous solution for two linear congruences in two variables. (From Sections 4.3 and 4.4). HANDOUT for Section 4.4.
• Thursday, 9/30 : Proof for Simultaneous solution for two linear congruences in two variables, Fermat's little theorem and its proofs, 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, Carmichael number's are square-free, A sufficient condition for Carmichael numbers. (From Section 5.2 and elsewhere). HANDOUT for Section 5.2.
• Tuesday, 10/5 : Carmichael number's are square-free, A sufficient condition for Carmichael numbers, Wilson's theorem, Application of Fermat's and Wilson's Theorems to solving certain quadratic congruences. (From Sections 5.2 and 5.3). HANDOUT for Section 5.3.
• Thursday, 10/7 : Application of Fermat's and Wilson's Theorems to solving certain quadratic congruences, Fermat's method for factorization, Generalized Fermat's method for factorization, Fermat-Kraitchik Method for factorization. (From Section 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).
• Tuesday, 10/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, 10/14 : Exam #1.
• Tuesday, 10/19 : Discussion of Exam #1 - score distribution and solutions. 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, Inverting the formula for f from F using Mobius inversion formula, Mobius function and its multiplicativity. (From Sections 6.1 and 6.2). HANDOUT for Section 6.2.
• Thursday, 10/21 : Discussion of Exam #1 solutions. Advice on better study habits and improved preparation for the exams.
• Tuesday, 10/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, 10/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. (From Sections 7.2, 7.3 and 7.4, and elsewhere). HANDOUT for Sections 7.3 and 7.4.
• Tuesday, 11/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; motivation for a direct proof of Euler's theorem as a generalization of the proof of Fermat's theorem. (From Section 7.3 and elsewhere). No HANDOUT for today's lecture. See previous handout for Section 7.3.
• Thursday, 11/4 : 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, 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. (From Sections 7.3, 8.1 and 8.2). HANDOUT for Sections 8.1 and 8.2.
• Tuesday, 11/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, 11/11 : An alternate proof of Wilson's theorem, the number of incongruent integers of order d modulo p, number of primitive roots of p. (From Section 8.2). No HANDOUT for today's lecture. See previous handouts for Section 8.2.
• Tuesday, 11/16 : 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, 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. (From Sections 8.2, 8.3, 9.1). No HANDOUT for today's lecture. Examples done in class are enough..
• Thursday, 11/18 : 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, Statement of QRL, applying QRL to calculate (a/p). (From Sections 9.1, 9.2, 9.3, and elsewhere). HANDOUT for Sections 9.1, 9.2 and 9.3.
• Tuesday, 11/23 : Mid-term Exam #2.
• Tuesday, 11/30 : Review of "when does a quadratic congruence have a solution?"; Examples for applying QRL, 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. Discussion of Exam #2 solutions and scores. (From Section 9.3). HANDOUT for Section 9.3 (II). Check out the many proofs of Quadratic Reciprocity Law.
• Thursday, 12/2 : Discussion of Exam#2 solutions. Cryptosystems and public-key cryptosystems, RSA cryptosystem - setup and the underlying mathematics, [Read in lecture notes: 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, with an example]. (From Sections 10.1, 10.3, and elsewhere). Survey of Attacks on RSA Cryptosystem. Rough CLASS NOTES on Cryptography.