2.1 Euclidean Algorithm

The Euclidean Algorithm determines the greatest common divisor (gcd) of two positive numbers (e.g. r₀ , r₁ , where r₀ > r₁).
The algorithm consists in the repeated application of the following integer division:

r0	= q1r1+r2 ,	0 < r2 < r1
r1	= q2 r2+r3 ,	0 < r3 < r2
	...
rm-2	= qm-1rm-1+rm ,	0 < rm < rm-1
rm-1	= qmrm .

It can easily be shown that:

ggT( r₀ , r₁) = ggT( r₁ , r₂) = ... = ggT( r_m-1 , r_m) = r_m .

Since the Euklidische algorithm finds greatest common divisors it can be used to check if a positive number b < n has a multiplicative inverse modulo n, by setting r₀ = n and r₁ = b.
One does, however, not receive the value of the inverse (it this exists at all).
This is performed by the Extended Euclidean Algorithm.

2.2 Extended Euclidean Algorithm