- The greatest common divisor and the Euclidean algorithm
- The Chinese Remainder Theorem
- Powers modulo n
- The Euler -function and Euler's Theorem

Some Number Theory

Most public key systems rely on number-theoretic results. Before we can
discuss the implementation of one, we need to quickly go over the necessary
background. We have already used a tiny amount of number theory (in our
discussion of computing mod *p* and of the greatest common divisor). Of
course, this must be done briefly, and we will only touch on a small part of a
large and ancient field-- the interested reader would do well to consult a
text on number theory (e.g. [NZM], [Ros]) for more
information.

We have already met the greatest common divisor, or gcd, which is the largest integer which divides both of a pair of numbers. Two numbers are said to be relatively prime if their greatest common divisor is 1. As we have already seen, finding two relatively prime numbers has important applications in many cryptosystems.

How can we determine the gcd of two numbers? If the numbers are not too large, just looking at their factors does the trick. For example,

gcd(138, 126) = 6 since 138 = 2^{ . }3^{ . }23 and 126 = 2^{ . }3^{2 . }7.

However, there must be a more efficient way, since Maple can calculate
the gcd of two 60-digit numbers in well under a second, while taking a long
time (about 10 minutes on a 600 Mhz pentium computer) to factor either
one of them.
One such algorithm is the Euclidean algorithm, which has been around for
thousands of years. It works by computing successive differences-- to compute
gcd(*a*, *b*), where *a* > *b*, we first compute
*r*_{1} = *a* - *k*_{1}*b*, where *k*_{1}*b* is the
largest multiple of *b* that is less than *a*. Then we repeat this, finding
*r*_{2} = *b* - *k*_{2}*r*_{1},
*r*_{3} = *r*_{1} - *k*_{3}*r*_{2}, and so on until the remainder is
zero. The last nonzero remainder is the gcd. For example, to calculate
gcd(138, 126),

a |
= | 138 | |||||

b |
= | 126 | |||||

a |
- b |
= | 12 | = | r_{1} |
||

b - 10r_{1} |
= | -10a |
+11b |
= | 6 | = | r_{2} |

r_{1} - 2r_{2} |
= | 21a |
-23b |
= | 0 |

This not only gives gcd(138, 126) = 6, but expresses it as a difference of multiples of the two numbers: 6 = 11×126 - 10×138. We can write this procedure more formally as a theorem.

We have already seen that the Euclidean algorithm also gives us the following:

Why does the Euclidean Algorithm work? It follows from the observation that
if *a* = *bk* + *r*, then
gcd(*a*, *b*) = gcd(*b*, *r*). For example,
gcd(138, 126) = gcd(126, 12) = gcd(12, 6) = 6. We write this as a lemma.

Let
*d* = gcd(*a*, *b*). Then since *d* is a divisor of *a* and a divisor of
*b*, it is also a divisor of *a* - *bk*. Since *r* = *a* - *bk*, we have *d* a divisor of
*r*. So it must divide gcd(*b*, *r*).

Now, in order to prove equality, we want to show that also gcd(*b*, *r*) is a
divisor of *d*. Certainly gcd(*b*, *r*) divides *a*, since *a* = *r* + *bk*. It also
divides *b*, and so we have gcd(*b*, *r*) as a divisor of gcd(*a*, *b*).

Thus,
gcd(*b*, *r*) = gcd(*a*, *b*).

Now we are ready to prove that the Euclidean Algorithm (Thm. 10.1) always yields the greatest common divisor.

Notice that the sequence
*b* > *r*_{1} > *r*_{2} > *r*_{3} >... is a strictly
decreasing sequence of positive integers, so it must eventually terminate with
some *r*_{n} > 0. The last equation can be written as
*k*_{n + 1}*r*_{n} = *r*_{n - 1}, and so *r*_{n} is a divisor of *r*_{n - 1}. Then certainly
*r*_{n} = gcd(*r*_{n}, *r*_{n - 1}). Applying
the lemma to the equation above it, we obtain
gcd(*r*_{n}, *r*_{n - 1}) = gcd(*r*_{n - 1}, *r*_{n - 2}). Repeating in this way, we
obtain
*r*_{n} = gcd(*r*_{n}, *r*_{n - 1}) = gcd(*r*_{n - 1}, *r*_{n - 2}) =...= gcd(*r*_{1}, *b*) = gcd(*a*, *b*).

