Schedule and Assignments

Day | Topics | Preparation | |
---|---|---|---|

Wed. 9/5 | Introduction | . | |

Fri. 9/7 | Fibonacci numbers, divisibility | Sec. 1.1-3 | |

Mon. 9/10 | Divisiblity, greatest integer function | Sec. 1.4 | |

Wed. 9/12 | Base representations and arithmetic r |
Secs. 2.1-2 | |

Fri. 9/14 | Base arithmetic, big O r |
Secs. 2.2,3 | |

Mon. 9/17 | Prime numbers | Sec. 3.1 | |

Wed. 9/19 | Conjectures on primes, greatest common divisor | Sec. 3.1,2 | |

Fri. 9/21 | Euclidean algorithm | Sec 3.3 | |

Mon. 9/24 | Matrix version of Euclidean algorithm, least common multiple | 3.3 | |

Wed. 9/26 | Least common multiple, preparation for unique factorization | Sec. 3.4 | |

Fri. 9/28 | Unique factorization, application to primes in arithmetic prgression |
Sec. 3.4 | |

Mon. 10/1 | Linear Diophantine equations | Sec. 3.6 | |

Wed. 10/3 | Linear Diophantine equations in several variables | Sec. 3.6 | |

Fri. 10/5 | Nonlinear Diophantine equations: Pythagorean triples | Sec. 13.1 | |

Mon. 10/8 | Nonlinear Diophantine equations: Fermat's last theorem | Sec. 13.2 | |

Wed. 10/10 | Gaussian integers | p. 98; 3.4 problems 19-24 | |

Fri. 10/12 | Quadratic extensions of Z |
p. 98; v3.4 problems 19-24 | |

Mon. 10/15 | EXAM | Secs. 1.1-4; 2.1-2; 3.1-4; 3.6; 13.1, 13.2. | |

Wed. 10/17 | A Non-unique factorization domain Z[sqrt(-5)]Modular arithmetic |
Sec. 4.1 | |

Fri. 10/19 | Units and zero-divisors in Z/m |
Sec. 4.1 | |

Mon. 10/22 | Solution of equations | Secs. 4.2, 11.1, pp. 376-7 | |

Wed. 10/24 | Quadratic equations, divisiblity tests | Secs. 11.1, 5.1 | |

Fri. 10/26 | More on divisibility. tournament scheduling | Sec. 5.3 | |

Mon. 10/29 | Chinese remainder theorem and extensions | Sec. 4.3 | |

Wed. 10/31 | Hash functions, check digits | Secs. 5.4-5 | |

Fri. 11/2 | Exercises | Secs. 4.1-3 | |

Mon. 11/5 | Systems of linear congruences | Sec. 4.5 | |

Wed. 11/7 | Fermat's little theorem | Sec. 6.1 | |

Fri. 11/9 | Euler's theorem | Sec. 6.3 | |

Mon. 11/12 | Linear cryptosystems | Sec. 8.1-2 | |

Wed. 11/14 | Exponentiation cryptosystems | Sec. 8.3 | |

Fri. 11/16 | The RSA cipher | Sec. 8.4 | |

Mon. 11/19 | EXAM | . | |

Wed. 11/21 | RSA cipher | Sec. 8.4 | |

Mon. 11/26 | The Euler phi function | Sec. 7.1 | |

Wed. 11/28 | Multiplicative functions, number of divisors, sum of divisors |
Sec 7.2 | |

Fri. 11/30 | Order in Z/m primitive elements |
Sec. 9.1 | |

Mon. 12/3 | Polynomials over Z/p |
Secs. 9.2 | |

Wed. 12/5 | Polynomials over Z/p |
Secs. 9.2 | |

Fri. 12/7 | Primitive elements in Z/p index Arithmetic |
Sec. 9.4 | |

Mon. 12/10 | El Gamal cryptosystem | Sec. 10.2 | |

Wed. 12/12 | Review, course evaluation. | . | |

Fri. 12/14 | Finite fields, the conjecture abc |
. |

Assigned exercises in Rosen, *Elementary Number Theory
and Its Applications* 4th ed.

