Difficulty: Introductory to Intermediate | Prerequisites: Division and Modular Arithmetic notes
Primes and GCDs are the second layer of the number theory stack in this course. You need to be comfortable with divisibility and the division algorithm before tackling this material. Primes are the atoms of the integers: every positive integer breaks down into them uniquely. The Euclidean algorithm is the workhorse that computes GCDs efficiently, and its extended version is what makes RSA key generation possible. If you are revising for the exam, this section is where the algorithmic questions come from.
A prime is an integer greater than 1 whose only divisors are 1 and itself, and every positive integer factors into primes in exactly one way. The Euclidean algorithm computes the greatest common divisor of two integers by repeated division, and the extended version finds integer coefficients that express the GCD as a linear combination of the two inputs, which is exactly what RSA needs to generate decryption keys.
Prime number
An integer p greater than 1 that is divisible only by 1 and p. In simple terms, a prime cannot be broken into smaller integer factors.
Composite number
An integer greater than 1 that is not prime, meaning it has at least one divisor other than 1 and itself. Think of it as a number that can be split into smaller building blocks.
The Fundamental Theorem of Arithmetic
Every positive integer greater than 1 can be written as a product of primes in exactly one way (ignoring the order of the factors). Think of it as saying the primes are the periodic table of numbers: every integer has a unique recipe.
Greatest common divisor, GCD / gcd(a, b)
The largest positive integer that divides both a and b. In simple terms, the biggest number that goes evenly into both.
Coprime (relatively prime)
Two integers a and b are coprime if gcd(a, b) = 1. Think of it as the two numbers sharing no prime factors at all. This concept is central to RSA.
Bezout's Theorem (Bezout's identity)
For any positive integers a and b, there exist integers s and t such that gcd(a, b) = sa + tb. In simple terms, you can always write the GCD as a combination of the two original numbers using integer multipliers. The Extended Euclidean Algorithm finds s and t.
Primes less than 20: 2, 3, 5, 7, 11, 13, 17, 19.
Note that 1 is not prime (by convention and definition), and 2 is the only even prime.
The Fundamental Theorem of Arithmetic guarantees unique prime factorisation. For example, 60 = 2 × 2 × 3 × 5 = 2² × 3 × 5, and no other combination of primes gives 60.
The key lemma: if a = bq + r, then gcd(a, b) = gcd(b, r). This means you can repeatedly replace the larger number with the remainder until you hit zero, and the last non-zero remainder is the GCD.
Worked example: gcd(414, 662)
662 = 1 × 414 + 248, so gcd(662, 414) = gcd(414, 248)
414 = 1 × 248 + 166, so gcd(414, 248) = gcd(248, 166)
248 = 1 × 166 + 82, so gcd(248, 166) = gcd(166, 82)
166 = 2 × 82 + 2, so gcd(166, 82) = gcd(82, 2)
82 = 41 × 2 + 0, so gcd(82, 2) = 2
Therefore gcd(414, 662) = 2.
Pseudocode:
function gcd(a, b):
while b ≠ 0:
temp = b
b = a mod b
a = temp
return aBezout's Theorem says that for positive integers a and b, there exist integers s and t such that gcd(a, b) = sa + tb.
The Extended Euclidean Algorithm finds s and t by working backwards through the steps of the standard algorithm.
Worked example: gcd(25, 11) = 1
We need s and t such that 1 = 25s + 11t.
25 = 2 × 11 + 3
11 = 3 × 3 + 2
3 = 1 × 2 + 1
2 = 2 × 1 + 0
Back-substitution:
1 = 3 - 1 × 2
1 = 3 - 1 × (11 - 3 × 3) = 4 × 3 - 1 × 11
1 = 4 × (25 - 2 × 11) - 1 × 11 = 4 × 25 - 9 × 11
So s = 4, t = -9. Check: 4 × 25 + (-9) × 11 = 100 - 99 = 1.
This process is how RSA finds the private decryption exponent d.
GCD Lemma: If a = bq + r, then gcd(a, b) = gcd(b, r)
Bezout's Identity: gcd(a, b) = sa + tb for some integers s and t
Euclidean Algorithm: Repeatedly apply a = bq + r, replacing (a, b) with (b, r) until r = 0. The last non-zero value is the GCD.
Unique Prime Factorisation: Every integer n > 1 can be written as n = p1^a1 × p2^a2 × ... × pk^ak where each pi is prime
The Euclidean algorithm is one of the oldest algorithms still in everyday computational use. RSA encryption depends on computing gcd(e, phi) = 1 to choose the public exponent, and then the Extended Euclidean Algorithm to find the private key d. Whenever your browser makes an HTTPS connection, this machinery runs underneath.
Students often think 1 is prime. It is not, by definition. Including 1 as a prime would break the uniqueness of prime factorisation.
Students confuse gcd(a, b) = 1 with "a and b have no common factors." They do share the factor 1, which every integer has. The point is they share no prime factor.
Students try to find the GCD by listing all factors of both numbers. This works for small numbers but is computationally impractical for large ones. The Euclidean algorithm is the efficient method.
Students forget that the Extended Euclidean Algorithm's coefficients s and t can be negative. That is expected and correct.
⚠️ Be prepared to trace through the Euclidean algorithm step by step for a given pair of numbers. This is a standard exam question.
⚠️ Know how to do back-substitution in the Extended Euclidean Algorithm. This is harder than the forward pass and frequently tested.
⚠️ The Fundamental Theorem of Arithmetic is often tested as a short proof or as the justification for why a step in another proof works.
True or false: 1 is a prime number. (False)
Fill in the blank: gcd(48, 18) = ___. (6)
True or false: If gcd(a, b) = 1, then a and b are called coprime. (True)
Fill in the blank: By Bezout's Theorem, gcd(a, b) can be written as ___ + ___. (sa + tb, for some integers s, t)
True or false: The Euclidean algorithm terminates because the remainders form a strictly decreasing sequence of non-negative integers. (True)
Q: Use the Euclidean algorithm to find gcd(270, 192).
A: 270 = 1 × 192 + 78; 192 = 2 × 78 + 36; 78 = 2 × 36 + 6; 36 = 6 × 6 + 0. So gcd(270, 192) = 6.
Q: Find integers s and t such that gcd(35, 12) = 35s + 12t.
A: 35 = 2 × 12 + 11; 12 = 1 × 11 + 1; 11 = 11 × 1 + 0. Back-substitute: 1 = 12 - 1 × 11 = 12 - 1 × (35 - 2 × 12) = 3 × 12 - 1 × 35. So s = -1, t = 3.
Q: Why does the Euclidean algorithm always terminate?
A: Each step produces a remainder r that satisfies 0 ≤ r < d (the current divisor). Since the remainders are non-negative integers that strictly decrease, they must eventually reach 0.
Q: Is 91 prime? If not, give its prime factorisation.
A: 91 = 7 × 13. It is composite.
The Euclidean algorithm relies on repeated application of the division algorithm from the previous topic. The Extended Euclidean Algorithm is used directly in RSA key generation to compute the modular inverse of the public exponent. Coprimality (gcd = 1) is the condition that makes modular inverses exist, which underpins all of public-key cryptography.
Prime, composite, prime factorisation, Fundamental Theorem of Arithmetic, greatest common divisor, GCD, Euclidean algorithm, Extended Euclidean Algorithm, Bezout's Theorem, Bezout's identity, coprime, relatively prime, modular inverse, back-substitution, number theory, HSK3X, Foundations of Computer Science, Purdue