Recall that if *r* is such that
*ar* 1 (mod *n*), then *r* is called the
multiplicative inverse of *a* modulo *n*.
We have already dealt with such objects extensively. We now state a
theorem which tells us exactly when such inverses exist. Note that
this is really just Prop. 7.1 slightly reworded.

First, suppose that *a* has an inverse modulo *n*. Then there is a *k* so
that

Now suppose that
gcd(*a*, *n*) = 1. Then again using
Cor. 10.2,
there are integers *r* and *s* with
*ar* + *ns* = 1. This means *ar* - 1 is
divisible by *n*, so

It is common (and quite convenient) to denote the set of integers modulo *n*
as . That is,

= 0, 1, 2,..., *n*-1

As we already know, this set is closed under addition and
multiplication, and the usual associative, distributive, and commutativity
laws hold. This set is an example of an algebraic structure called a
ring.

We will use to denote the elements of which
have multiplicative inverses. In light of the last theorem, we have

= *a* gcd(*a*, *n*)=1

For example,
= 1, 2, 3, 4, 5, 6 = 1, 3, 5, 7 = 1, 5, 7, 11

In this section, we state a very old theorem about simultaneous solutions to
congruences. This theorem may have been known to the eight-century Buddhist
monk I-Hsing, and certainly appears in Ch'in Chiu-shao's *Mathematical
Treatise in Nine Sections*, written in 1247. It is sometimes (rarely)
referred to as the ``Formosa Theorem''.

As an example of this, suppose five kids pool all their money and buy a bag of candy. They divide the candy up evenly, and find there are 3 pieces left over. Suddenly, one kid's mom comes out, tells him ``no candy before dinner'', and hauls him off. The other four kids divide up the candy and there is one piece left over. While they are squabbling over it, a dog runs up and eats the disputed piece.

The Chinese Remainder Theorem tells us that we can always determine how many
pieces of candy were in the bag, at least up to multiples of 20. In the above
example, there were 13 pieces of candy (or 33, or 53, or ...). If we
want to solve this problem with Maple, the command
chrem([3,1],[5,4]) does the trick. We could also use
numtheory[mcombine](5,3,4,1).

Since *m* and *n* are relatively prime, there are integers *k* and *t* so that
*mk* + *nt* = 1. Then

To check uniqueness, suppose there are two solutions *c* and *d*. Since
*c* *a* (mod *m*) and
*d* *a* (mod *m*), we have
*c* - *d* 0 (mod *m*). Similarly,
*c* - *d* 0 (mod *n*). Since both *m* and *n*
divide *c* - *d*, and *m* and *n* are relatively prime, we have that *mn*
divides *c* - *d*. Thus
*c* - *d* 0 (mod *mn*), that is,
*c* *d* (mod *mn*).

In this and future sections, we shall use the notation
*ab* to denote
*a* mod *b*.

First, let's take a look at a few examples of what happens when we reduce
the sequence
*a*, *a*^{2}, *a*^{3}, *a*^{4},... modulo *n*.
Consider
3^{k}20:

3, 3^{2}20 = 9, 3^{3}20 = 7, 3^{4}20 = 2120 = 1, 3^{5}20 = 3,...

The sequence consists of four numbers 3, 9, 7, 1 and then it repeats. What about 4? We have

4, 4^{2}20 = 16, 4^{3}20 = 4, 4^{4}20 = 16,...

This is also periodic, but notice that we never get back to 1. Similarly, let's look at the powers of 6:

6, 6^{2}20 = 3620 = 16, 6^{3}20 = 16^{ . }620 = 9620 = 16, 6^{4}20 = 16,...

This gets stuck at 16. Finally, consider the powers of 11:

11, 11^{2}20 = 12120 = 1, 11^{3}20 = 11,...

This sequence is periodic of period 2, and contains 1.

We can readily categorize the elements with finite order. If you look at the examples above, 3 and 11 have finite order mod 20, while 4 and 6 do not. You probably have already guessed that this is because gcd(3, 20) = 1 and gcd(11, 20) = 1, while gcd(4, 20) = 4 and gcd(6, 20) = 2.

