Euclidean Algorithm

Lecture 3

Justin Stevens

Justin Stevens Euclidean Algorithm (Lecture 3) 1 / 43

Outline

1 Euclidean Algorithm
Greatest Common Divisor
Proof
GCD of 3 Numbers
Euclidean Algorithm Challenges

2 Bezout’s Identity

3 Linear Congruences

Justin Stevens Euclidean Algorithm (Lecture 3) 2 / 43

Greatest Common Divisor

We can find the set of all positive divisors of the number n, denoted D(n):

Justin Stevens Euclidean Algorithm (Lecture 3) 3 / 43

Greatest Common Divisor

We can find the set of all positive divisors of the number n, denoted D(n):

D(12) = {1, 2, 3, 4, 6, 12}

D(30) = {1, 2, 3, 5, 6, 10, 15, 30}.

Justin Stevens Euclidean Algorithm (Lecture 3) 3 / 43

Greatest Common Divisor

We can find the set of all positive divisors of the number n, denoted D(n):

D(12) = {1, 2, 3, 4, 6, 12}

D(30) = {1, 2, 3, 5, 6, 10, 15, 30}.

The set of common divisors of 12 and 30 is D(12) ∩ D(30) = {1, 2, 3, 6}.

The max is 6. We say that this is the greatest common divisor of 12 and 30.

Justin Stevens Euclidean Algorithm (Lecture 3) 3 / 43

Greatest Common Divisor

We can find the set of all positive divisors of the number n, denoted D(n):

D(12) = {1, 2, 3, 4, 6, 12}

D(30) = {1, 2, 3, 5, 6, 10, 15, 30}.

The set of common divisors of 12 and 30 is D(12) ∩ D(30) = {1, 2, 3, 6}.

The max is 6. We say that this is the greatest common divisor of 12 and 30.

Definition. For two integers a and b the set of common divisors of

a and b is D(a) ∩ D(b). The maximum element in this set is the
greatest common divisor of a and b, gcd(a, b).

By definition, gcd(a, b) | a and gcd(a, b) | b since it is a divisor of both. We

do not define gcd(0, 0) since every positive integer divides 0.

Theorem. When a | b, gcd(a, b) = a.

Justin Stevens Euclidean Algorithm (Lecture 3) 3 / 43
Euclid’s Elements

Around the time of 300 BC, a great Greek mathematician rose from
Alexandria by the name of Euclid. He wrote a series of 13 books known as
Elements. Elements is thought by many to be the most successful and
influential textbook ever written. It has been published the second most of
any book, next to the Bible.
The book covers both Euclidean geometry and elementary number theory.
This chapter will focus solely on Book VII, Proposition 1.

Justin Stevens Euclidean Algorithm (Lecture 3) 4 / 43

Euclidean Algorithm I

In a previous example, we saw that when a = 25 and b = 15, then

D(25) = {1, 5, 25}, D(15) = {1, 3, 5, 15}.

Justin Stevens Euclidean Algorithm (Lecture 3) 5 / 43

Euclidean Algorithm I

In a previous example, we saw that when a = 25 and b = 15, then

D(25) = {1, 5, 25}, D(15) = {1, 3, 5, 15}.

Their difference is a − b = 25 − 15 = 10. Note that D(10) = {1, 2, 5, 10}.

Justin Stevens Euclidean Algorithm (Lecture 3) 5 / 43

Euclidean Algorithm I

In a previous example, we saw that when a = 25 and b = 15, then

D(25) = {1, 5, 25}, D(15) = {1, 3, 5, 15}.

Their difference is a − b = 25 − 15 = 10. Note that D(10) = {1, 2, 5, 10}.

D(25) ∩ D(15) = D(15) ∩ D(10) = {1, 5}.

Hence, gcd(25, 15) = gcd(15, 10) = 5.

Justin Stevens Euclidean Algorithm (Lecture 3) 5 / 43

Euclidean Algorithm II

“When two unequal numbers are set out, and the less is
continually subtracted in turn from the greater, if the number
which is left never measures the one before it until a unit is left,
then the original numbers are relatively prime." - Euclid

Theorem. If n = dq + r where 0 ≤ r < d, then gcd(n, d) = gcd(d, r ).

Justin Stevens Euclidean Algorithm (Lecture 3) 6 / 43

Proof of Euclidean Algorithm

Theorem. If n = dq + r where 0 ≤ r < d, then gcd(n, d) = gcd(d, r ).

Proof. I claim that the set of common divisors between n and d is the same
as the set of common divisors between d and r .

Justin Stevens Euclidean Algorithm (Lecture 3) 7 / 43

Proof of Euclidean Algorithm

Theorem. If n = dq + r where 0 ≤ r < d, then gcd(n, d) = gcd(d, r ).

Proof. I claim that the set of common divisors between n and d is the same
as the set of common divisors between d and r .
If l is a common divisor of n and d, then since l | n and l | d, l divides all
linear combinations of n and d. Therefore, l | n − dq = r , meaning that l is
also a common divisor of n and r .

Justin Stevens Euclidean Algorithm (Lecture 3) 7 / 43

