Home / Courses / Discrete Mathematics / Unit 7

Discrete Mathematics Unit 7: Number theory

Number theory studies integers: divisibility, primes and modular arithmetic. It's the math behind cryptography.

Covers: Divisibility, primes, GCD & Euclidean algorithm, modular arithmetic

Study guide

Number theory studies the integers. a divides b (a | b) if b = ak for some integer k. Divisibility is transitive, and if a divides b and c, it divides any combination of them. The division algorithm says any integer a can be written a = dq + r with 0 ≤ r < d; r is a mod d.

A prime has exactly two positive divisors, 1 and itself. The Fundamental Theorem of Arithmetic says every integer greater than 1 factors uniquely into primes. There are infinitely many primes (Euclid's proof by contradiction), and to test whether n is prime you only need to check divisors up to √n.

The greatest common divisor gcd(a, b) is the largest integer dividing both. The Euclidean algorithm finds it quickly: gcd(a, b) = gcd(b, a mod b), repeated until the remainder is 0. Bézout's identity says gcd(a, b) = ax + by for some integers x and y, which you can find by running the algorithm backward. Numbers are relatively prime if their gcd is 1, and lcm(a, b) = ab/gcd(a, b).

Modular arithmetic works with remainders: a ≡ b (mod n) means n divides a − b. Congruences can be added, subtracted and multiplied like equations. a has a multiplicative inverse mod n exactly when gcd(a, n) = 1, and it's found with Bézout's identity. Applications include check digits, hashing, and RSA encryption, which relies on Fermat's little theorem: aᵖ⁻¹ ≡ 1 (mod p) for prime p not dividing a.

ax + by = c has integer solutions exactly when d = gcd(a, b) divides c. If (x₀, y₀) is one solution, all solutions are x = x₀ + (b/d)t and y = y₀ − (a/d)t for integers t. ax ≡ b (mod n) has a solution exactly when d = gcd(a, n) divides b. Then divide a, b and n by d and solve with an inverse. The solution is unique mod n/d, which gives d solutions mod n.

Every common multiple of a and b is a multiple of lcm(a, b). Proof: divide a common multiple by the lcm; the remainder is also a common multiple but smaller than the lcm, so it must be 0. Euler's totient φ(n) counts the integers from 1 to n that are relatively prime to n, and a^φ(n) ≡ 1 (mod n) whenever gcd(a, n) = 1. For a prime p, φ(p) = p − 1, which gives Fermat's little theorem. To compute aᵏ mod n, reduce k mod φ(n) first.

Key ideas

• a | b means b = ka for some integer k.
• Every integer > 1 factors uniquely into primes.
• The Euclidean algorithm finds gcd(a, b) by repeated division.
• a ≡ b (mod n) means n divides a − b.
• A modular inverse of a mod n exists exactly when gcd(a, n) = 1.

Formulas and rules

Common mistakes

• Dividing in modular arithmetic without an inverse.
• Forgetting 1 isn't prime.

Words to know

Euclidean algorithm step

gcd(a, b) = gcd(b, a mod b)

Congruence a ≡ b (mod n)

n divides a − b.

Modular inverse

a has an inverse mod n exactly when gcd(a, n) = 1.

Greatest common divisor (gcd)

The largest integer dividing both numbers (gcd(48, 18) = 6).

Fundamental Theorem of Arithmetic

Every integer > 1 has a unique prime factorization.

Bézout's identity

gcd(a, b) = ax + by for some integers x and y.

Divides (a

b)|b = ak for some integer k.

Division algorithm

a = dq + r with 0 ≤ r < d.

Prime number

An integer > 1 whose only positive divisors are 1 and itself.

Relatively prime

gcd(a, b) = 1.

Least common multiple

lcm(a, b) = ab/gcd(a, b)

Fermat's little theorem

aᵖ⁻¹ ≡ 1 (mod p) for prime p not dividing a.

RSA encryption

Public-key cryptography based on modular exponentiation and factoring.

Sample practice questions

23 more questions like these, from level 1 to 5, are in the practice set.