**Instructor:** Hemanshu Kaul

**Office:** 234B, Engineering 1

**Phone:** (312) 567-3128

**E-mail:** kaul [at]
math.iit.edu

**Time:** 3:15pm, Tuesday & Thursday.

**Place:** 106, Engineering 1 Bldg.

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

|Course Information| |Advice| |Announcements| |Examinations| |Homework| |Class Log & Handouts| |Links|

The

The official course syllabi: MATH 410.

Excellent advice by Doug West on how to write homework solutions in a course like this, and on how to write homework solutions for proof-based problems.

Why do we have to learn proofs?

Understanding Mathematics - a study guide

On a more abstract note, here is a discussion of Language and Grammar of Mathematics - which is what you are starting to learn in a course like this.

Excellent advice for math majors, especially those planning to go on to graduate school, by Terry Tao, 2006 Fields medallist. Required reading.

*Thursday, 4/23*: Homework #11 has been uploaded. Its longer than usual but you have 12 days to finish it.*Thursday, 4/9*: Exam #2 has been announced.*Tuesday, 2/24*: Exam #1 has been announced.*Thursday, 2/12*: I have corrected Supplementary Exercise #11, a part of HW#3. The solution to this corrected problem will be due on Thursday, 2/19.*Thursday, 2/5*: I have begun uploading handouts related to the material covered in class on the class log section below. In the later sections I will also upload examples not done in class/ textbook.*Thursday, 1/29*: Please make a note of the 'Important Policy' stated in the Homework section below.*Thursday, 1/22*: Check this webpage regularly for homework assignments, announcements, etc.

*Exam # 1*: Thursday, March 12th. Topics: Everything covered in class up to and including the lecture on Thursday, 2/26. This corresponds to material covered in HW#1 to HW#6.*Exam # 2*: Thursday, April 23rd. Topics: Everything covered in class from Tuesday, 3/3 to Thursday, 4/9 (including both days). This corresponds to material covered in HW#7 to HW#10.*Final Exam*: Thursday, May 14th, 2pm-4pm. Topics: All topics studied during the semester.

You only have to submit solutions to

However, solving a majority of the

Important Policy: For solving HW problems, you can only use the methods/ Theorems studied in class till the day of the HW assignment. If you use some other fact/ or another exercise, you have to prove that first.

**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..Due Thursday, 1/29. Select solutions distributed in class on Tuesday, 2/3.__Homework #1__:

Suggested Problems: Section 1.1: #1ce, #3, #10. Section 1.2: #3acde. Section 2.2: #3abc, #5. Section 2.3: #2bc, #6c, #9, #14c, #15, #20d, #23. Supplementary Exercises: #3, #5.

Written Problems: Section 1.1: #14. Section 1.2: #6. Section 2.2: #4. Section 2.3: #13, #19b, #20f. Supplementary Exercises: Submit two of the following {#1, #4, #6}.

Due Thursday, 2/5. Select solutions distributed in class on Tuesday, 2/10.__Homework #2__:

Suggested Problems: Section 2.4: #2d, #4c, #5a, #10c. Section 2.5: #2b, #3b, #6. Supplementary Exercises: #7, #9.

Written Problems: Section 2.4: #4b, #6, #11. Section 2.5: #3c. Supplementary Exercises:#8, #10.

Due Thursday, 2/12. Select solutions distributed in class on Thursday, 2/19.__Homework #3__:

Suggested Problems: Section 3.1: #3c, #4, #6c, #9, #11, #17. Section 3.2: #7, #9a, #12b. Section 3.3: #18a, #21a, #22. Supplementary Exercises: #12, #14.

Written Problems: Section 3.1: #3d, #6b. Section 3.2: #4c, #8, #12c. Section 3.3: #13, #24. Supplementary Exercises: #11, #15.

Due Thursday, 2/19. Select solutions distributed in class on Thursday, 2/19.__Homework #4__:

Suggested Problems: Section 3.3: #3, #27. Section 4.2: #3, #5, #9.

Written Problems: Section 3.3: #12, #25, #26a. Section 4.2: #12a, #13, #15. Supplementary Exercises: #16.

Due Thursday, 2/26. Select solutions distributed in class on Thursday, 3/5.__Homework #5__:

Suggested Problems: Section 4.3: #2abc, #5b, #7, #16. Section 4.4: #2, #4ab, #5, #9, #19, #20b.

Written Problems: Section 4.3: #5a, #17b, #19a. Section 4.4: #6, #11, #17. Supplementary Exercises: #17a, #18.

Due Thursday, 3/5. Because of the Exam on 3/12, this will be a strict deadline. Select solutions distributed in class on Thursday, 3/5.__Homework #6__:

Suggested Problems: Section 5.2: #9, #10b, #14, #19, #21. Section 5.3: #5, #7, #13.

Written Problems: Section 5.2: #5, #13, #15a, #18a. Section 5.3: #6, #10a, #12, #18. Supplementary Exercises: #13, #19.

Due Thursday, 3/26. This HW is longer than usual as it is based on 3 lectures, make sure you start on it right after the Exam. Select solutions distributed in class on Tuesday, 3/31.__Homework #7__:

Suggested Problems: Section 5.4: #2, #3, #4. Section 6.1: #1, #2, #3, #6, #10ac, #12a. Section 6.2: #4c, #7. Supplementary Exercises: #23.

Written Problems: 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, 4/2 in class at 3:15pm Select solutions distributed in class on Tuesday, 4/7.__Homework #8__:

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.

Written Problems: Section 7.2: #4e, #10, #14. Section 7.3: #4, #10. Section 7.4: #10a, #11. Supplementary Exercises: #24, #25.