Proof of Euclidean Algorithm

Theorem. If n = dq + r where 0 ≤ r < d, then gcd(n, d) = gcd(d, r ).

Proof. I claim that the set of common divisors between n and d is the same
as the set of common divisors between d and r .
If l is a common divisor of n and d, then since l | n and l | d, l divides all
linear combinations of n and d. Therefore, l | n − dq = r , meaning that l is
also a common divisor of n and r .
Conversely, if k is a common divisor of d and r , then since k | d and k | r ,
k is a common divisor of all linear combinations of d and r , therefore,
k | dq + r = n. Hence, k is also a common divisor of n and d.

Justin Stevens Euclidean Algorithm (Lecture 3) 7 / 43

Proof of Euclidean Algorithm

Theorem. If n = dq + r where 0 ≤ r < d, then gcd(n, d) = gcd(d, r ).

Proof. I claim that the set of common divisors between n and d is the same
as the set of common divisors between d and r .
If l is a common divisor of n and d, then since l | n and l | d, l divides all
linear combinations of n and d. Therefore, l | n − dq = r , meaning that l is
also a common divisor of n and r .
Conversely, if k is a common divisor of d and r , then since k | d and k | r ,
k is a common divisor of all linear combinations of d and r , therefore,
k | dq + r = n. Hence, k is also a common divisor of n and d.
We have established that the two sets of common divisors are equivalent,
therefore, the greatest common divisor must be equivalent.
Example. Compute gcd(60, 8) and gcd(490, 110).

Justin Stevens Euclidean Algorithm (Lecture 3) 7 / 43

Practice Euclidean Algorithm

Example. Compute gcd(60, 8) and gcd(490, 110).

We see that 60 = 8 · 7 + 4, hence, gcd(60, 8) = gcd(8, 4) = 4.

Justin Stevens Euclidean Algorithm (Lecture 3) 8 / 43

Practice Euclidean Algorithm

Example. Compute gcd(60, 8) and gcd(490, 110).

We see that 60 = 8 · 7 + 4, hence, gcd(60, 8) = gcd(8, 4) = 4.
For the second problem, we use the division algorithm twice:

490 = 110 · 4 + 50
110 = 50 · 2 + 10
50 = 10 · 5.

Therefore, gcd(490, 110) = gcd(110, 50) = 10. We can verify that

D(490) = {1, 2, 5, 7, 10, 14, 35, 49, 70, 98, 245, 490}
D(110) = {1, 2, 5, 10, 11, 22, 55, 110}
D(50) = {1, 2, 5, 10, 25, 50}.

Hence, D(490) ∩ D(110) = D(110) ∩ D(50) = {1, 2, 5, 10}.

Justin Stevens Euclidean Algorithm (Lecture 3) 8 / 43
Extended Euclidean Algorithm

Theorem. For two natural a, b, a > b, to find gcd(a, b) we use the division
algorithm repeatedly

a = bq1 + r1
b = r1 q2 + r2
r1 = r2 q3 + r3
···
rn−2 = rn−1 qn + rn
rn−1 = rn qn+1 .

Then we have gcd(a, b) = gcd(b, r1 ) = · · · = gcd(rn−1 , rn ) = rn .

Notice the greatest common divisor is the final non-zero remainder.

Justin Stevens Euclidean Algorithm (Lecture 3) 9 / 43

Examples of Euclidean Algorithm

Example 1.
(a) Find gcd(603, 301).
(b) Find gcd(289, 153).
(c) Find gcd(2627, 481).
(d) Find gcd(8774, 1558).

Justin Stevens Euclidean Algorithm (Lecture 3) 10 / 43

Example (a) Solution

Example. Find gcd(603, 301).

Note that
603 = 301 · 2 + 1.
Therefore, by the Euclidean Algorithm, we have

gcd(603, 301) = gcd(1, 301) = 1 .

Justin Stevens Euclidean Algorithm (Lecture 3) 11 / 43

Example (b) Solution

Example. Find gcd(289, 153).

We repeatedly use the division algorithm as follows:

289 = 153 · 1 + 136

153 = 136 · 1 + 17
136 = 17 · 8 + 0.

Therefore gcd(153, 289) = 17 .

Justin Stevens Euclidean Algorithm (Lecture 3) 12 / 43

Example (c) Solution

Example. Find gcd(2627, 481).

We repeatedly use the division algorithm as follows:

2627 = 481 · 5 + 222

481 = 222 · 2 + 37
222 = 37 · 6 + 0

Therefore gcd(2627, 481) = 37.

Notice that we only use remainders in the Euclidean algorithm. For
instance, in the previous example, 2627 ≡ 222 (mod 481). For larger
numbers, we use computers to calculate the remainders.

Justin Stevens Euclidean Algorithm (Lecture 3) 13 / 43

Example (d) Solution

Example. Find gcd(8774, 1558).

With the help of a computer:

8774 ≡ 984 (mod 1558)

1558 ≡ 574 (mod 948)
948 ≡ 410 (mod 574)
574 ≡ 164 (mod 410)
410 ≡ 82 (mod 164)
164 ≡ 0 (mod 82)

