[go: up one dir, main page]
Scribd
Upload
9 views1 page

Euclidean Algorithm

The document explains the Euclidean algorithm for finding the greatest common divisor (GCD) of two integers through repeated division until a remainder of zero is reached. It also introduces the extended Euclidean algorithm, which not only finds the GCD but also determines integer coefficients that satisfy the equation ax + by = gcd(a, b). Examples are provided to illustrate both algorithms using the integers 99 and 78.

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
9 views1 page

Euclidean Algorithm

The document explains the Euclidean algorithm for finding the greatest common divisor (GCD) of two integers through repeated division until a remainder of zero is reached. It also introduces the extended Euclidean algorithm, which not only finds the GCD but also determines integer coefficients that satisfy the equation ax + by = gcd(a, b). Examples are provided to illustrate both algorithms using the integers 99 and 78.

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
You are on page 1/ 1

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)

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)

You might also like