Euclidean algorithm

From Wikiversity
Jump to navigation Jump to search
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 algorithm[edit]

Substitute the following text into the sandbox:

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

Sandbox[edit]

Libya 5230 Wan Caza Dunes Luca Galuzzi 2007.jpg + Crystal Clear app kthememgr.png


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.