Since we desire the last non-zero remainder, gcd(8774, 1558) = 82.

Justin Stevens Euclidean Algorithm (Lecture 3) 14 / 43

More than 2 Numbers

The greatest common divisor of more than 2 numbers is defined similarly.

For example, to calculate gcd(21, 35, 49), we see that

Justin Stevens Euclidean Algorithm (Lecture 3) 15 / 43

More than 2 Numbers

The greatest common divisor of more than 2 numbers is defined similarly.

For example, to calculate gcd(21, 35, 49), we see that
D(21) = {1, 3, 7, 21}, D(35) = {1, 5, 7, 35}, D(49) = {1, 7, 49}.

Justin Stevens Euclidean Algorithm (Lecture 3) 15 / 43

More than 2 Numbers

The greatest common divisor of more than 2 numbers is defined similarly.

For example, to calculate gcd(21, 35, 49), we see that
D(21) = {1, 3, 7, 21}, D(35) = {1, 5, 7, 35}, D(49) = {1, 7, 49}.
Therefore, D(21) ∩ D(35) ∩ D(49) = {1, 7}. Hence, gcd(21, 35, 49) = 7.

Justin Stevens Euclidean Algorithm (Lecture 3) 15 / 43

More than 2 Numbers

The greatest common divisor of more than 2 numbers is defined similarly.

For example, to calculate gcd(21, 35, 49), we see that
D(21) = {1, 3, 7, 21}, D(35) = {1, 5, 7, 35}, D(49) = {1, 7, 49}.
Therefore, D(21) ∩ D(35) ∩ D(49) = {1, 7}. Hence, gcd(21, 35, 49) = 7.
Caution: When calculating gcd(6, 10, 15), we may be tempted to say 2 or 3
since gcd(6, 10) = 2 or gcd(6, 15) = 3. However, 2 - 15 and 3 - 10. Indeed,
D(6) = {1, 2, 3, 6}, D(10) = {1, 2, 5, 10}, D(15) = {1, 3, 5, 15}.
The only common divisor of all three numbers is 1.

Justin Stevens Euclidean Algorithm (Lecture 3) 15 / 43

More than 2 Numbers

The greatest common divisor of more than 2 numbers is defined similarly.

For example, to calculate gcd(21, 35, 49), we see that
D(21) = {1, 3, 7, 21}, D(35) = {1, 5, 7, 35}, D(49) = {1, 7, 49}.
Therefore, D(21) ∩ D(35) ∩ D(49) = {1, 7}. Hence, gcd(21, 35, 49) = 7.
Caution: When calculating gcd(6, 10, 15), we may be tempted to say 2 or 3
since gcd(6, 10) = 2 or gcd(6, 15) = 3. However, 2 - 15 and 3 - 10. Indeed,
D(6) = {1, 2, 3, 6}, D(10) = {1, 2, 5, 10}, D(15) = {1, 3, 5, 15}.
The only common divisor of all three numbers is 1.
Using our set notation, we can show the following theorem:
Theorem. For three positive integers a, b, c,
gcd(a, b, c) = gcd(gcd(a, b), c) = gcd(a, gcd(b, c)) = gcd(gcd(a, c), b).

Justin Stevens Euclidean Algorithm (Lecture 3) 15 / 43

Euclidean Algorithm Challenges

Example 2. Compute gcd(364 − 1, 340 − 1) and gcd(364 − 1, 320 − 1).

Example 3. Compute gcd(2002 + 2, 20022 + 2, 20023 + 2, · · · ). ∗

∗
Source: 2002 HMMT
Justin Stevens Euclidean Algorithm (Lecture 3) 16 / 43
Exponent GCD

Example. Compute gcd(364 − 1, 340 − 1).

We reduce the exponents using the Euclidean algorithm:
364 − 1 = 340 − 1 324 + 324 − 1 =⇒ gcd(364 − 1, 340 − 1) = gcd(340 − 1, 324 − 1)

340 − 1 = 324 − 1 316 + 316 − 1 =⇒ gcd(324 − 1, 340 − 1) = gcd(324 − 1, 316 − 1)

324 − 1 = 316 − 1 38 + 38 − 1 =⇒ gcd(324 − 1, 316 − 1) = gcd(316 − 1, 38 − 1)

316 − 1 = 38 − 1 38 + 1 =⇒ gcd(38 − 1, 316 − 1) = 38 − 1 .

Note the parallel between the above equations and computing gcd(64, 40):

gcd(64, 40) = gcd(40, 24) = gcd(24, 16) = gcd(16, 8) = 8.

Justin Stevens Euclidean Algorithm (Lecture 3) 17 / 43

Exponent GCD II

Example. Compute gcd(364 − 1, 320 − 1).

We reduce the exponents using the Euclidean algorithm:
364 − 1 = 320 − 1 344 + 344 − 1 =⇒ gcd(364 − 1, 320 − 1) = gcd(344 − 1, 320 − 1)

344 − 1 = 320 − 1 324 + 324 − 1 =⇒ gcd(344 − 1, 320 − 1) = gcd(324 − 1, 320 − 1)

