Math 174 Lecture 21 Summary

Number Theory

Divisibility: We use the notation



to mean “a divides b ” exactly. So etc. while the symbol means “does not divide
evenly”, so , and 12 etc. Note that holds for all a, i.e. zero is divisible by everything.

Greatest Common Divisor The greatest common divisor (GCD) of a and b is defined as:



So for example, gcd(20,65) = 5, gcd(19,38) = 19, gcd(5,12) = 1 etc.

Lowest Common Multiple The lowest common multiple (LCM) of a and b is defined as:



So for example, lcm(20,30) = 60, lcm(19,38) = 38, gcd(5,12) = 60 etc.

Lemma The GCD g(a, b) and LCM l (a, b) satisfy:



Proof If g is the GCD of a and b then they can both be written:

a = ga'

b = gb'

and substituting into l = ab/g gives l = a'gb'. That form of l is clearly divisible by both a and b
and so it is a common multiple.

Then either l = ab/g is the LCM or there is another common multiple which is smaller.
Suppose a smaller LCM exists. Now the LCM divides all common multiples of a and b , and in
particular, it divides ab. Define



The ratio / b is an integer ( is a multiple of b), and rearranging the last equation shows that is
a factor of a :

Similarly the ratio =a is an integer, and rearranging shows that is also a factor of b.

Thus is a common multiple of a and b. Now since l = ab/g and = ab= and l > , we
must have > g. But that is a contradiction (g is the greatest common divisor of a and b).

Factorization

A prime p > 1 is a number with no divisors except for p and 1.

Other numbers are called composite. Composite numbers have unique factorizations as powers of
primes . That is, every number (primes too) n can be uniquely ex pressed as a product :



For example 84 = 2² ×3 ×7.

Division Theorem

Given a dividend a and a divisor b, there are unique integers q and r ∈ [0, ..., b - 1] such that:

a = qb + r

and we write q = a div b for the quotient and r = a mod b for the remainder.

Note that b l a is equivalent to a mod b = 0

With the results we have so far, we can prove an interesting theorem. You already know this
theorem is true, but nevertheless its useful to know one reason why.

Theorem: There are infinitely many primes.

Proof: Suppose not. Then there are finitely many primes, . Lets define a new number Q
as



By the unique factorization theorem, this number must be a product of powers of primes. But
notice that:



In other words, Q is not divisible by any of the p_is, which means it has no prime factors at all.
That is, it must be equal to 1. But that is a contradiction because all the p_i’s are > 1 and so is their
product. QED

Euclid’s Algorithm

Euclid’s algorithm is a method for efficiently computing GCDs. Its based on the observation that
if

g = gcd(a, b)

then

r = a mod b = a - qb

is also divisible by g because both a and b are. By repeatedly taking remainders, we can reduce the
size of the numbers whose gcd we are computing, until eventually we get the gcd itself. Let



We will say more in a moment about why thismust terminate with a zero . To see that this computes
the GCD, we notice that common divisors of any pair of consecutive r_i’s are the same. That is

Lemma

The number g is a common divisor of and if and only if it is a common divisor of and
.

Proof

First suppose g is a common divisor of and . Then can be written



where q_j is the j^th quotient. Clearly, any common divisor of and will be a divisor of .
If we simply rearrange this expression:



then we can see that any divisor of both and r_j is also a divisor of . QED

It follows immediately that very last pair in the sequence is , 0, so
. We can apply the equality all the way back to the begining to
conclude that:



That is, , the last non-zero remainder in the sequence.

Next we consider the speed of convergence. First of all, notice that if a > 0 and b > 0, then
the sequence is strictly decreasing. So it must eventually terminate with a zero. How fast does it
decrease?

We show that if the algorithm runs for k steps (k defined as above), then

Lemma
If Euclid’s algorithm runs for k steps, then



where F_k is the k^th Fibonacci number.

Proof
Assume w log that a > b > 0 (else swap a, b). Then at every step there is a positive quotient
such that



where because and .

The proof is by induction. Assume:

The base cases are j = 2, 3, where F₂ = 1, F₃ = 2. The corresponding remainders are and .
Now , and since the sequence is decreasing. This completes the
case cases.

For the inductive step, we use the identity:



Making the substitution i = k - j + 2 gives:



And we substitute using , giving:

remember

So we have moved the Fibonacci inequality up one level in the sequence. We get the results we are
looking for by setting j = k - 1 for a and j = k - 2 for b:



Which completes the proof. QED

From this result it follows that if , the algorihm must run for less than k step. Now
the Fibonacci numbers satisfy where  is the golden ratio . Thus k is at most
about . So we can say that:

Corollary Euclid’s algorithm takes O(log a) steps to compute gcd(a, b).

Extended Euclid

We can get more information from Euclid’s algorithm by doing some book-keeping. In particular,
if g = gcd(a, b), we will compute x, y such that

g = ax + by

This follows easily by induction. Suppose that we can express



Clearly this is true for i = 1, 2 with the pairs (1, 0) and (0, 1) respectively. Suppose its true
for i and i + 1. We prove it holds for i + 2. Now



Which proves the identity we were looking for and establishes the inductive formulae:



And if is the last remainder in the sequence, we see that



To implement extended Euclid, simply initialize and to (1, 0) and (0, 1) respecively,
and use the above inductive formula as the remainders are computed.