Euclidean algorithm

Nuvola apps edu mathematics-p.svg Subject classification: this is a mathematics resource.
Nuvola apps edu miscellaneous.svg Type classification: this is a lesson resource.
Smiley green alien big eyes.svg Educational level: this resource has not yet been assigned an educational level. Please help!

In this lesson we learn about the Euclidean algorithm, an ancient algorithm for finding the greatest common divisor of two integers.

The idea is as follows. Let p,q be two integers. Let p<q. The greatest common divisor of p and q, denoted (p,q), is the same as (p,q-p), or (p,q-2p),... and so on. Since there is such a q-kp which is smaller than p, the problem is reduced to the simpler one of calculating (q-kp, p). And so on.

For more details and background, see w:Euclidean algorithm, and w:Euclidean domain.

Try your hands on Euclidean algorithmEdit

Substitute the following text into the sandbox:

{{Subst:Euclidean algorithm|first integer|second integer}}

SandboxEdit

  +  


The greatest common divisor (g.c.d.) of 4689 and 2346 is
( 4689,2346 )
=(2346,2343)
=(2343,3)
=(3,0)
=(0,Division by zero)
The great common divisor is 3.