Here are some computer assignments, most taken from Rosen's book, that you can do for extra credit.

postscript file

pdf file

Due dates may change depending on schedule.

Due Date | Section | Problems |
---|---|---|

Wed. 9/12 | 1.1 | 8 (find an explicit formula), 24, 28, 32 |

. | 1.2 | 4, 8, 14 |

Wed. 9/19 | 1.3 | 8, 24, 25, 26, 30 |

. | 1.4 | 16, 22, 30 (reduce to 0 < x < 1), 40, 46 |

Wed. 9/26 | 1.4 | 48, 50, 53 |

. | 2.1 | 6, 14, 20, 24, 26 |

. | 2.2 | 8, 10, 14 |

Wed. 10/3 | 3.1 | 10, 16, 24 |

. | 3.2 | 14, 16, 22 |

. | 3.3 | 8b, 14 |

Wed. 10/10 | 3.3 | 10, 20 |

. | 3.4 | 4d, 12, 16, 36 |

. | 3.6 | 8,16 |

Mon. 10/22 | 3.4 | 24, 45, 60 |

. | 13.1 | 2, 12 |

Mon. 10/29 | 4.1 | 18, 24, 28, 34 |

. | 4.2 | 6, 14, 16 |

. | 11.1 | 6 (partially), 12 |

. | 5.1 | 10, 20, 22 |

Wed. 11/7 | 4.3 | 9, 12, 16a |

. | 5.3 | 2 |

. | 5.5 | 8, 10, 20 |

. | 13.1 | 3 |

Wed. 11/14 | 4.5 | 3, 8c, 10a |

. | 6.1 | 20, 22, 24 ( is odd), 28, 40p |

. | 6.3 | 1d, 2, 4, 10, 11c |

Wed. 11/28 | 8.1 | 6 |

. | 8.2 | 8 (write it as a matrix), 20 |

. | 8.3 | 4, 6 |

. | 8.4 | 2, 6 (use 11 not 7 and find ) d |

Wed. 12/5 | 7.1 | 6, 8, 28, 30 |

. | 7.2 | 8, 10 |

. | 9.1 | 8, 10, 14, 16 |

Wed. 12/12 | 9.2 | 2, 6, 8, 10 |

. | 9.3 | 2, 4, 8 |

. | 10.2 | 4, 6 |

I recommend that you at least read the following problems and solve as many as you can. These recommended problems form the material that you are expected to understand upon completion of this course. You can safely ignore the problems that are not listed here. The midterms and the final exam will be based on the material in these problems, but will not necessarily be identical to them.

Section | Recommended Problems |
---|---|

1.1 | 2-9, 13-15, 23-27,29 |

1.2 | 2-9, 11-14, 25-29 |

1.3 | 1-22, 30, 31, 35 |

1.4 | All |

2.1 | 1-7, 14-17 |

2.2 | 1-11, 13-15, |

3.1 | 1-16, 20, 24, 25 |

3.2 | 1-25 |

3.3 | 1-10, 14, 15, 20 |

3.4 | 1-24, 30-41, 44, 45, 52-54, 60 |

3.6 | 1-9, 11-16 |

13.1 | 1-6, 7(read only), 12 |

13.2 | 1, 2, 4, 5, 9, 10 |

4.1 | 1-19, 24-28, 33-35 |

4.2 | 1-13, 15, 16, 18 |

4.3 | 1-13, 15-19 |

4.5 | 1-10 |

5.1 | 1-10 |

5.3 | 1-3 |

5.4 | 1-2 |

5.5 | 1-20 |

6.1 | 1-25, 28-31, 33, 39, 40 |

6.3 | 1-11, 15-17 |

7.1 | 1-8, 11-13 |

7.2 | 1-12 |

9.1 | 1-16 |

9.2 | 1-10, 12 |

9.4 | 1-9 |

10.2 | 1-6 |

8.1 | 1-6 |

8.2 | 5-8, 18-20 |

8.3 | 1-6 |

8.4 | 1-2, 5-8 |

11.1 | 1, 2, 6, 12, 13 |

13.1 | 2-4 |