Due Thursday, 4/9 in class at 3:15pm Select solutions distributed in class on Thursday, 4/16.__Homework #9__:

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.

Due Thursday, 4/16 in class at 3:15pm Select solutions distributed in class on Thursday, 4/16.__Homework #10__:

Suggested Problems: Section 8.2: #3, #4b, #9. Section 8.3: #8ab. Section 9.1: #5.

Written Problems: Section 8.2: #1b, #7, #10, #12. Section 8.3: #2b, #8c (you can use #8ab), #10. Section 9.1: #2, #6. Supplementary Exercises: #27.

Due Tuesday, 5/5 in class at 3:15pm. This HW is longer than usual as it is based on 3 lectures, make sure you start on it right after the Exam. Select solutions distributed in class on Tuesday, 5/5.__Homework #11__:

Suggested Problems: Section 9.1: #5, #10. Section 9.2: #3, #5, #12, #14a, #17. Section 9.3: #4, #5b, #6, #9, #10a, #11, #12ab, [optional: #16, #17, #18, #19].

Written Problems: Section 9.1: #9. Section 9.2: #4a, #7, #11a, #14b. Section 9.3: #2, #3b, #7, #8, #15. Supplementary Exercises: #28.

*Note*: All Theorems/ Rules/ Properties/ Corollaries stated in the log below are proved in class unless stated otherwise.

*Tuesday, 1/20*: 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, Factorial, Binomial coefficients, Pascal's Rule, Binomial Theorem. (From Sections 1.1, 1.2, and elsewhere)*Thursday, 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, Euclid's lemma. (From Sections 2.2 and 2.3)*Tuesday, 1/27*: Alternate definition of gcd, Lemma for Euclidean Algorithm, Euclidean Algorithm, Blankinship's method, Expressing gcd(a,b) as ax+by, gcd of integers with a common factor, lcm(a,b), Relationship between lcm and gcd. (From Sections 2.3 and 2.4, and elsewhere)*Thursday, 1/29*: 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), Prime and composite numbers, existence of prime factors of positive integers. (From Sections 2.4, 2.5, and 3.1)*Tuesday, 2/3*: 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), 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. (From Sections 2.5, 3.1, 3.2, and elsewhere). HANDOUT for another proof of irrationality of sqrt(2).*Thursday, 2/5*: gcd, lcm, and their relationship using Fundamental Theorem of Arithmetic, 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, 2/10*: 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, some elementary bounds on p_n. (From Sections 3.2, 3.3, and elsewhere). Read about Fermat's Last Theorem.*Thursday, 2/12*: 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.*Tuesday, 2/17*: Binary exponential algorithm, Congruent values of a polynomial with integral coefficients and their applications to divisibility tests, 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 and 4.3). HANDOUT for Section 4.3.*Thursday, 2/19*: 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.*Tuesday, 2/24*: 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, 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.*Thursday, 2/26*: Wilson's theorem, 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. (From Sections 5.3 and 5.4). HANDOUT for Section 5.3.*Tuesday, 3/3*: 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/5*: 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.*Tuesday, 3/10*: 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). (From Section 6.2). HANDOUT for Section 6.2.*Thursday, 3/12*: Exam #1.*Tuesday, 3/24*: Discussion of Exam#1 - solutions and score distribution. Euler's phi function - for primes, powers of primes, multiplicative, formula in terms of prime factorization. (From Section 7.2). HANDOUT for Section 7.2.*Thursday, 3/26*: 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 - proof using Fermat's theorem. (From Sections 7.3 and 7.4, and elsewhere). HANDOUT for Sections 7.3 and 7.4.*Tuesday, 3/31*: 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 od 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 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, 4/2*: 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 a power of a in terms of order of a, primitive root of n, Characterization of positive integers coprime to n in terms of the powers of a primitive root of n. (From Sections 8.1 and 8.2). HANDOUT for Sections 8.1 and 8.2.*Tuesday, 4/7*: 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, the number of incongruent integers of order d modulo p, number of primitive roots of p. (From Section 8.2). HANDOUT for Section 8.2.*Thursday, 4/9*: 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. (From Sections 8.2, 8.3, 9.1). No HANDOUT for today's lecture. Examples done in class are enough..*Tuesday, 4/14*: Proof of Euler's criterion, 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.*Thursday, 4/16*: Computational evidence for Quadratic Reciprocity law (QRL), Statement of QRL, applying QRL to calculate (a/p), 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. (From Sections 9.2, 9.3, and elsewhere). No HANDOUT for today's lecture, see last lecture's Handout.*Tuesday, 4/21*: Short proof using GL for 'infinitude of primes of the form 8k-1', Sophie Germain primes and the formula for their primitive root, General statement of QRL and its simplified 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). Check out the many proofs of Quadratic Reciprocity Law.*Thursday, 4/23*: Exam #2*Tuesday, 4/28*: Expressing (a/p) as sum of quotients of multiples of a modulo p, Example for applying QRL, the general method for finding (a/p) using prime factorization of a, formula for (3/p), When is 'a' a quadratic residue modulo a product of distinct non-primes - method and use of CRT. Discussion of Exam #2 solutions and scores. (From Section 9.3).*Thursday, 4/30*: Discussion of Exam #2 solutions (continued and finished). Solving quadratic congruences modulo powers of an odd prime, modulo powers of 2, modulo a composite number. (From Section 9.4)*Tuesday, 5/5*: Cryptosystems and public-key cryptosystems, RSA cryptosystem - setup and the underlying mathematics, 3 main attacks on the RSA cryptosystem. (From Section 10.1, and elsewhere). Survey of Attacks on RSA Cryptosystem.*Thursday, 5/7*: 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.3, and elsewhere). Rough CLASS NOTES on Cryptography.