Euclidean algorithm

This algorithm is used to calculate the greatest common divisor for two positive integers. This uses Euclid’s rule and modular arithmetic.

Algorithm

Euclid(x,y):
	Input: integers x,y where x >= y >= 0
	Output: gcd(x,y)
1. If y = 0 return x
2. return Eculid(y, x mod y)

Run time

If and are -bit integers then calculating mod takes time. From Claim 1 we have every 2 rounds decreases by at least a factor of 2. So there are at most rounds giving this algorithm a run time of .

Claim 1

Claim 1

If then mod < .

Proof

If then mod .

If then mod = .

Correctness

This follows from Euclid’s rule.