324 − 1 = 320 − 1 34 + 34 − 1 =⇒ gcd(324 − 1, 320 − 1) = gcd(320 − 1, 34 − 1)

5
Note that 34 − 1 | 34 − 1, hence gcd(320 − 1, 34 − 1) = 34 − 1.
Notice the parallel with the division algorithm:

64 = 20 · 3 + 4
20 = 4 · 5.

Therefore, gcd(64, 20) = gcd(4, 20) = 4.

Justin Stevens Euclidean Algorithm (Lecture 3) 18 / 43

Generalized Exponent GCD

Theorem. For natural numbers, gcd(am − 1, an − 1) = agcd(m,n) − 1.

Justin Stevens Euclidean Algorithm (Lecture 3) 19 / 43

2002 GCD Sequence

Example. Compute gcd(2002 + 2, 20022 + 2, 20023 + 2, · · · ).

We compute the gcd of the first two terms. By difference of squares,

Justin Stevens Euclidean Algorithm (Lecture 3) 20 / 43

2002 GCD Sequence

Example. Compute gcd(2002 + 2, 20022 + 2, 20023 + 2, · · · ).

We compute the gcd of the first two terms. By difference of squares,

20022 − 4 = (2002 + 2) (2002 − 2) =⇒ 20022 + 2 = (2002 + 2) (2002 − 2) + 6.

Justin Stevens Euclidean Algorithm (Lecture 3) 20 / 43

2002 GCD Sequence

Example. Compute gcd(2002 + 2, 20022 + 2, 20023 + 2, · · · ).

We compute the gcd of the first two terms. By difference of squares,

20022 − 4 = (2002 + 2) (2002 − 2) =⇒ 20022 + 2 = (2002 + 2) (2002 − 2) + 6.

Hence, by the Euclidean Algorithm,

gcd(2002 + 2, 20022 + 2) = gcd(2002 + 2, 6) = gcd(2004, 6) = 6.

Justin Stevens Euclidean Algorithm (Lecture 3) 20 / 43

2002 GCD Sequence

Example. Compute gcd(2002 + 2, 20022 + 2, 20023 + 2, · · · ).

We compute the gcd of the first two terms. By difference of squares,

20022 − 4 = (2002 + 2) (2002 − 2) =⇒ 20022 + 2 = (2002 + 2) (2002 − 2) + 6.

Hence, by the Euclidean Algorithm,

gcd(2002 + 2, 20022 + 2) = gcd(2002 + 2, 6) = gcd(2004, 6) = 6.

Therefore, the greatest common divisor of the sequence can be at most 6.

Justin Stevens Euclidean Algorithm (Lecture 3) 20 / 43

2002 GCD Sequence

Example. Compute gcd(2002 + 2, 20022 + 2, 20023 + 2, · · · ).

We compute the gcd of the first two terms. By difference of squares,

20022 − 4 = (2002 + 2) (2002 − 2) =⇒ 20022 + 2 = (2002 + 2) (2002 − 2) + 6.

Hence, by the Euclidean Algorithm,

gcd(2002 + 2, 20022 + 2) = gcd(2002 + 2, 6) = gcd(2004, 6) = 6.

Therefore, the greatest common divisor of the sequence can be at most 6.

Every term in the sequence is even. Furthermore, since 2002 ≡ 1 (mod 3),

2002k + 2 ≡ 1k + 2 ≡ 1 + 2 ≡ 0 (mod 3).

Justin Stevens Euclidean Algorithm (Lecture 3) 20 / 43

2002 GCD Sequence

Example. Compute gcd(2002 + 2, 20022 + 2, 20023 + 2, · · · ).

We compute the gcd of the first two terms. By difference of squares,

20022 − 4 = (2002 + 2) (2002 − 2) =⇒ 20022 + 2 = (2002 + 2) (2002 − 2) + 6.

Hence, by the Euclidean Algorithm,

gcd(2002 + 2, 20022 + 2) = gcd(2002 + 2, 6) = gcd(2004, 6) = 6.

Therefore, the greatest common divisor of the sequence can be at most 6.

Every term in the sequence is even. Furthermore, since 2002 ≡ 1 (mod 3),

2002k + 2 ≡ 1k + 2 ≡ 1 + 2 ≡ 0 (mod 3).

Hence, every term in the sequence is divisible by both 2 and 3, and

therefore 6. The greatest common divisor of the sequence is 6 .
Justin Stevens Euclidean Algorithm (Lecture 3) 20 / 43
Outline

1 Euclidean Algorithm

2 Bezout’s Identity
Euclidean Algorithm Recap
Proof
Bezout’s Identity Puzzles

3 Linear Congruences

Justin Stevens Euclidean Algorithm (Lecture 3) 21 / 43

Euclidean Algorithm Recap

Theorem. For two natural a, b, a > b, to find gcd(a, b) we use the division
algorithm repeatedly

a = bq1 + r1
b = r1 q2 + r2
r1 = r2 q3 + r3
···
rn−2 = rn−1 qn + rn
rn−1 = rn qn+1 .

