Number Theory

Number Theory

---

Definitions

---

Formulas

---

Python Implementations

GCD and Extended Euclidean Algorithm

def gcd(a, b):
    while b:
        a, b = b, a % b
    return a

def extended_gcd(a, b):
    if a == 0:
        return b, 0, 1
    g, x, y = extended_gcd(b % a, a)
    return g, y - (b // a) * x, x

def mod_inverse(a, m):
    g, x, _ = extended_gcd(a % m, m)
    if g != 1:
        raise ValueError("Modular inverse does not exist")
    return x % m

def lcm(a, b):
    return a * b // gcd(a, b)

print(f"gcd(48, 18) = {gcd(48, 18)}")
print(f"lcm(4, 6) = {lcm(4, 6)}")
print(f"mod_inverse(3, 7) = {mod_inverse(3, 7)}")

Modular Exponentiation

def mod_pow(base, exp, mod):
    result = 1
    base %= mod
    while exp > 0:
        if exp % 2 == 1:
            result = (result * base) % mod
        exp //= 2
        base = (base * base) % mod
    return result

def is_prime_miller_rabin(n, k=10):
    if n < 2:
        return False
    if n == 2 or n == 3:
        return True
    if n % 2 == 0:
        return False

    d, r = n - 1, 0
    while d % 2 == 0:
        d //= 2
        r += 1

    for _ in range(k):
        a = 2 + (hash(str(_)) % (n - 4))
        x = pow(a, d, n)
        if x == 1 or x == n - 1:
            continue
        for _ in range(r - 1):
            x = pow(x, 2, n)
            if x == n - 1:
                break
        else:
            return False
    return True

print(f"7^222 mod 11 = {mod_pow(7, 222, 11)}")
print(f"Is 97 prime: {is_prime_miller_rabin(97)}")

Sieve of Eratosthenes

def sieve_of_eratosthenes(limit):
    is_prime = [True] * (limit + 1)
    is_prime[0] = is_prime[1] = False
    for i in range(2, int(limit**0.5) + 1):
        if is_prime[i]:
            for j in range(i*i, limit + 1, i):
                is_prime[j] = False
    return [i for i in range(2, limit + 1) if is_prime[i]]

primes = sieve_of_eratosthenes(100)
print(f"Primes below 100: {primes}")
print(f"Count: {len(primes)}")

Euler's Totient Function

def euler_totient(n):
    result = n
    p = 2
    temp = n
    while p * p <= temp:
        if temp % p == 0:
            while temp % p == 0:
                temp //= p
            result -= result // p
        p += 1
    if temp > 1:
        result -= result // temp
    return result

for n in range(1, 21):
    print(f"phi({n}) = {euler_totient(n)}")

Chinese Remainder Theorem

def chinese_remainder_theorem(remainders, moduli):
    M = 1
    for m in moduli:
        M *= m
    x = 0
    for i in range(len(moduli)):
        Mi = M // moduli[i]
        yi = mod_inverse(Mi, moduli[i])
        x += remainders[i] * Mi * yi
    return x % M

# Solve: x ≡ 2 (mod 3), x ≡ 3 (mod 5), x ≡ 2 (mod 7)
remainders = [2, 3, 2]
moduli = [3, 5, 7]
print(f"Solution: x = {chinese_remainder_theorem(remainders, moduli)}")

---

Applications in AI/ML

---

Common Mistakes

---

Interview Questions

1. What is the Euclidean algorithm and its time complexity? It computes $\gcd(a, b)$ by repeated division: $\gcd(a, b) = \gcd(b, a \bmod b)$. Time complexity: $O(\log(\min(a, b)))$.

2. How do you compute modular inverse? Use the extended Euclidean algorithm: find $x, y$ such that $ax + my = \gcd(a, m) = 1$. Then $x \pmod{m}$ is the inverse.

3. Explain Fermat's Little Theorem with an example. If $p = 7$ and $a = 3$, then $3^6 \equiv 1 \pmod{7}$. This means $3^6 = 729 = 104 \times 7 + 1$.

4. How does RSA encryption work? Choose primes $p, q$, compute $n = pq$ and $\phi(n) = (p-1)(q-1)$. Pick $e$ coprime to $\phi(n)$. Private key $d = e^{-1} \pmod{\phi(n)}$. Encrypt: $c = m^e \pmod{n}$. Decrypt: $m = c^d \pmod{n}$.

5. What is the Chinese Remainder Theorem? A system of congruences $x \equiv a_i \pmod{m_i}$ with pairwise coprime $m_i$ has a unique solution modulo $M = \prod m_i$.

6. How do you check if a number is prime efficiently? For small numbers, trial division up to $\sqrt{n}$. For large numbers, use Miller-Rabin probabilistic test (polynomial time).

7. What is Euler's totient function? $\phi(n)$ counts integers from 1 to $n$ coprime to $n$. For $n = p_1^{e_1} \cdots p_k^{e_k}$: $\phi(n) = n \prod (1 - 1/p_i)$.

8. Why is modular arithmetic important in computer science? It provides efficient computation with bounded integers, underpins cryptography and hashing, and enables arithmetic in finite fields.

---

Practice Problems

---

Primality Testing Deep Dive

def trial_division(n):
    if n < 2:
        return False
    if n < 4:
        return True
    if n % 2 == 0 or n % 3 == 0:
        return False
    i = 5
    while i * i <= n:
        if n % i == 0 or n % (i + 2) == 0:
            return False
        i += 6
    return True

def fermat_test(n, k=10):
    if n < 2:
        return False
    if n == 2 or n == 3:
        return True
    for _ in range(k):
        a = 2 + (hash(str(_)) % (n - 3))
        if pow(a, n - 1, n) != 1:
            return False
    return True

# Compare methods
test_numbers = [97, 561, 1105, 1729, 2147483647]
for n in test_numbers:
    td = trial_division(n)
    fr = fermat_test(n)
    print(f"{n}: trial={td}, fermat={fr}")

---

Quadratic Residues

def legendre_symbol(a, p):
    if p < 2 or p % 2 == 0:
        raise ValueError("p must be an odd prime")
    a = a % p
    if a == 0:
        return 0
    ls = pow(a, (p - 1) // 2, p)
    return -1 if ls == p - 1 else ls

def quadratic_residues(p):
    return sorted(set(pow(x, 2, p) for x in range(p)))

for p in [7, 11, 13]:
    qr = quadratic_residues(p)
    print(f"p={p}: QR={qr}, QNR={[x for x in range(1, p) if x not in qr]}")

---

Quick Reference

---

Cross-References

• Graph Theory — Discrete Graphs: Graph coloring uses modular arithmetic
• Trees — Discrete Trees: Cayley's formula involves exponentiation
• Recurrence Relations — Discrete Recurrence: Modular exponentiation is recursive
• Boolean Algebra — Discrete Boolean: Finite field arithmetic for error-correcting codes
• Automata Theory — Discrete Automata: Finite state machines over modular states
• Applications — Discrete Applications: Cryptography and coding theory use number theory