Number Theory

a | b     "a divides b" — b = ka for some integer k
a ∤ b     "a does not divide b"

Properties:
  a | 0     for all a != 0
  1 | a     for all a
  a | a     for all a != 0 (reflexive)
  a | b and b | c → a | c  (transitive)
  a | b and a | c → a | (bx + cy) for all integers x, y

Division algorithm:
  For any integers a, b (b > 0):
  a = bq + r    where 0 <= r < b
  q = quotient, r = remainder

By 2:   last digit even
By 3:   digit sum divisible by 3
By 4:   last two digits divisible by 4
By 5:   ends in 0 or 5
By 6:   divisible by 2 AND 3
By 8:   last three digits divisible by 8
By 9:   digit sum divisible by 9
By 11:  alternating digit sum divisible by 11

Prime: integer p > 1 with no divisors other than 1 and p
Composite: integer > 1 that is not prime

Fundamental theorem of arithmetic:
  Every integer > 1 has a UNIQUE prime factorization (up to order)
  60 = 2^2 × 3 × 5
  100 = 2^2 × 5^2
  360 = 2^3 × 3^2 × 5

Testing primality:
  Only need to check divisors up to sqrt(n)
  If n has no prime factor <= sqrt(n), then n is prime

Primes < 100:
  2 3 5 7 11 13 17 19 23 29 31 37 41 43 47
  53 59 61 67 71 73 79 83 89 97

There are infinitely many primes (Euclid's proof)

# Factor a number
factor 360
# 360: 2 2 2 3 3 5

# Check if prime
factor 97
# 97: 97   (only factor is itself → prime)

# Trial division in bash
is_prime() {
    local n=$1 i=2
    (( n < 2 )) && return 1
    while (( i * i <= n )); do
        (( n % i == 0 )) && return 1
        ((i++))
    done
    return 0
}

gcd(a, b) = largest d that divides both a and b

Euclidean algorithm:
  gcd(a, b) = gcd(b, a mod b)    until b = 0
  gcd(a, 0) = a

Example:
  gcd(252, 105)
  = gcd(105, 252 mod 105) = gcd(105, 42)
  = gcd(42, 105 mod 42) = gcd(42, 21)
  = gcd(21, 42 mod 21) = gcd(21, 0)
  = 21

Properties:
  gcd(a, b) = gcd(b, a)
  gcd(a, 0) = a
  gcd(a, 1) = 1
  a and b coprime (relatively prime) iff gcd(a, b) = 1

lcm(a, b) = smallest positive m divisible by both a and b

Relationship: lcm(a, b) = |a × b| / gcd(a, b)

Example:
  lcm(12, 18) = 12 × 18 / gcd(12, 18) = 216 / 6 = 36

Applications:
  Scheduling: events at intervals of 12 and 18 days
              next coincidence in lcm(12, 18) = 36 days
  Fractions:  common denominator = lcm of denominators

Find x, y such that: ax + by = gcd(a, b)    (Bezout's identity)

Modular inverse:
  a^(-1) mod m exists iff gcd(a, m) = 1
  Find x such that ax ≡ 1 (mod m)

Fermat's little theorem:
  If p is prime and gcd(a, p) = 1:
  a^(p-1) ≡ 1 (mod p)
  So: a^(-1) ≡ a^(p-2) (mod p)

Euler's theorem (generalization):
  If gcd(a, n) = 1:
  a^φ(n) ≡ 1 (mod n)

Euler's totient φ(n):
  Count of integers 1..n coprime to n
  φ(p) = p - 1           (p prime)
  φ(p^k) = p^k - p^(k-1)
  φ(mn) = φ(m)φ(n)       (if gcd(m,n) = 1)

Key generation:
  1. Choose large primes p, q
  2. n = p × q
  3. φ(n) = (p-1)(q-1)
  4. Choose e coprime to φ(n)  (public exponent, often 65537)
  5. Compute d = e^(-1) mod φ(n)  (private exponent)
  Public key: (n, e)
  Private key: d

Encrypt: c = m^e mod n
Decrypt: m = c^d mod n

Security: factoring n into p and q is computationally hard

Z_n = {0, 1, 2, ..., n-1}    residues mod n

Z_5 = {0, 1, 2, 3, 4}

Addition table mod 5:
  + | 0 1 2 3 4
  ──┼──────────
  0 | 0 1 2 3 4
  1 | 1 2 3 4 0
  2 | 2 3 4 0 1
  3 | 3 4 0 1 2
  4 | 4 0 1 2 3

Multiplication table mod 5:
  × | 0 1 2 3 4
  ──┼──────────
  0 | 0 0 0 0 0
  1 | 0 1 2 3 4
  2 | 0 2 4 1 3
  3 | 0 3 1 4 2
  4 | 0 4 3 2 1

Every nonzero element has an inverse (5 is prime)

If gcd(m, n) = 1, the system:
  x ≡ a (mod m)
  x ≡ b (mod n)
has a unique solution mod mn.

Example:
  x ≡ 2 (mod 3)
  x ≡ 3 (mod 5)
  Solution: x ≡ 8 (mod 15)

Application: parallel computation
  Compute mod small primes, combine with CRT