Scribd
Upload
4 views16 pages

Understanding the Euclidean Algorithm

The document explains the Euclidean Algorithm, a method for finding the greatest common divisor (gcd) of two positive integers through recursive division without factoring. It also introduces Bezout’s Theorem, which states that any two nonzero integers have a gcd that can be expressed as a linear combination of those integers. Additionally, it discusses the concept of relative primality and its relevance in finding multiplicative inverses in modular arithmetic.

Uploaded by

Shawn Sensei
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
4 views16 pages

Understanding the Euclidean Algorithm

The document explains the Euclidean Algorithm, a method for finding the greatest common divisor (gcd) of two positive integers through recursive division without factoring. It also introduces Bezout’s Theorem, which states that any two nonzero integers have a gcd that can be expressed as a linear combination of those integers. Additionally, it discusses the concept of relative primality and its relevance in finding multiplicative inverses in modular arithmetic.

Uploaded by

Shawn Sensei
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

Module 3
By recursive use of the division
algorithm, we may find the greatest
common divisor of two positive
integers a and b, gcd (a, b), without
factoring either. This procedure is
also known as the Euclidean
Algortihm
First, note that if and , then . The
next observation provides the basis
for the Euclidean Algorithm. If ,
then . Thus given integers , the
Euclidean algorithm uses the division
algorithm repeatedly
with
with ,
etc.
Since the remainders get smaller
and smaller, and after a finite
number of steps we obtain a
remainder . Thus
Example

𝑎= 329 , 𝑏 =182
Example

𝑎= 35 , 𝑏=11
Example

𝑎=52 , 𝑏 =30
Example

𝑎= 24 , 𝑏 =51
Bezout’s Theorem
Module 3
Theorem
Any two nonzero integers a and b
have a greatest common divisor,
which can be expressed as the
smallest positive linear combination
of a and b.
Moreover, an integer is a linear
combination of a and b if and only if
it is a multiple of their greatest
Bezout’s Theorem
Let then there exist such that .
Example
Find the , and also find such
that
Example
Find the , and also find such
that
Example
Find the , and also find such
that
Corollary
Two integers a and b are relatively
prime [that is, ] if and only if there
exist x, y such that .

Note: It will be used in finding for the multiplicative inverse of mod

You might also like