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

  1. Use the Euclidean algorithm to confirm .
  2. Reverse the steps to write (Bézout coefficients).
  3. 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)

  1. , and (product of all the other moduli).
  2. , so find inverse of mod .

Why it works: mod , every term with vanishes (), and , so .

Example (Sun-Tsu): .

(inverse of mod )
132352 ()
253211 ()
372151 ()

.

Back substitution (often faster by hand)

Example: .

  1. . Plug into 2nd: .
  2. . Plug into 3rd: .
  3. ⇒ .

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

  1. Choose moduli , pairwise coprime, with product larger than any result.
  2. Do , componentwise, reducing each component mod its .
  3. 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: . , ⇒ .
⇒ .