Primes and Great Common Divisors – Rosen

Section 4.3

Anna-Simone Frank1

MNF130

Spring 2024

1
Slides created by Tom Michoel and modified by Erik Maartensson and
Anna-Simone Frank
Prime numbers and integer factorization
I An integer p > 1 is called prime if it is divisible only by 1 and itself
(its only factors are 1 and p). Otherwise it is called composite.
I The fundamental theorem of arithmetic states that every integer
n greater than 1 can be written uniquely as a prime or as the
product of two or more primes, where the prime factors are written
in nondecreasing order. In other words

n = p1e1 p2e2 · · · pkek , (1)

where p1 < p2 < · · · < pk are primes and e1 , e2 , . . . , ek are positive
integers.
I Examples:

14 = 2 · 7
30 = 2 · 3 · 5
100 = 2 · 2 · 5 · 5 = 22 · 52

I Given n, the problem of writing n on the form (1) is called integer

factorization.
3
On the difficulty of factoring integers

I Given primes p1 , p2 , . . . , pk and exponents e1 , e2 , . . . , ek , computing

n = p1e1 · · · pkek is easy.
I On the other hand, given n, no efficient algorithm for factoring it is
known!
I Factoring a 250 digit (829 bit) integer, designed to be hard to
factor, using the best known algorithm, takes the equivalent of 2700
years of single-processor computing time2
I The difference between the difficulty of multiplying integers and
factoring integers is what makes RSA encryption work!

2 https://en.wikipedia.org/wiki/RSA_numbers#RSA-250
4
Theorem √
√ a prime divisor ≤ n.
If n is a composite integer, then n has
(Hence, if n has no prime divisor ≤ n, then n is prime.)

Proof.
I If n is composite, it has factors 1 < a, b < n such that n = ab.
√ √ √ √
I If a > n and b > n, then ab > n n = n, which is a
contradiction.
√ √ √
I Hence a ≤ n or b ≤ n, and n has a divisor ≤ n.
I This divisor is either prime, or has a prime divisor less than itself. In
√
both cases n has a prime divisor ≤ n.

Example
Is 149 prime?
√
The only primes ≤ 149 = 12.0266 are 2, 3, 5, 7, 11. 149 is not divisible
by any of those and hence it must be prime.

5
Theorem
There are infinitely many primes.

Proof (Euclid, ca. 300BC).

I Assume that there are only finitely many primes p1 , p2 , . . . , pn .
I Let Q = p1 p2 . . . pn + 1.
I If Q is prime, we have found a new prime not in the original list.
I If Q is not prime, then it has a prime factor p | Q by the
fundamental theorem of arithmetic.
I If pj | Q then pj would divide Q − p1 p2 . . . pn = 1, which is
impossible.
I Hence none of the pj can divide Q and we have again found a prime
p 6∈ {p1 , p2 , . . . , pn }.

7
Greatest common divisors

Definition
The greatest common divisor of two integers a and b not both zero,
written gcd(a, b), is the largest integer d such that d | a and d | b. If
gcd(a, b) = 1, then we say that a and b are relatively prime.

Example
gcd(36, 90) = gcd(22 · 32 , 2 · 32 · 5) = 2 · 32 = 18.

Theorem
Given two integers with integer factorizations a = p1e1 · · · pkek and
min(e ,f ) min(e ,f )
b = p1f1 · · · pkfk , we have gcd(a, b) = p1 1 1 · · · pk k k .

8
Least common multiple
Definition
The least common multiple of two non-zero integers a and b is the
smallest positive integer that is divisible by both a and b.

Example
lcm(36, 90) = lcm(22 · 32 , 2 · 32 · 5) = 22 · 32 · 5 = 180.

Example (Adding fractions using the least common multiple)

Since lcm(36, 90) = 180, 180/90 = 2 and 180/36 = 5 we have

1 1 5 2 7
+ = + = .
36 90 180 180 180

Theorem
Given two integers with integer factorizations a = p1e1 · · · pkek and
max(e1 ,f1 ) max(ek ,fk )
b = p1f1 · · · pkfk , we have lcm(a, b) = p1 · · · pk .
9
Greatest common divisor and least common multiple
Theorem
Given two positive integers a and b we have ab = gcd(a, b) lcm(a, b).

