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:

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.

Enrichment Task

You should check that:

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.

Axiom ComplexPlane EuclideanGeometry Factorial FermatsLittleTheorem MatrixTransformation PerfectNumber PoincaresDisc	(none)			AddingComplexNumbers AddingFractions Admin_ProjectFrontEnd CommonMultiple EquivalentFractions HighestCommonFactor MultiplyingComplexNumbers WhatIsThisAbout
↓	↓		↓	↓
Euclid ModuloArithmetic			CancellingFractions CommonFactor
			↓
		⇌	You are here EuclideanAlgorithm
			↓
			ContinuedFraction Divisor HighestCommonFactor PrimeNumber 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

Local neighbourhood - D3

Edit this page
(with sufficient authority)
Change password

Recent changes
All pages
Search