Then we have gcd(a, b) = gcd(b, r1 ) = · · · = gcd(rn−1 , rn ) = rn .

Notice the greatest common divisor is the final non-zero remainder.

Justin Stevens Euclidean Algorithm (Lecture 3) 22 / 43

Linear Combinations

Definition. A linear combination of two integers n1 and n2 is of the form

n1 x1 + n2 x2 where x1 and x2 are integers.

Theorem. If d | n1 and d | n2 , then d | n1 x1 + n2 x2 for integers x1 and x2 .

Example 4. Express 5 as a linear combination of 45 and 65.

Example 5. Express 10 as a linear combination of 110 and 380.

Justin Stevens Euclidean Algorithm (Lecture 3) 23 / 43

Express 5 as Linear Combination

Example. Express 5 as a linear combination of 45 and 65.

Notice gcd(65, 45) = 5. Using the Euclidean Algorithm,

65 = 45 · 1 + 20
45 = 20 · 2 + 5
20 = 5 · 4

Running the process in reverse:

5 = 45 − 20 · 2
= 45 − (65 − 45 · 1)2
= 45 · 3 − 65 · 2.
Express 5 as Linear Combination

Example. Express 5 as a linear combination of 45 and 65.

Notice gcd(65, 45) = 5. Using the Euclidean Algorithm,

65 = 45 · 1 + 20
45 = 20 · 2 + 5
20 = 5 · 4

Running the process in reverse:

5 = 45 − 20 · 2
= 45 − (65 − 45 · 1)2
= 45 · 3 − 65 · 2.

Justin Stevens Euclidean Algorithm (Lecture 3) 24 / 43

Express 10 as Linear Combination

Example. Express 10 as a linear combination of 110 and 380.

Solution. We again, use the Euclidean Algorithm to arrive at

380 = 110 · 3 + 50
110 = 50 · 2 + 10
50 = 10 · 5

Using the Euclidean Algorithm in reverse:

10 = 110 − 50 · 2
= 110 − (380 − 110 · 3) · 2
= 7 · 110 − 2 · 380.

Justin Stevens Euclidean Algorithm (Lecture 3) 25 / 43

Bezout’s Identity

Theorem. For a, b natural, there exist x , y ∈ Z with ax + by = gcd(a, b).

Proof 1: Run the Euclidean Algorithm backwards.

Justin Stevens Euclidean Algorithm (Lecture 3) 26 / 43

Bezout’s Identity

Theorem. For a, b natural, there exist x , y ∈ Z with ax + by = gcd(a, b).

Proof 1: Run the Euclidean Algorithm backwards.
Proof 2: Consider the set S = {ax + by > 0 with x , y integers}.
For instance, if a = 4 and b = 6, then which values would be in the set?

(i) 10 (ii) 7 (iii) 2 (iv) −8

Justin Stevens Euclidean Algorithm (Lecture 3) 26 / 43

Bezout’s Identity

Theorem. For a, b natural, there exist x , y ∈ Z with ax + by = gcd(a, b).

Proof 1: Run the Euclidean Algorithm backwards.
Proof 2: Consider the set S = {ax + by > 0 with x , y integers}.
For instance, if a = 4 and b = 6, then which values would be in the set?

(i) 10 (ii) 7 (iii) 2 (iv) −8

The answer is (i) and (iii) since 4 · 1 + 6 · 1 = 10 and 4 · (−1) + 6 · 1 = 2.

Justin Stevens Euclidean Algorithm (Lecture 3) 26 / 43

Bezout’s Identity

Theorem. For a, b natural, there exist x , y ∈ Z with ax + by = gcd(a, b).

Proof 1: Run the Euclidean Algorithm backwards.
Proof 2: Consider the set S = {ax + by > 0 with x , y integers}.
For instance, if a = 4 and b = 6, then which values would be in the set?

(i) 10 (ii) 7 (iii) 2 (iv) −8

The answer is (i) and (iii) since 4 · 1 + 6 · 1 = 10 and 4 · (−1) + 6 · 1 = 2.

The well-ordering principle states that every non-empty subset of positive
integers has a least element. Let this minimum be d = min(S).

Justin Stevens Euclidean Algorithm (Lecture 3) 26 / 43

Bezout’s Identity

Theorem. For a, b natural, there exist x , y ∈ Z with ax + by = gcd(a, b).

Proof 1: Run the Euclidean Algorithm backwards.
Proof 2: Consider the set S = {ax + by > 0 with x , y integers}.
For instance, if a = 4 and b = 6, then which values would be in the set?

(i) 10 (ii) 7 (iii) 2 (iv) −8

The answer is (i) and (iii) since 4 · 1 + 6 · 1 = 10 and 4 · (−1) + 6 · 1 = 2.

The well-ordering principle states that every non-empty subset of positive
integers has a least element. Let this minimum be d = min(S).
Since d is a member of the set, there exists integers x1 and y1 such that
d = ax1 + by1 . Now, we must prove d = gcd(a, b). How can we do this?

Justin Stevens Euclidean Algorithm (Lecture 3) 26 / 43

Bezout’s Identity Proof I

