Euclidean Algorithm

AllPages
RecentChanges
Links to this page
Edit this page
Search
Entry portal
Advice For New Users

Devised by Euclid, the Euclidean Algorithm is a method for finding 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

More if anyone asks.
Links to this page / Page history / Last change to this page
Recent changes / Edit this page (with sufficient authority)
All pages / Search / Change password / Logout