| Day | Topics | Preparation | |
|---|---|---|---|
| Wed. 9/4 | Introduction, countability, sums and products of sequences |
Sec. 1.1 | |
| Mon. 9/9 | Induction, Fibonacci numbers. | Sec. 1.1-3 | |
| Wed. 9/11 | Divisiblity, greatest integer function,
base r representation of an integer |
Sec. 1.4, Sec. 2.1 | |
| Mon. 9/16 | Base r conversions and arithmetic, computational complexity | Secs. 2.1-3 | |
| Wed. 9/18 | Prime numbers | Sec. 3.1 | |
| Mon. 9/23 | Comments on HW. Two's complement, etc.
Greatest common divisor. |
Sec. 3.2 | |
| Wed. 9/25 | Euclidean algorithm | Sec. 3.3 | |
| Mon. 9/30 | Gcd of several ints. Least common multiple. Unique factorization |
Sec. 3.4 | |
| Wed. 10/2 | EXAM | Secs. 1.1-4; 2.1-2; 3.1-4; | |
| Mon. 10/7 | Unique factorization, application to primes in arithmetic prgression |
Sec. 3.4 | |
| Wed. 10/9 | Linear Diophantine equations | Sec. 3.6 | |
| Mon. 10/14 | Nonlinear Diophantine equations:
Pythagorean triples, Fermat's last theorem |
Sec. 13.1-2 | |
| Wed. 10/16 | Modular arithmetic | Sec. 4.1 | |
| Mon. 10/21 | Units and zero-divisors in Z/m | Sec. 4.1 | |
| Wed. 10/23 | Solution of congruences, linear and quadratic | Sec. 4.2, Sec. 11.1, pp. 376-7 | |
| Mon. 10/28 | Applications: divisiblity tests, tournaments. The Chinese Remainder Theorem. |
Secs. 5.1, 5.3 | |
| Wed. 10/30 | Chinese remainder theorem and extensions Check digits |
Sec. 4.3 | |
| Mon. 11/4 | Check digits. Systems of linear congruences |
Secs. 5.5, 4.5 | |
| Wed. 11/6 | Linear cryptosystems.
Fermat's little theorem. |
Sec. 6.1 Sec. 8.1-2 | |
| Mon. 11/11 | Euler's theorem
Exponentiation cryptosystems |
Sec. 6.3 Sec. 8.3 | |
| Wed. 11/13 | Questions? RSA Cipher. Primality testing. |
8.4 | |
| Mon. 11/18 | EXAM | Secs. 3.4,6; 4.1-3; 4.5; 5.1; 5.5; 6.1; 6.3. | |
| Wed. 11/20 | Multiplicative functions:
Euler phi function, number of divisors, sum of divisors |
Sec 7.1,2 | |
| Mon. 11/25 | Quadratic extensions of Z,
a non-unique factorization domain, Z[sqrt(-5)] |
p. 98; 3.4 problems 19-24 | |
| Mon. 12/2 | Order in Z/m , primitive elements
polynomials over Z/m |
Sec. 9.1 | |
| Wed. 12/4 | Polynomials over Z/p , Primitive elements in
Z/p , index arithmetic |
Secs. 9.2, 9.4 | |
| Mon. 12/9 | El Gamal cryptosystem, course evaluation. | Sec. 10.2 | |
| Wed. 12/11 | Review, the abc conjecture | . |