Scribd
Upload
8 views13 pages

Euclidean Algorithm for GCD Calculation

The document explains the Euclidean Algorithm, a method for finding the Greatest Common Divisor (GCD) of two integers through a series of steps involving division and remainders. It provides examples of calculating GCDs for pairs of integers and introduces the Extended Euclidean Algorithm, which finds integers x and y such that ax + by = gcd(a, b). Additional examples are given for practice with finding GCDs and corresponding x and y values.

Uploaded by

Maryam Perez
Copyright
© All Rights Reserved
We take content rights seriously. If you suspect this is your content, claim it here.
Available Formats
Download as PPTX, PDF, TXT or read online on Scribd
8 views13 pages

Euclidean Algorithm for GCD Calculation

The document explains the Euclidean Algorithm, a method for finding the Greatest Common Divisor (GCD) of two integers through a series of steps involving division and remainders. It provides examples of calculating GCDs for pairs of integers and introduces the Extended Euclidean Algorithm, which finds integers x and y such that ax + by = gcd(a, b). Additional examples are given for practice with finding GCDs and corresponding x and y values.

Uploaded by

Maryam Perez
Copyright
© All Rights Reserved
We take content rights seriously. If you suspect this is your content, claim it here.
Available Formats
Download as PPTX, PDF, TXT or read online on Scribd

Euclidean

Algorithm
Algorith
m Set of steps that are followed
in order to solve a mathematical
problem or to complete a
computer process.
• Recall that the Greatest Common Divisor
(GCD) of two integers A and B is the largest
integer that divides both A and B.
• The Euclidean Algorithm is a technique for
quickly finding the GCD of two integers.
Euclidean
Algorithm
𝑎=𝑏∙𝑞+𝑟
Express it in the form:

a is the bigger number


b is the smaller number
q is the quotient
r is the remainder
Euclidean
Algorithm
𝑎=𝑏∙𝑞+𝑟
Express it in the form:

If you reach a zero remainder


You have to look up on the previous
line
To the last non zero remainder that
you got and that is the GCD of the
two number
Example : GCD
(1425, 480)

𝑎=𝑏∙𝑞+𝑟
Express it in the form:

GCD (1425, 480) = 15


Example : GCD
(1701,3768)
𝑎=𝑏∙𝑞+𝑟
Express it in the form:

GCD (1701,3768) = 3
Other Examples :
 GCD( 56,15)
 GCD (180,378)
 GCD (7544,115)
Extended
Euclidean
Algorithm
Given two whole numbers look at all the possible numbers obtained by adding a multiple of to
a multiple of In other words, consider all numbers obtained from the formula when all
possible integers for are substituted. For example, take and This gives the expression Some
of the values are given in the following table:
x= -3 x = -2 x = -1 x=0 x=1 x=2 x=3
y = -3 -216 -174 -132 -90 -48 -6 36
y = -2 -186 -144 -102 -60 -18 24 66
y= -1 -156 -114 -72 -30 12 54 96
y=0 -126 -84 -42 0 42 84 126
y=1 -96 -54 -12 30 72 114 156
y=2 -66 -24 18 60 102 144 186
y=3 -36 6 48 90 132 174 216
Observe that every entry in the table is divisible by 6. This is not surprising since both 42 and 30 are divisible by 6, so every
number of the form is a multiple of 6. Take note also that More generally, it is clear that every number of the form is
divisible by since both are divisible by
The smallest positive value of is equal to
always has solutions.
Example: Find x and y in GCD(22,60)
22 𝑥+60 𝑦= 2
First : use the Euclidean
Algorithm Rewrite in the form:
60 = 2(22)+16 (1)
22=1(16)+6 (2) 16 =60+22(-2) (1)
16=2(6)+4 (3) 6=22+16(-1) (2)
6=1(4)+2 (4) 4=16+6(-2) (3)
4=2(2)+0 (5) 2=6+4(-1) (4)
22 , 60 ) =2
Example: Find x and y in GCD(22,60) o 2=6+4(-1)
o 2=6+[16+6(-2)](-1)
o 2=6+16(-1)+6(2)
Rewrite in the form: o 2=6(3)+16(-1)
o 2= [22+16(-1)](3)+16(-1)
o 2=22(3)+16(-3)+16(-1)
16 =60+22(-2) (1) o 2=22(3)+16(-4)
6=22+16(-1) (2) o 2=22(3)+ [60+22(-2)](-4)
4=16+6(-2) (3) o 2=22(3)+60(-4)+22(8)
o 2=22(11)+60(-4)
2=6+4(-1) (4)
o x=11 and y =-4
Other Examples :
 GCD( 56,15)
 GCD (180,378)
 GCD (7544,115)
Find x and y:
 GCD (254,32)
 GCD (74,383)
 GCD (7544,115)
 GCD (687,24)

You might also like