Proof.
Let a = p1e1 · · · pkek and b = p1f1 · · · pkfk be the integer factorizations of the
two integers. Then
min(e1 ,f1 ) min(ek ,fk ) max(e1 ,f1 ) max(ek ,fk )
gcd(a, b) lcm(a, b) = p1 · · · pk · p1 · · · pk
min(e1 ,f1 )+max(e1 ,f1 ) min(ek ,fk )+max(ek ,fk )
= p1 · · · pk
= p1e1 +f1 · · · pkek +fk = p1e1 p1f1 · · · pkek pkfk
= p1e1 · · · pkek · p1f1 · · · pkfk = ab.

Example
gcd(36, 90) · lcm(36, 90) = 18 · 180 = 3240 = 36 · 90.
A result of this theorem is that if we can calculate gcd(a, b), then we get
lcm(a, b) = ab/ gcd(a, b) for free. 10
On efficient computation of the greatest common divisor

Calculating the greatest common divisor using integer factoring is

inefficient in general since factoring is hard!
Example
How do we calculate gcd(90, 36) in a more efficient way?
I Using the division algorithm we get 90 = 2 · 36 + 18.
I Hence any divisor of 36 and 18 is also a divisor of 90, and any
divisor of 90 and 36 is also a divisor of 18 = 90 − 2 · 36. Hence
gcd(90, 36) = gcd(36, 18).
I We have 36 = 2 · 18 + 0. Because 18 divides 36, it follows that
gcd(90, 36) = gcd(36, 18) = 18.

11
The Euclidean algorithm
Theorem
For a, b integers with a ≥ b, gcd(a, b) = gcd(b, a mod b).

Proof.
I Let r = a mod b, q = a div b, and

S = {d | d divides a and b}
T = {d | d divides b and r }

I Take d ∈ S arbitrary. Then d divides a − bq = r , and hence d ∈ T .

Hence S ⊆ T .
I Let d ∈ T arbitrary. Then d divides bq + r = a, and hence d ∈ S.
Hence T ⊆ S.
I Hence S = T .
I gcd(a, b) is the largest element in S, gcd(b, r ) is the largest element
in T , and S = T . Hence gcd(a, b) = gcd(b, r )

12
Repeated application of this theorem produces gcd(a, b):
procedure gcd(a, b : positive integers, a ≥ b)
x := a
y := b
while y 6= 0 do
r := x mod y
x := y
y := r
return x

13
 Remember gcd(x, y ) = gcd(y , x mod y ) when x ≥ y

Example
Apply the Euclidean algorithm to find gcd(312, 42):
I

(x1 , y1 ) = (312, 42)

312 = 7 · 42 + 18 (x2 , y2 ) = (42, 18)
42 = 2 · 18 + 6 (x3 , y3 ) = (18, 6)
18 = 3 · 6 + 0 (x4 , y4 ) = (6, 0)

I Hence gcd(312, 42) = 6.

I Work backwards to find

6 = 42 − 2 · 18 = 42 − 2 · (312 − 7 · 42) = 15 · 42 − 2 · 312

14
Bézout’s theorem
Theorem
If a and b are positive integers, then there exist integers s and t such that
gcd(a, b) = sa + tb.

Algorithm
I The Euclidean algorithm generates x1 = a, y1 = b, and for i = 1, . . . , n − 1

xi+1 = yi (2)
yi+1 = xi mod yi = xi − qi yi (3)

where qi = xi div yi , the terminal condition is yn = 0, and xn = gcd(a, b).

I By iterating (2) and (3) backwards, we find

xn = yn−1 = 0 · xn−1 + yn−1

= xn−2 − qn−2 yn−2 = yn−3 − qn−2 (xn−3 − qn−3 yn−3 )
= −qn−2 xn−3 + (1 + qn−2 qn−3 )yn−3
..
.
= sx1 + ty1
15
A note on Bézout’s theorem

Bézout’s theorem states that given positive integers a and b, we can

write d = gcd(a, b) as a linear combination of a and b.
Since d|a and d|b, we have that d|sa + tb, for all s, t ∈ Z. Thus
I All linear combinations of a and b are divisible by d.
I All linear combinations of a and b are larger than or equal to d.
This will be important in the next lecture on multiplicative inverses in Zm
and in the RSA lecture.

16
Exercise
Find gcd(252, 198) and write the result as a linear combination of 252
and 198. Let’s do it on the blackboard!

17