Unit 3: Number Theory-III

I. Orientation: Congruences and Modular Arithmetic

Congruence, introduced by Gauss (Disquisitiones Arithmeticae, 1801), is the language for reasoning about remainders. This unit builds every technique below on a single relation: two integers are equivalent when they leave the same remainder on division by a fixed modulus.

• Definition of congruence: For integers a, b and a positive integer m, we write a ≡ b (mod m) if m | (a − b). Equivalently, a and b have the same remainder when divided by m.
• Residue classes: The modulus m partitions the integers into m disjoint classes [0], [1], …, [m−1]; the set {0,1,…,m−1} is the complete set of least non-negative residues.
• Arithmetic conventions: If a ≡ b (mod m) and c ≡ d (mod m), then a+c ≡ b+d, a−c ≡ b−d, and ac ≡ bd (mod m). Addition, subtraction and multiplication respect classes.
• Cancellation caveat: Division is not free — ac ≡ bc (mod m) implies a ≡ b (mod m/gcd(c,m)), not necessarily a ≡ b (mod m).
• Key tool: gcd and the Extended Euclidean Algorithm, which yields integers x, y with ax + by = gcd(a,b), underpin inversion and solvability throughout.

II. Linear Congruences

Solving ax ≡ b (mod m) and modular inverses

A linear congruence is the modular analogue of a linear equation; its solvability is governed entirely by a gcd.

A. Statement and solvability condition

The congruence ax ≡ b (mod m) seeks all integers x satisfying the relation.

• Solvability criterion: Let d = gcd(a, m). A solution exists iff d | b.
• Number of solutions: If d | b, there are exactly d incongruent solutions modulo m.
• Reason: ax ≡ b (mod m) is equivalent to the linear Diophantine equation ax − my = b, solvable precisely when d | b.

B. The modular inverse

When gcd(a, m) = 1, a has a unique inverse a⁻¹ with a·a⁻¹ ≡ 1 (mod m).

• Existence: The inverse exists iff gcd(a, m) = 1.
• Computation: Extended Euclidean Algorithm gives ax + my = 1, so x ≡ a⁻¹ (mod m).
• Use: Multiply ax ≡ b by a⁻¹ to get the unique solution x ≡ a⁻¹ b (mod m).

C. Worked example and limitations

Solving 3x ≡ 4 (mod 7):

gcd(3,7)=1  → unique solution
3·5 = 15 ≡ 1 (mod 7)  → 3⁻¹ ≡ 5
x ≡ 5·4 = 20 ≡ 6 (mod 7)

• Verification: 3·6 = 18 ≡ 4 (mod 7). ✓
• Limitation: When d = gcd(a,m) > 1 and d ∤ b, no solution exists (e.g. 2x ≡ 3 (mod 4) is unsolvable since gcd=2 ∤ 3).

III. The Chinese Remainder Theorem

Reconstructing an integer from its remainders

The CRT solves a system of simultaneous congruences with pairwise coprime moduli, guaranteeing a unique answer within the product modulus.

A. Statement and conditions

Given congruences with pairwise coprime moduli, a unique joint solution exists.

• System: x ≡ a₁ (mod m₁), x ≡ a₂ (mod m₂), …, x ≡ aₙ (mod mₙ).
• Condition: The moduli are pairwise coprime: gcd(mᵢ, mⱼ) = 1 for i ≠ j.
• Conclusion: There is a unique solution modulo M = m₁m₂⋯mₙ.

B. The Chinese remainder theorem — constructive method

The proof is constructive and gives a formula.

M  = m₁·m₂·…·mₙ
Mₖ = M / mₖ
yₖ ≡ Mₖ⁻¹ (mod mₖ)       (inverse of Mₖ modulo mₖ)
x  ≡ Σ aₖ·Mₖ·yₖ (mod M)

• Symbols: Mₖ is the product of all moduli except mₖ; yₖ its inverse mod mₖ.
• Why it works: Mₖ ≡ 0 (mod mⱼ) for j ≠ k, so each term contributes only to its own congruence.

C. Worked example

Solve x ≡ 2 (mod 3), x ≡ 3 (mod 5), x ≡ 2 (mod 7):

M = 105,  M₁=35, M₂=21, M₃=15
35 ≡ 2 (mod 3) → y₁ = 2   (2·2=4≡1)
21 ≡ 1 (mod 5) → y₂ = 1
15 ≡ 1 (mod 7) → y₃ = 1
x = 2·35·2 + 3·21·1 + 2·15·1 = 140+63+30 = 233 ≡ 23 (mod 105)

• Check: 23 = 3·7+2 (≡2 mod 3), 23 = 5·4+3 (≡3 mod 5), 23 = 7·3+2 (≡2 mod 7). ✓

IV. Computer Arithmetic with Large Integers

