Number Theory: The Queen of Mathematics

Number theory is the study of the set of integers $\mathbb{Z}$. While the objects of study are simple, the problems are among the most difficult and beautiful in all of mathematics.

1. Prime Numbers and Factorization

A prime number is an integer $p > 1$ whose only divisors are $1$ and itself. The Fundamental Theorem of Arithmetic states that every integer $n > 1$ has a unique prime factorization.

Primes are the “atoms” of the number system. We can find them efficiently using the Sieve of Eratosthenes.

def sieve(n):
  primes = [True] * (n + 1)
  p = 2
  while (p * p <= n):
      if (primes[p]):
          for i in range(p * p, n + 1, p):
              primes[i] = False
      p += 1
  return [p for p in range(2, n + 1) if primes[p]]

# Find all primes up to 100
print(f"Primes up to 100: {sieve(100)}")

2. Greatest Common Divisor (GCD)

The GCD of two integers $a$ and $b$ is the largest positive integer that divides both. The Euclidean Algorithm calculates this by repeatedly applying the remainder operation: $\text{gcd}(a, b) = \text{gcd}(b, a \bmod b)$.

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

print(f"GCD of 48 and 18: {gcd(48, 18)}")
print(f"GCD of 101 and 103: {gcd(101, 103)}")

3. Modular Arithmetic: “Clock Math”

In modular arithmetic, we work with remainders. We say $a \equiv b \pmod{n}$ if $n$ divides $(a-b)$. This system forms a Ring, which is the basis for modern cryptography (like RSA).

4. Bezout’s Identity and Modular Inverses

Bezout’s Identity states that for any non-zero $a, b$, there exist integers $x, y$ such that $ax + by = \text{gcd}(a, b)$. We can find these coefficients using the Extended Euclidean Algorithm. This is how we find Modular Inverses, which allow us to “divide” in modular arithmetic.

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

# Find modular inverse of 3 mod 11
# We need x such that 3x = 1 (mod 11)
g, x, y = extended_gcd(3, 11)
if g == 1:
  print(f"Modular inverse of 3 mod 11 is: {x % 11}")

5. Summary Check