Theorem. For a, b natural, there exist x , y ∈ Z with ax + by = gcd(a, b).

?
S = {ax + by > 0, x , y ∈ Z} and d = min(S) = ax1 + by1 = gcd(a, b).

Justin Stevens Euclidean Algorithm (Lecture 3) 27 / 43

Bezout’s Identity Proof I

Theorem. For a, b natural, there exist x , y ∈ Z with ax + by = gcd(a, b).

?
S = {ax + by > 0, x , y ∈ Z} and d = min(S) = ax1 + by1 = gcd(a, b).
To begin, we show that d is a common divisor a and b. Assume for the sake
of contradiction that d doesn’t divide a. By the division algorithm, we have

Justin Stevens Euclidean Algorithm (Lecture 3) 27 / 43

Bezout’s Identity Proof I

Theorem. For a, b natural, there exist x , y ∈ Z with ax + by = gcd(a, b).

?
S = {ax + by > 0, x , y ∈ Z} and d = min(S) = ax1 + by1 = gcd(a, b).
To begin, we show that d is a common divisor a and b. Assume for the sake
of contradiction that d doesn’t divide a. By the division algorithm, we have

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

We substitute d = ax1 + by1 into this equation:

a = dq + r = (ax1 + by1 ) q + r =⇒ r = a (1 − qx1 ) + b (−qy1 ) .

Justin Stevens Euclidean Algorithm (Lecture 3) 27 / 43

Bezout’s Identity Proof I

Theorem. For a, b natural, there exist x , y ∈ Z with ax + by = gcd(a, b).

?
S = {ax + by > 0, x , y ∈ Z} and d = min(S) = ax1 + by1 = gcd(a, b).
To begin, we show that d is a common divisor a and b. Assume for the sake
of contradiction that d doesn’t divide a. By the division algorithm, we have

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

We substitute d = ax1 + by1 into this equation:

a = dq + r = (ax1 + by1 ) q + r =⇒ r = a (1 − qx1 ) + b (−qy1 ) .

If r is positive, then r ∈ S since it satisfies the two conditions, however this

contradicts the minimality of d. Therefore, we must have r = 0 and d | a.
We can similarly show d | b. Hence, d is a common divisor of a and b.

Justin Stevens Euclidean Algorithm (Lecture 3) 27 / 43

Bezout’s Identity Proof II

Theorem. For a, b natural, there exist x , y ∈ Z with ax + by = gcd(a, b).

?
S = {ax + by > 0, x , y ∈ Z} and d = min(S) = ax1 + by1 = gcd(a, b).
It is now left to show that d is the greatest common divisor of a and b.

Justin Stevens Euclidean Algorithm (Lecture 3) 28 / 43

Bezout’s Identity Proof II

Theorem. For a, b natural, there exist x , y ∈ Z with ax + by = gcd(a, b).

?
S = {ax + by > 0, x , y ∈ Z} and d = min(S) = ax1 + by1 = gcd(a, b).
It is now left to show that d is the greatest common divisor of a and b.
Let d1 be another common divisor of a and b. By the linear combination
theorem, d1 divides all linear combinations of a and b. Specifically,

d1 | ax1 + by1 = d.

Therefore, every common divisor of a and b divides d, hence, d = gcd(a, b).

Corollary. If c | a and c | b, then c | gcd(a, b).

Justin Stevens Euclidean Algorithm (Lecture 3) 28 / 43

Bezout’s Identity Proof II

Theorem. For a, b natural, there exist x , y ∈ Z with ax + by = gcd(a, b).

?
S = {ax + by > 0, x , y ∈ Z} and d = min(S) = ax1 + by1 = gcd(a, b).
It is now left to show that d is the greatest common divisor of a and b.
Let d1 be another common divisor of a and b. By the linear combination
theorem, d1 divides all linear combinations of a and b. Specifically,

d1 | ax1 + by1 = d.

Therefore, every common divisor of a and b divides d, hence, d = gcd(a, b).

Corollary. If c | a and c | b, then c | gcd(a, b).

Example. Express 3 as a linear combination of 1011 and 11, 202.

Justin Stevens Euclidean Algorithm (Lecture 3) 28 / 43

Linear Combination of 1011 and 11, 202.

Example. Express 3 as a linear combination of 1011 and 11, 202.

Solution. We use the Euclidean Algorithm to arrive at
11202 = 1011 · 11 + 81
1011 = 81 · 12 + 39
81 = 39 · 2 + 3
39 = 3 · 13
Using the Euclidean Algorithm in reverse
3 = 81 − 39 · 2
= 81 − (1011 − 81 · 12) · 2
= 81 · 25 − 1011 · 2
= (11202 − 1011 · 11) · 25 − 1011 · 2
= 11202 · 25 − 1011 · 277.
Linear Combination of 1011 and 11, 202.

Example. Express 3 as a linear combination of 1011 and 11, 202.

