# Euclid's Algorithm

Euclid's algorithm is a famous procedure for finding the gcd, i.e., greatest common divisor (factor) of two integers. The idea is pretty simple. If

If N = M×s then M = gcd(N, M).

when N = M×s + R (where all four are positive integers), then every common divisor of M and N is also a divisor of R. Actually, any common divisor of any pair of these three numbers is a divisor of the third; so that, with

N = M×s + R implies gcd(N, M) = gcd(M, R).

Euclid's algorithm is based on the observation that taking R to be the remainder of the division of N by M makes

The applet below illustrates Euclid's algorithm. The two numbers on top are modifiable digit-by-digit. Click a little off the vertical midline of the digit you wish to modify. (For a faster action just drag the mouse up and down.) When the box "Autonomous digits" is checked, trying to increase, say, 9 in 19 will result in 10, otherwise it will be 20. The number of digits is also controlled at the bottom of the applet.

What if applet does not run? |

- Modular Arithmetic
- Chinese Remainder Theorem
- Euclid's Algorithm
- Pick's Theorem
- Fermat's Little Theorem
- Wilson's Theorem
- Euler's Function
- Divisibility Criteria
- Examples
- Equivalence relations
- A real life story

|Activities| |Contact| |Front page| |Contents| |Algebra|

Copyright © 1996-2018 Alexander Bogomolny

70196893