4.2: Euclidean algorithm and Bezout's algorithm
 Page ID
 7534
\( \newcommand{\vecs}[1]{\overset { \scriptstyle \rightharpoonup} {\mathbf{#1}} } \)
\( \newcommand{\vecd}[1]{\overset{\!\!\rightharpoonup}{\vphantom{a}\smash {#1}}} \)
Definition: Euclidean Algorithm
The Euclidean Algorithm is an efficient way of computing the GCD of two integers. It was discovered by the Greek mathematician Euclid, who determined that if n goes into x and y, it must go into xy. Therefore, we can subtract the smaller integer from the larger integer until the remainder is less than the smaller integer. We continue using this process until the remainder is 0, thus leaving us with our GCD.
Example \(\PageIndex{1}\)
Find the GCD of 30 and 650 using the Euclidean Algorithm.
650 / 30 = 21 R 20. Now take the remainder and divide that into the original divisor.
30 / 20 = 1 R 10. Now take the remainder and divide that into the previous divisor.
20 / 10 = 2 R 0. Since we have a remainder of 0, we know that the divisor is our GCD.
Therefore, the GCD of 30 and 650 is 10.
Example \(\PageIndex{2}\):
Find \(\gcd(2420, 230)\).
Note: Work from right to left to follow the steps shown in the image below.
Hence, \(\gcd(2420,230) =10\).
Example \(\PageIndex{3}\):
Find \(\gcd(3915, 825)\).
Note: Work from right to left to follow the steps shown in the image below.
Hence, \(\gcd(3915, 825 )=15\).
Example \(\PageIndex{4}\): Geometric GCD
We want to tile an a ft by b ft (a, b \(\in \mathbb{Z}\)) floor with identical square tiles. What is the largest square tile we can use? \(\gcd(a, b)\).
Consider the following example where \(a=100\) and \(b=44\).
The largest square tile we can use to completely tile a 100 ft by 44 ft floor is a \(4\) ft by \(4\) ft tile.
BEZOUT'S IDENTITY
For integers a and b, let d be the greatest common divisor, d = GCD (a, b). Then there exists integers x and y such that ax+by=d. Any integer that is of the form ax+by, is a multiple of d.
Note
This condition will be a necessary and sufficient condition in the case of \(d=1\). We will prof this result in section 4.4 Relatively Prime numbers.
Bezout Algorithm
Use the Euclidean Algorithm to determine the GCD, then work backwards using substitution. WHEN DOING SUBSTITUTION BE VERY CAREFUL OF THE POSITIVES AND NEGATIVES.
Example \(\PageIndex{5}\)
Find the Bezout Identity for a=34 and b=19.
Solution
First, find the gcd(34, 19).
34 = 19(1) + 15.
19 = 15(1) + 4.
15 = 4(3) + 3.
4 = 3(1) + 1.
3 = 1(3) + 0.
Thus, the gcd(34, 19) = 1.
Next, work backwards to find x and y.
1 = 4  1(3).
= 4  1(15  4(3)) = 4(4)  1(15).
= 4(19  15(1)) 1(15) = 4(19)  5(15).
= 4(19)  5(34  19(1)) = 9(19)  5(34).
Thus Bezout's Identity for a=34 and b=19 is 1 = 34(5) + 19(9).
Example \(\PageIndex{6}\): Tabular Method, yielding GCD and Bezout's Coefficients
Find Bezout's Identity for a = 237 and b = 13.
Solution:
(1) Set up the initial table. This step is always the same regardless of which numbers you are trying to find the GCD of. 
Iteration

Remainder

Quotient

Coefficients of Bezout’s 

i 
r 
q 
s 
t 

0 


1 
0 

1 


0 
1 

2 




(2) Insert numerator into R_{0}C_{1} (3) Insert denominator into R_{1}C_{1} (4) Integer divide R_{0}C_{1} by R_{1}C_{1} and place result into R_{1}C_{2} (5) Place remainder from (4) into R_{2}C_{1}
Table at right shows completed steps 1  5 of GCD(237,13). Note: 237/13 = 18 R 3 
i 
r 
q 
s 
t 
0 
237 

1 
0 

1 
13 
18 
0 
1 

2 
3 



(6) add new line to table, increment i. (7) R_{i}C_{2} is integer division R_{i1}C_{1}/R_{i}C_{1} (8) Place remainder from (7) into R_{i+1}C_{1} Note: 13/3 = 4 R 1 (9) R_{i}C_{3} is R_{i2}C_{3}  (R_{i1}C_{2} * R_{ i1}C_{3}) (10) R_{i}C_{4} is R_{i2}C_{4}  (R_{i1}C_{2} * R_{ i1}C_{4}) 
i 
r 
q 
s 
t 
0 
237 

1 
0 

1 
13 
18 
0 
1 

2 
3 
4 
1 
18 

3 
1 



Repeat steps 6  10 until R_{i}C_{1} = 0 Completed table for GCD(237,13) at right.
GCD (237,13) = 1 = first non zero remainder. Write answer as: GCD(237,13) = 1 = 4(237) + 73(13)
Where 4=s and 73=t. The GCD = 1 indicates that the numbers are relatively prime. 
Iteration 
Remainder 
Quotient 
Coefficients of Bezout’s 

i 
r 
q 
s 
t 

0 
237 

1 
0 

1 
13 
18 
0 
1 

2 
3 
4 
1 
18 

3 
1 
3 
4 
73 

4 
0 



Thus, the Bezout's Identity for a=237 and b=13 is 1 = 4(237) + 73(13).
Example \(\PageIndex{7}\):
Find the GCD of 149553 and 177741:
First, use the Euclidean Algorithm to determine the GCD.
177741/149553 = 1 R 28188
149553/28188 = 5 R 8613
28188/8613 = 3 R 2349
8613/2349 = 3 R 1566
2349/1566 = 1 R 783
1566/783 = 2 R 0
Because we have a remainder of 0 we have now determined that 783 is the GCD.
Next, find \(x, y \in \mathbb{Z}\) such that 783=149553(x)+177741(y).
Using the answers from the division in Euclidean Algorithm, work backwards.
783= 2349+1566(1).
1566=8613+2349(3).
2349=28188+8613(3).
8613=149553+28188(5).
28188=177741+149553(1).
Now substitute in,
783 =2349+1566(1).
=2349 +(8613 + 2349(3))(1)
=2349 +(8613(1)+2349(3)
=2349(4)+8613(1)
=(28188+8613(3))(4)+8613(1)
=28188(4)+8613(13)
=28188(4)+(149553+28188(5))(13)
=28188(69)+149553(13)
=(177741+149553(1))(69)+149553(13)
=177741(69)+149553(82)
Thus, Bezout's Identity is 783=177741(69)+149553(82).
Example \(\PageIndex{8}\):
Let \(a,b \in \mathbb{Z}\). If \(ax+by=12\) for some integers \(x\) and \(y\). Then what are the possible values for \(\gcd(a, b)\). For these values find possible values for \(a, b, x\) and \(y\).
 Answer:

a b x y d=gcd(a,b)