Solution. We use the Euclidean Algorithm to arrive at
11202 = 1011 · 11 + 81
1011 = 81 · 12 + 39
81 = 39 · 2 + 3
39 = 3 · 13
Using the Euclidean Algorithm in reverse
3 = 81 − 39 · 2
= 81 − (1011 − 81 · 12) · 2
= 81 · 25 − 1011 · 2
= (11202 − 1011 · 11) · 25 − 1011 · 2
= 11202 · 25 − 1011 · 277.
Justin Stevens Euclidean Algorithm (Lecture 3) 29 / 43
Bezout’s Identity Puzzles

Example 6. Suppose you have a 5 litre jug and a 7 litre jug. We can
perform any of the following moves:
Fill a jug completely with water.
Transfer water from one jug to another, stopping if the other jug is
filled.
Empty a jug of water.
The goal is to end up with one jug having exactly 1 litre of water. How do
we do this?

Justin Stevens Euclidean Algorithm (Lecture 3) 30 / 43

Jug Puzzle

Note that at every stage, the jugs will contain a linear combination of 5 and
7 litres of water. We find that 1 = 5 · 3 + 7 · (−2), therefore, we want to fill
the jug with 5 litres 3 times, and empty the one with 7 litres twice.

Justin Stevens Euclidean Algorithm (Lecture 3) 31 / 43

Jug Puzzle

Note that at every stage, the jugs will contain a linear combination of 5 and
7 litres of water. We find that 1 = 5 · 3 + 7 · (−2), therefore, we want to fill
the jug with 5 litres 3 times, and empty the one with 7 litres twice.
In order to keep track of how much water we have in each step, we use an
ordered pair (a, b), where a is the amount in the 5 litre jug and b is the
amount in the 7 litre jug:
Fill Transfer Transfer Transfer Empty
(0, 0) → (5, 0) → (0, 5) → (5, 5) → (3, 7) → (3, 0)
Transfer Fill Transfer Empty
(3, 0) → (0, 3) → (5, 3) → (1, 7) → (1, 0).
Jug Puzzle

Note that at every stage, the jugs will contain a linear combination of 5 and
7 litres of water. We find that 1 = 5 · 3 + 7 · (−2), therefore, we want to fill
the jug with 5 litres 3 times, and empty the one with 7 litres twice.
In order to keep track of how much water we have in each step, we use an
ordered pair (a, b), where a is the amount in the 5 litre jug and b is the
amount in the 7 litre jug:
Fill Transfer Transfer Transfer Empty
(0, 0) → (5, 0) → (0, 5) → (5, 5) → (3, 7) → (3, 0)
Transfer Fill Transfer Empty
(3, 0) → (0, 3) → (5, 3) → (1, 7) → (1, 0).

Justin Stevens Euclidean Algorithm (Lecture 3) 31 / 43

Proving Important Theorems

Example 7. Prove that gcd(am − 1, an − 1) = agcd(m,n) − 1.

Example 8. Prove that if a | bc and gcd(a, b) = 1, then a | c.

Justin Stevens Euclidean Algorithm (Lecture 3) 32 / 43

? Exponent GCD Theorem

Example. Prove that gcd(am − 1, an − 1) = agcd(m,n) − 1.

Let d = gcd(am − 1, an − 1). We show d | agcd(m,n) − 1 and agcd(m,n) − 1 | d.

Justin Stevens Euclidean Algorithm (Lecture 3) 33 / 43

? Exponent GCD Theorem

Example. Prove that gcd(am − 1, an − 1) = agcd(m,n) − 1.

Let d = gcd(am − 1, an − 1). We show d | agcd(m,n) − 1 and agcd(m,n) − 1 | d.
Since d | am − 1 =⇒ am ≡ 1 (mod d). Similarly, an ≡ 1 (mod d).

Justin Stevens Euclidean Algorithm (Lecture 3) 33 / 43

? Exponent GCD Theorem

Example. Prove that gcd(am − 1, an − 1) = agcd(m,n) − 1.