First, suppose *a* has finite order mod *n*. Then there is some *k* so that

1 = *a*^{k}*n* = *an*^{ . }*a*^{k - 1}*n*.

Thus,
Now we suppose
gcd(*a*, *n*) = 1, and we want to find the inverse of *a*.
Consider the sequence

So, we have seen that any invertible element of has finite order. In
particular, if *p* is a prime number, every element except 0 is
invertible and so has finite order. What are the possible orders? A
theorem of Pierre de Fermat gives a result in that direction.

Among other things, this theorem says that if *p* is prime, then the order of
*a* mod *p* always divides *p* - 1. Note that it doesn't say the order *is*
*p* - 1, just that it is a divisor of it. Also, it says nothing about order
with modulo a non-prime. We won't give the proof of this theorem here.
Rather, we will give a proof of a more general result in the next section.

Recall that we denote the set of invertible elements of by . That is,

= *a* *Z*_{n}gcd(*a*, *n*)=1.

This set is sometimes called a reduced residue system modulo
We can compute a few values of
(*n*) just by counting.

(2) | = | 1 | since | = | 1 | |

(3) | = | 2 | since | = | 1, 2 | |

(4) | = | 2 | since | = | 1, 3 | |

(5) | = | 4 | since | = | 1, 2, 3, 4 | |

(6) | = | 2 | since | = | 1, 5 | |

(7) | = | 6 | since | = | 1, 2, 3, 4, 5, 6 | |

(8) | = | 4 | since | = | 1, 3, 5, 7 | |

(9) | = | 6 | since | = | 1, 2, 4, 5, 7, 8 | |

(10) | = | 4 | since | = | 1, 3, 7, 9 | |

(11) | = | 10 | since | = | 1, 2, 3, 4, 5, 6, 7, 8, 9, 10 | |

(12) | = | 4 | since | = | 1, 5, 7, 11 |

Of course, Maple also knows about the function in the numtheory package, so we could generate more values by asking Maple. But let's try to understand a bit more. We can readily prove some properties of .

**(a)** This is immediate, since all non-zero elements of
0, 1,..., *p*-1 are invertible.

**(b)**
We prove this part just by counting. Since *p* is prime, the only numbers
in which are not relatively prime to *p*^{n} are multiples of *p*. These
are
0, *p*, 2*p*, 3*p*,..., *p*^{2},(*p* + 1)*p*,...,(*p*^{n - 1} - 1)*p*. Note that
*p*^{n - 1}*p* = *p*^{n}, so there are exactly *p*^{n - 1} multiples of *p* less than
*p*^{n} (including 0). All the others are relatively prime to *p*-- this
gives the result.

**(c)**
We need to show that the number of elements in is the same as the
product of the size of and . We do that by showing that for
each
*t* , there is exactly one pair (*r*, *s*) with
*r*
and
*s* .

So, let
*r* and
*s* . Then, by the Chinese Remainder Theorem
(Thm. 10.5), there is an integer *t* < *ab* with

Now take
*t* , and we must find a corresponding *r* and *s*. Let
*r* = *ta*. Now, since
gcd(*t*, *ab*) = 1, certainly
gcd(*t*, *a*) = 1. Since
*r* *t* mod *a*, there is an integer *k* so that *t* = *r* + *ka*, so we have
gcd(*r*, *a*) = 1. Thus
*r* . Similarly, we let
*s* = *tb*, and
we see that
*s* .

Since we have paired each
*t* with a unique pair
(*r*, *s*) ×*Z*_{b}^{*}, they have the same cardinality. The first set has
(*ab*) elements, and the latter has
(*a*)(*b*).

We now come to Euler's generalization of Fermat's result. This result is the central idea underlying the RSA public key cryptosystem.

Let *a* be relatively prime to *n*, and consider the set

Now, multiply all the elements of together; call the result *N*.
Then
*Nn* . If we multiply all the elements of *a*
together, we get
*a*^{(n)}*N*, and since the two sets are the same, we
have

- ...
$$ -
*function*,^{4.31} - Although the function was invented by Euler, the notation $&phiv#varphi;(n)$ to represent it is actually due to Gauss.

2002-08-29