Euclid's algorithm find the gcd (greatest common divisor) of two integer numbers. It is based on the following facts:
Now Euclid's algorithm. Given two numbers a and b, find their gcd.
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).
The system of equations
Suppose that n is a solution to the system. Then
there are two numbers t1 and t2 such that
n = t1 m1 + n1
= t2 m2 + n2.
Fermat's little theorem
If p is aprime number which does not divide a then ap-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
An immediate corollary of this theorem is that if p is prime than for any integer a, ap = 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.
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).