Euclidean algorithm

From Wikiversity

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.

[edit] Try your hands on Euclidean algorithm

Substitute the following text into the sandbox:

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

[edit] Sandbox

+

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.