Chapter 2: Congruences

Chapter 2 is all about modular (or congruence) arithmetic and how it can help us understand numbers and their properties. Here's the stuff we covered in class

- Lecture 5: Primes in Arithmetic Progression; Modular Congruence
- We wrapped up our discussion on the Fundamental Theorem of Arithmetic, eventually hitting Dirichlet's Theorem on primes in an arithmetic progression. Afterwards we introduced the notion of modular congruence, the basic notion which drives modular arithmetic.
- Lecture 6: Modular Arithmetic and Linear Congruences
- We discussed how congruences behave with respect to addition and multiplication. We'll then studied linear congruences in 1 variable, determining a criterion when these kinds of equations have a solution.
- Lecture 7: Solving Congruence Equations, Con't.
- We continued talking about linear congruence equations, in particular seeing how to solve these equations in the case that solutions do exist. We did even better than this, though, since we found all distinct solutions (modulo m) to the equation. We also talked about a special case of these equations: when the constant term
*b*is 1. This led us to*multiplicative inverses modulo m*. We finished by discussing the problem of simultaneous linear congruences; i.e., the problem of trying to find a common solution to a handful of different linear congruences. - Lecture 8: Chinese Remainder Theorem and Wilson's Theorem
- We discussed the Chinese Remainder Theorem and Wilson's Theorem. The former is a technique for finding simultaneous solutions to multiple congruence equations, whereas the latter is a congruence equation which characterizes primes.
- Lecture 9: Fermat's Little Theorem
- Today we started by introducing a few methods for solving simultaneous congruences suggested by students in the class. We then finished our proof of Wilson's Theorem before moving on to introduce and prove the "other" theorem of Fermat: Fermat's Little Theorem (aka,
*flt*). We saw several applications and corollaries of this result which made some modular computations really quite simple. - Lecture 10: Fake Primes and Euler's Theorem
- Today we finished up our discussion of Fermat's Little Theorem. This led us to a test for primality, and it also gave us an indication of what it might mean for a composite number to be a "false prime." By the end of the class we stated and proved a generalization of Fermat's Little Theorem which works for all integers, not just primes. This also gave us an excuse to define Euler's $\phi$-function.

page revision: 10, last edited: 19 Sep 2008 19:58