Representing and computing with numbers beyond machine word size

Cryptography needs integers of hundreds of digits, so numbers are held as arrays of digits in a large base and manipulated by algorithms whose cost is tracked carefully.

A. Representation of large integers

A big integer is stored positionally in a base matched to the machine word.

• Base choice: Digits taken base b = 2³² or 2⁶⁴ so each "digit" fits one register; the value is Σ dᵢ bⁱ.
• Storage: An array (d₀, d₁, …, d_{n−1}) plus a sign flag; length n grows with the number's size.

B. CRT-based and modular representation

The CRT lets a large integer be represented by its residues, parallelising arithmetic.

• Residue system: Pick coprime moduli m₁,…,mₙ; represent x by (x mod m₁, …, x mod mₖ).
• Benefit: Addition and multiplication act componentwise, with no carries between components — ideal for parallel hardware.
• Recovery: The original x < M is reconstructed via the CRT formula in Section III.B.

C. Cost of the basic operations

Efficiency is measured in bit operations as a function of digit length n.

• Addition/subtraction: O(n) — digitwise with carry propagation.
• Schoolbook multiplication: O(n²); Karatsuba reduces this to about O(n^1.585).
• Modular exponentiation: Computed by repeated squaring, reducing mod m at each step so operands never exceed m²:

result = 1;  base = a mod m
while e > 0:
    if e is odd: result = (result * base) mod m
    base = (base * base) mod m
    e = e >> 1        # e ← ⌊e/2⌋

• Bound: Exponentiation aᵉ mod m uses O(log e) multiplications — essential for RSA where e, m are enormous.

V. Fermat's Little Theorem

A prime modulus forces a power identity

Fermat's Little Theorem (Pierre de Fermat, 1640) states a fundamental relation between any integer and a prime modulus, and is the engine behind fast primality testing.

A. Statement and conditions

• Primary form: If p is prime and p ∤ a, then a^{p−1} ≡ 1 (mod p).
• Universal form: For any integer a, aᵖ ≡ a (mod p) (no coprimality needed).
• Consequence: For p ∤ a, the inverse is a⁻¹ ≡ a^{p−2} (mod p).

B. Worked example

Compute 3^100 mod 7:

FLT: 3⁶ ≡ 1 (mod 7)
100 = 6·16 + 4
3^100 = (3⁶)^16 · 3⁴ ≡ 1·3⁴ (mod 7)
3⁴ = 81 ≡ 4 (mod 7)

• Result: 3^100 ≡ 4 (mod 7); the theorem collapses a huge exponent to a tiny one.

C. Applications and limitations

• Fermat primality test: If a^{n−1} ≢ 1 (mod n) for some a, then n is composite (proof of compositeness).
• Carmichael numbers: The converse fails — composites like 561 = 3·11·17 satisfy a^{n−1} ≡ 1 for all coprime a, so passing the test does not prove primality.
• Relation to Euler: FLT is the special case φ(p) = p−1 of Euler's theorem a^{φ(m)} ≡ 1 (mod m) for gcd(a,m)=1.

VI. Applications of Congruences

Everyday and cryptographic uses of modular arithmetic

Congruences appear wherever data must be mapped, distributed, checked or protected using a fixed modulus.

A. Hashing and pseudorandom generation

• Hash functions: A key k maps to slot h(k) = k mod m, distributing records across m buckets; a prime m spreads keys evenly.
• Linear congruential generator: x_{n+1} = (a·xₙ + c) mod m produces pseudorandom sequences; period quality depends on choosing a, c, m (e.g. m = 2³¹).

B. Check digits and error detection

• ISBN-10: Digits satisfy Σ i·dᵢ ≡ 0 (mod 11); the check digit d₁₀ makes the weighted sum divisible by 11, catching single-digit and transposition errors.
• UPC/EAN: A weighted sum taken mod 10 validates barcodes.

C. Cryptography

• Caesar/affine ciphers: Encryption E(x) = (ax + b) mod 26; decryption needs a⁻¹ (mod 26), so gcd(a,26)=1.
• RSA: With n = pq, public exponent e, private d where ed ≡ 1 (mod φ(n)): encrypt c = mᵉ mod n, decrypt m = c^d mod n. Correctness rests on Fermat/Euler theorems; security rests on the hardness of factoring n.
• Diffie–Hellman: Shared secret from g^{ab} mod p, relying on the difficulty of the discrete logarithm modulo a large prime.

D. Calendars and scheduling

• Day-of-week arithmetic: Weekday cycles are computed mod 7; e.g. 100 days after a Monday is (0 + 100) mod 7 = 2, a Wednesday.
• Zeller-type formulas: Combine mod 7 and mod 12 reductions to map any date to a weekday, illustrating congruences over multiple moduli.