# Euclidean algorithm

Jump to navigation
Jump to search

Subject classification: this is a mathematics resource. |

Type classification: this is a lesson resource. |

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 | edit source]

Substitute the following text into the sandbox:

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

### Sandbox[edit | edit source]

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.