Number Theory: Key Concepts in Modular Arithmetic and Theorems

Division Algorithm

To divide a by b (b > 0), find q = floor(a/b), then r = a − qb. Example: 23 ÷ 5 → q=4, r=3.

Linear Congruence Theorem

To solve ax ≡ b (mod n): check if gcd(a,n) divides b. If yes, divide through by gcd and find solutions. Example: 6x ≡ 9 mod 15 → gcd(6,15)=3 divides 9 → reduce to 2x ≡ 3 mod 5 → solution x ≡ 4 mod 5 → 3 solutions mod 15.

Chinese Remainder Theorem

Step 1: Solve each congruence separately. Step 2: Use successive substitution or constructive formula. Example: x ≡ 2 mod 3, x ≡ 3 mod 5 → solution x ≡ 8 mod 15.

Fermat's Little Theorem

To compute a^(p−1) mod p quickly: reduce exponent mod (p−1). Example: 7^100 mod 13 → 100 ≡ 4 mod 12 → 7^4 mod 13 = 2401 mod 13 = 9.

Carmichael Numbers

Recognize by testing a^(n−1) ≡ 1 mod n for many a coprime to n. Example: 561 is Carmichael since it passes the test for all coprime a.

Congruences mod p^e Use lifting:

solve mod p, then extend to mod p^2, etc. Example: Solve x^2 ≡ 1 mod 9 → first solve mod 3 (x ≡ ±1), then lift to mod 9 → solutions x ≡ 1, 8.

Euler's Totient Function φ(n)

Compute using prime factorization: φ(n) = n ∏(1 − 1/p). Example: φ(120) = 120(1−1/2)(1−1/3)(1−1/5) = 32.

Euler's Theorem

To compute a^φ(n) mod n: reduce exponent mod φ(n). Example: gcd(7,20)=1, φ(20)=8 → 7^8 ≡ 1 mod 20.

Totient of Prime Powers Formula:

φ(p^k) = p^k − p^(k−1). Example: φ(2^5) = 32 − 16 = 16.

Legendre Symbol

Compute (a/p) using: (a/p) ≡ a^((p−1)/2) mod p. Example: (3/7) → 3^3 = 27 ≡ −1 mod 7 → (3/7) = −1.

Quadratic Reciprocity

Use reciprocity law: (p/q)(q/p) = (−1)^((p−1)(q−1)/4). Example: (3/11)(11/3) = (−1)^((2*10)/4) = (−1)^5 = −1.

Finding Square Roots mod p

Step 1: Check if solution exists via Legendre symbol. Step 2: Use trial or Tonelli-Shanks algorithm. Example: Solve x^2 ≡ 4 mod 7 → check (4/7)=1 → solutions x ≡ ±2 mod 7.

Solving Linear Congruences

Reduce to simpler congruence using gcd. Example: Solve 14x ≡ 21 mod 35 → gcd(14,35)=7 divides 21 → reduce to 2x ≡ 3 mod 5 → solution x ≡ 4 mod 5 → 7 solutions mod 35.

Division Algorithm

Theorem: For integers a, b with b > 0, there exist unique q, r such that a = qb + r with 0 ≤ r < b.

Linear Congruence Theorem

Theorem: The congruence ax ≡ b (mod n) has a solution iff gcd(a,n) divides b. If so, there are exactly gcd(a,n) solutions modulo n.

Chinese Remainder Theorem

If n1, n2, ..., nk are pairwise coprime, then the system x ≡ ai (mod ni) has a unique solution modulo N = n1n2...nk.

Fermat's Little Theorem

If p is prime and a ≠ 0 mod p, then a^(p−1) ≡ 1 (mod p).

Carmichael Numbers

A composite n such that a^(n−1) ≡ 1 (mod n) for all a coprime to n.

Congruences mod p^e

Solutions modulo p^e can often be lifted from solutions modulo p using Hensel's lemma or iterative methods.

Euler's Totient Function φ(n)

φ(n) counts the positive integers less than n that are coprime to n.

Euler's Theorem

If gcd(a,n) = 1, then a^φ(n) ≡ 1 (mod n).

Totient of Prime Powers

φ(p^k) = p^k − p^(k−1).

Legendre Symbol

( a / p ) = 1 if a is a quadratic residue mod p, −1 if not, and 0 if p divides a.

Euler's Criterion

For odd prime p, ( a / p ) ≡ a^((p−1)/2) (mod p).

Quadratic Reciprocity

For distinct odd primes p, q: (p/q)(q/p) = (−1)^((p−1)(q−1)/4).