Number Theory Results

Euclid's Algorithm

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

The first fact is obvious. To prove the second one note that if x | a and x | b then x must divide also r = a - kb. Conversely if x | b and x | r then x divides also a = kb + r. Therefore a number divides both a and b iff it divides b and r.

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

  1. Suppose a > b; if b | a the gcd(a,b) is b. Output b and exit.
  2. 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).

  1. 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).
  2. Find the integer k such that k b is the greatest multiple of b smaller than a.
  4. 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.)
  5. If r is not zero go back to step 2.
  6. 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 Chinese Remainder Theorem

The system of equations

n = n1 mod m1
n = n2 mod m2

is solvable iff n1 = n2 mod( g ) where g = gcd( m1, m2). Furthermore two solution differ by a multiple of lcm( m1, m2).

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. Therefore

t1 m1 - t2 m2 = n2 - n1

The left hand side is divisible by g. Hence n2 - n1 is also divisible by g.
Conversely let k = (n2 - n1) / g. To solve the system we need to find two numbers, t1 and t2, such that
t1 m1/g - t2 m2/g = k.

Since m1/g and m2/g are coprime there exist, by the corollary to Euclid's algorithm, two numbers s1 and s2 such that s1 m1/g + s2 m2/g = 1. Now take t1 = k s1 and t2 = - k s2.
Finally to prove the uniqueness, suppose that there are two solutions to the system,
n = t1 m1 + n1 = t2 m2 + n2
N = T1 m1 + N1 = T2 m2 + N2

By subtracting side by side these equations we obtain that N - n = 0 mod(m1) and N - n = 0 mod(m2). Therefore N = n mod lcd(m1, m2).

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

ap-1 (p-1)! = (p-1)! mod(p)

Hence ap-1 = 1 mod(p).

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.

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