Scribd
Upload
62 views2 pages

(Joland) Euclidean Algorithm

Uploaded by

Joland Manzano
Copyright
© © All Rights Reserved
We take content rights seriously. If you suspect this is your content, claim it here.
Available Formats
Download as DOCX, PDF, TXT or read online on Scribd
62 views2 pages

(Joland) Euclidean Algorithm

Uploaded by

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

Name: Joland Manzano

Course: BSED Major in Mathematics III

Euclidean Algorithm
The Euclidean algorithm is a method for finding the greatest common divisor
of two integers. It involves repeatedly applying the division algorithm until
the remainder is zero. The last non-zero remainder is the GCD.

Example:

GCD(99, 78)

a=b* q + r

99=78(1)+21

78=21(3)+15

21=15(1)+6
The last non-zero remainder
15=6(2)+3
is the gcd. Gcd=3
6=3(2)+0

Extended Euclidean Algorithm


The extended Euclidean algorithm builds upon the regular Euclidean
algorithm. It not only finds the GCD but also determines the integer
coefficients 'x' and 'y' that satisfy the equation ax + by = gcd(a, b).

Example 2: 99x+78y=gcd(99,78)

find the gcd using Euclidean algorithm which is in example no.1.

Gcd=3

3=15+6(-2)
THEREFORE
3=15+(21+15(-1))-2 3=78(3)+21(-11)
x=-11 and y=14
3=21(-2)+15(3) 3=78(2)+(99+78(-1))
(-11)
3=21(-2)+(78+21(-3)) (3)
3=99(-11)+78(14)
Joland’s Revised Extended Euclidean Algorithm
First step is list down the negation of q in example no.1

q -q Y=(k1)(k2)+x= y(k3)+x= y(k4)+x


=…
1 -
1=k4
3
- X=1 k1=x y=x
1
3=k3 y=x …
2
-
Y=(-2)(-1)+1= 3(-3)+-2= -11(-1)+3 = 14
1=k2

-
X=-11 and y=14
2=k1
X=1 -2=x 3=x -11=x

You might also like