Number theory

Number theory studies whole numbers: primes, divisibility and remainders. Modular arithmetic (“clock arithmetic”) underpins modern cryptography, which keeps online banking secure.

Key facts

  • a mod n is the remainder when a is divided by n.
  • a ≡ b (mod n) means a and b have the same remainder.
  • Euclidean algorithm: gcd(a, b) = gcd(b, a mod b).
  • Every whole number > 1 is a product of primes in exactly one way.

Worked examples

Example 1

Find gcd(252, 105) using the Euclidean algorithm.

  1. 252 = 2 × 105 + 42
  2. 105 = 2 × 42 + 21
  3. 42 = 2 × 21 + 0, so gcd = 21.

Answer: 21

Example 2

What is 7¹⁰⁰ mod 10 (the last digit)?

  1. 7, 49, 343, 2401: last digits 7, 9, 3, 1, then repeat every 4.
  2. 100 is a multiple of 4, so the last digit is 1.

Answer: 1