Let d = gcd(am − 1, an − 1). We show d | agcd(m,n) − 1 and agcd(m,n) − 1 | d.
Since d | am − 1 =⇒ am ≡ 1 (mod d). Similarly, an ≡ 1 (mod d).
By Bezout’s identity, let gcd(m, n) = mx + ny . Then,
agcd(m,n) ≡ amx +ny ≡ amx any ≡ 1 (mod d).
Therefore, d | agcd(m,n) − 1. We now show that agcd(m,n) − 1 | d.
Since gcd(m, n) | m and gcd(m, n) | n, we have
agcd(m,n) − 1 | am − 1
(
=⇒ agcd(m,n) − 1 | gcd(am − 1, an − 1).
agcd(m,n) − 1 | an − 1

From d | agcd(m,n) − 1 and agcd(m,n) − 1 | d, we have

d = gcd(am − 1, an − 1) = agcd(m,n) − 1.
Justin Stevens Euclidean Algorithm (Lecture 3) 33 / 43
Euclid’s Lemma

Example. If a | bc and gcd(a, b) = 1, prove that a | c.

Proof. By Bezout’s identity, gcd(a, b) = 1 implies that there exist x , y such
that ax + by = 1. Next, multiply this equation by c to arrive at

c(ax ) + c(by ) = c.

Finally, since a | c(ax ) and a | bc (given), we have a | ac(x ) + bc(y ) = c.

Justin Stevens Euclidean Algorithm (Lecture 3) 34 / 43

Outline

1 Euclidean Algorithm

2 Bezout’s Identity

3 Linear Congruences
Diophantine Equations
Modular Inverses

Justin Stevens Euclidean Algorithm (Lecture 3) 35 / 43

Linear Diophantine Equation

Example 9. How many ways are there to make $3.00 using dimes and
quarters?
Example 10. Find all pairs of integers x , y such that 5x + 7y = 1.

Justin Stevens Euclidean Algorithm (Lecture 3) 36 / 43

Parametizing

Example. How many ways are there to make $3.00 using dimes and quarters?
Let the number of dimes be d and quarters be q. Then,

10d + 25q = 300 =⇒ 2d + 5q = 60.

Note that the number of dimes must be divisible by 5. Hence,

d = 0, 5, 10, 15, 20, 25, 30 gives the solutions

(d, q) = (0, 12), (5, 10), (10, 8), (15, 6), (20, 4), (25, 2), (30, 0).

There are a total of 7 solutions.

Justin Stevens Euclidean Algorithm (Lecture 3) 37 / 43

Pairs of Integers

Example. Find all pairs of integers x , y such that 5x + 7y = 1.

We see that (x , y ) = (3, −2) is a solution. All such solutions are given by
(x , y ) = (3 + 5t, −2 − 7t).

Justin Stevens Euclidean Algorithm (Lecture 3) 38 / 43

Division in Modulos

Consider the multiplication table below for mod 7:

× 0 1 2 3 4 5 6
0 0 0 0 0 0 0 0
1 0 1 2 3 4 5 6
2 0 2 4 6 1 3 5
3 0 3 6 2 5 1 4
4 0 4 1 5 2 6 3
5 0 5 3 1 6 4 2
6 0 6 5 4 3 2 1

Find values of x and y such that 3x ≡ 1 (mod 7) and 2y ≡ 1 (mod 7).

Justin Stevens Euclidean Algorithm (Lecture 3) 39 / 43

Division in Modulos

Consider the multiplication table below for mod 7:

× 0 1 2 3 4 5 6
0 0 0 0 0 0 0 0
1 0 1 2 3 4 5 6
2 0 2 4 6 1 3 5
3 0 3 6 2 5 1 4
4 0 4 1 5 2 6 3
5 0 5 3 1 6 4 2
6 0 6 5 4 3 2 1

Find values of x and y such that 3x ≡ 1 (mod 7) and 2y ≡ 1 (mod 7).

We see that x ≡ 5 (mod 7) and y ≡ 4 (mod 7). These are called inverses.
Definition. The inverse of a mod m is the value x with ax ≡ 1 (mod m).
This is denoted a−1 (mod m) and is analogous to division.
Justin Stevens Euclidean Algorithm (Lecture 3) 39 / 43
Inverses

Example 11. Solve the congruences 8y ≡ 1 mod 39 and 9z ≡ 1 mod 41.

Example 12. Are there values of x such that 2x ≡ 1 (mod 6)?
Example 13. Solve the congruence 13x ≡ 1 (mod 71).

Justin Stevens Euclidean Algorithm (Lecture 3) 40 / 43

 Example. Solve the congruences 8y ≡ 1 (mod 39) and 9z ≡ 1 (mod 41).
We see that 8 · 5 = 40 ≡ 1 (mod 39) =⇒ y ≡ 5 (mod 39).

Justin Stevens Euclidean Algorithm (Lecture 3) 41 / 43

 Example. Solve the congruences 8y ≡ 1 (mod 39) and 9z ≡ 1 (mod 41).
We see that 8 · 5 = 40 ≡ 1 (mod 39) =⇒ y ≡ 5 (mod 39).
For the second problem,

9 · 9 = 81 ≡ −1 (mod 41) =⇒ z ≡ −9 ≡ 32 (mod 41).

Justin Stevens Euclidean Algorithm (Lecture 3) 41 / 43

When Division Fails

Example. Are there values of x such that 2x ≡ 1 (mod 6)?

× 0 1 2 3 4 5
0 0 0 0 0 0 0
1 0 1 2 3 4 5
2 0 2 4 0 2 4
3 0 3 0 3 0 3
4 0 4 2 0 4 2
5 0 5 4 3 2 1

Table 1: Multiplication Table Mod 6.

We see that only 2x ≡ 0, 2, 4 (mod 6). Therefore, the answer is no.

Justin Stevens Euclidean Algorithm (Lecture 3) 42 / 43

Mod 71 Congruence

Example. Solve the congruence 13x ≡ 1 (mod 71).

Using the Euclidean algorithm

71 = 13 · 5 + 6
13 = 6 · 2 + 1
In reverse:
1 = 13 − 6 · 2
= 13 − (71 − 13 · 5) · 2
= 13 · 11 − 71 · 2.

Hence, x ≡ 11 (mod 71).

Justin Stevens Euclidean Algorithm (Lecture 3) 43 / 43