1. Linear Congruences and Inverses
A linear congruence has the form
An integer with is an inverse of modulo .
Theorem 1 — existence of inverses
If and , an inverse of modulo exists and is unique modulo (one inverse in ; all others are congruent to it).
Proof: Bézout gives . Since , — so is an inverse.
How to find
- Use the Euclidean algorithm to confirm .
- Reverse the steps to write (Bézout coefficients).
- Reduce mod : is the inverse.
Example: inverse of 101 modulo 4620.
Euclid:
Back-substitute:
⇒ .
Solving
Multiply both sides by : .
Example: .
- is an inverse of 3 mod 7 ().
- .
- Check: ✓.
- Solutions: , i.e.
2. The Chinese Remainder Theorem (CRT)
Sun-Tsu’s puzzle: a number leaves remainder 2 mod 3, 3 mod 5, 2 mod 7. What is it?
Theorem 2 — CRT
If are pairwise relatively prime, the system
has a unique solution modulo (one with ; all others are congruent to it).
Construction (the proof is the recipe)
- , and (product of all the other moduli).
- , so find inverse of mod .
Why it works: mod , every term with vanishes (), and , so .
Example (Sun-Tsu): .
| (inverse of mod ) | ||||
|---|---|---|---|---|
| 1 | 3 | 2 | 35 | 2 () |
| 2 | 5 | 3 | 21 | 1 () |
| 3 | 7 | 2 | 15 | 1 () |
.
Back substitution (often faster by hand)
Example: .
- . Plug into 2nd: .
- . Plug into 3rd: .
- ⇒ .
3. Computer Arithmetic with Large Integers
By the CRT, with pairwise coprime moduli and , every is uniquely represented by
Example (mod 3 and 4, integers < 12):
0=(0,0) 1=(1,1) 2=(2,2) 3=(0,3) 4=(1,0) 5=(2,1) 6=(0,2) 7=(1,3) 8=(2,0) 9=(0,1) 10=(1,2) 11=(2,3)
Method
- Choose moduli , pairwise coprime, with product larger than any result.
- Do , componentwise, reducing each component mod its .
- Recover the answer by solving the CRT system.
Benefits: works with numbers bigger than the machine word, and components can be computed in parallel.
Example: moduli 99, 98, 97, 95 (product 89,403,930).
- ,
- Sum:
- Recover via CRT: ; inverses ;
✓
Good moduli: numbers of the form — binary arithmetic is easy, and makes coprime sets easy to find.
e.g. are pairwise coprime; product .
4. Fermat’s Little Theorem
Theorem 3 — Fermat’s Little Theorem
If is prime and :
Also, for every integer : .
(Stated by Fermat without proof; first published proof by Euler.)
Using it to reduce big exponents
Write with . Then
→ Reduce the exponent mod .
Example: . , ⇒ .
⇒ .