← MATH 01352 · Theory of Numbers
MATH 01352 · Congruences
Modular arithmetic
Definition
a ≡ b (mod n) means n|(a−b). Congruences respect addition and multiplication. ℤₙ is the ring of residue classes mod n.
Read this
Reduce often to stay in {0,1,…,n−1}. Negative residues OK if consistent.
You can cancel a factor c in a congruence only when gcd(c,n)=1 (or cancel the gcd carefully).
Powers mod n use repeated squaring; Euler/Fermat speed this up.
Drill with flashcards
Flip through these until you can say the answer before revealing it.
Flashcards · 1 / 3
Click the card to flip
Try this
Attempt each problem first, then open the worked solution.
1.Compute 7⁸ mod 10 using patterns or successive squaring.