Devised by Euclid, the Euclidean Algorithm is a method for finding the highest common factor (also know as the greatest common divisor) of two numbers.

Here's the algorithm:

• Let a and b be your starting numbers
• Compute q and r such that a=qb+r and 0<=r<b
• Copy b into a and r into b.
• Repeat until r=0.
The value in b is now the GCD of the original a and b.

As an example, consider 429 and 2002.

 a = q * b + r 2002 = 4 * 429 + 286 429 = 1 * 286 + 143 286 = 2 * 143 + 0

Here we can see that gcd(429,2002) is 143.

You should check that:

• this is an algorithm in the technical sense
• the result always divides the original a and b
• every divisor of both a and b will divide the result.

## Extras

• If $g=gcd(a,b)$ then the $q$ in the algorithm can be used to compute $c$ and $d$ such that $g=ca+db.$
• This in turn can be used to show that working in modulo arithmetic, every non-zero number has a multiplicative inverse $mod~p,$ when $p$ is a prime number.
• This algorithm can also be used to find the exact continued fraction of a square root.
• If $l=lcm(a,b)$ and $g=gcd(a,b),$ then $lg=ab.$

Axiom
ComplexPlane
EuclideanGeometry
Factorial
FermatsLittleTheorem
MatrixTransformation
PerfectNumber
PoincaresDisc
CommonMultiple
EquivalentFractions
HighestCommonFactor
MultiplyingComplexNumbers
Euclid
ModuloArithmetic
CancellingFractions
CommonFactor

## You are here

EuclideanAlgorithm
ContinuedFraction
Divisor
HighestCommonFactor
SquareRoot
Axiom
DedekindCut
EuclideanGeometry
FamousPeople
FermatsLittleTheorem
MersennePrime
PerfectNumber
Integer CancellingFractions
CoDomainOfAFunction
CommonFactor
ComplexNumber
CompositeNumber
CountingNumber
Denominator
DomainOfAFunction
Function
ImageOfAFunction
ImaginaryNumber
LeastCommonMultiple
PrimePair
RationalNumber
RealNumber
ReducingFractionsToLowestTerms
RiemannSurface
Root
RootTwoIsIrrational
WholeNumber