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 6 - Modular Arithmetic
- Today in class we introduced the notion of modular congruence and saw that it can be used to give an equivalence relation to the integers. Not only does this provide us with a way to split the integers up into distinct subgroups (a so-called "partition"), but it also behaves well with respect to addition and multiplication. We started to explore how we can use these arithmetic properties of congruences to prove results about integers.
- Lecture 7 - Linear Congruence Equations
- Today we started by reviewing how one can go about "canceling" common factors in congruence equations. Afterwards we introduced the notion of a linear congruence equation, giving a theorem which told us exactly when such an equation has solutions (and, indeed, how many solutions exist).
- Lecture 8 - Multiplicative Inverses; the Chinese Remainder Theorem
- We started off today by talking about a special class of linear congruence equations, namely those of the form $ax \equiv 1 \mod{m}$. These led to multiplicative inverses, which we saw were useful in solving certain congruence equations. We drove this point home when we used multiplicative inverses to prove the Chinese Remainder Theorem, a tool that is used to solve simultaneous linear congruence equations.
- Lecture 9 - Sweet Congruences for Prime Numbers
- We started today by saying a few more words about techniques for solving CRT problems aside from the method developed in class last time. We then shifted gears; instead of trying to solve congruence equations, we instead asked if there were any interesting congruence properties of numbers. This led us to Wilson's Theorem as well as Fermat's little Theorem (flt).
- Lecture 10 - Consequences of flt
- We started today by finishing off the proof of Fermat's Little Theorem, then proceeded to use this theorem to give various properties which make life modulo p nice. In particular, we saw a test which can be used to prove a number is composite without actually factoring the number! We also saw that there are certain composite numbers which behave much like prime numbers do.
- Lecture 11 - Euler's Theorem
- We started today by looking for a generalization to Fermat's Little Theorem, and in doing so we conjectured what is known as Euler's Theorem. This theorem relates the number of residue classes that are relatively prime to n to a "magic exponent result" that has the flavor of Fermat's Little Theorem. After introducing the theory and giving a proof, we went on to compute values of Euler's $\phi$ function.