**Euclid's Algorithm**

Euclid's algorithm find the gcd (greatest common divisor) of two integer numbers. It is based on the following facts:

- if b | a (ie, b divides a ) then gcd(a,b) = b.
- if a > b and a = k b + r then gcd(a,b) = gcd(b,r).

Now Euclid's algorithm. Given two numbers a and b, find their gcd.

- Suppose a > b; if b | a the gcd(a,b) is b. Output b and exit.
- Divide a by b; let r be the remainder. Replace a = b, and b = r. Goto step 1.

A corollary of Euclid's algorithm.
Given two integer numbers a and b there exits two (possibly negative) integers
t and s such that t a + s b = gcd(a,b).

The proof is by induction on the number of steps required to find the
gcd of the two numbers using Euclid's algorithm.
Again assume a > b. If b|a, a = kb and 1 a + (1-k) b = gcd(a,b).
Otherwise a = kb + r and we want to find two integers, t and s, such that
t a + s b = (tk+s)b + tr = gcd(a,b). Since the numbers b and r require
one less step of Euclid's algorithm, by induction we have two numbers
t' and s' such that t' b + s' r = gcd(b,r) = gcd(a,b).
Therefore the two numbers t = s' and s = t' - s' k solve the problem.

**Extended Euclid's Algorithm**

The extended Euclid's algorithm finds both the gcd of the two numbers, a and b, and the integer numbers, t and s, such that t a + s b = gcd(a,b).

- Assume that a > b. Initialize t = 1, s = 0, so that a = t a + s b (first relation), and t' = 0, s' = 1 so that b = t' a + s' b (second relation).
- Find the integer k such that k b is the greatest multiple of b smaller than a.
- Let t"=t', t' = t - k t' and t = t". Similarly let s"=s', s' = s - k s', and s = s". (This is equivalent to subtract the second relation multiplied by k from the first, obtaining the new second relation r = t' a + s' b, and replacing the first equation by b = t a + s b.)
- If r is not zero go back to step 2.
- The values t and s are the two integers such that t a + s b = gcd(a,b). The value on the lhs of the first relation is the gcd.

The system of equations

n = n

is solvable iff n

Suppose that n is a solution to the system. Then
there are two numbers t_{1} and t_{2} such that
n = t_{1} m_{1} + n_{1}
= t_{2} m_{2} + n_{2}.
Therefore

The left hand side is divisible by g. Hence n

Conversely let k = (n

Since m

Finally to prove the uniqueness, suppose that there are two solutions to the system,

N = T

By subtracting side by side these equations we obtain that N - n = 0 mod(m

**Fermat's little theorem**

If p is aprime number which does not divide a then a^{p-1} = 1
mod(p).

List the numbers a, 2a, 3a, ..., (p-1)a.
If ra = sa mod(p), since r and s are less than p and p does not divide a
we must have r=s. Therefore the numbers above are all different mod(p),
so they scan (modulo p) the integers 1, 2, ..., (p-1).
By multiplying together all these congruences we have

Hence a

An immediate corollary of this theorem is that if p is prime than
for any integer a, a^{p} = a mod(p).

Note. This results is not true for prime numbers only. Non-prime numbers which satisfy the conditions of the theorem are called pseudo-primes.

Note.
Another test of primality is Wilson's theorem: p is prime iff
(p-1)! = -1 mod(p).

If p is prime for each a there is a number b (unique modulo p) such that
ab = 1 mod(p). If a=1 b=1. If a=p-1 b=p-1. For the other numbers
b is different from a. Therefore the numbers in the product 2 3 ... (p-2)
can be paired so that (p-2)! = 1 mod(p), and (p-1)! = -1 mod(p).
If p is not prime the (p-2)! and p have common factors
(since p-1 and p are coprime). Therefore
gcd((p-2)!, p)>1, and (p-2)! = k > 1 mod(p). Thus
(p-1)! = -k < -1 mod(p).

Marco Corvi - 2003