Senior Math Circles – Cryptography and Number

Theory Week 2
Dale Brydon
Feb. 9, 2014

1 Divisibility and Inverses

At the end of last time, we saw that not all numbers have inverses mod n, but some
do. We will now explore what conditions must be satisfied for an inverse to exist.
We say that an integer, a, is divisible by an integer, b, if there exists an integer c,
such that a = bc. In this case, we write b | a and say b divides a. If b is positive, this
is equivalent to saying that a (mod b) = 0. For example, we know that −2 | 6, since
6 = (−2)(−3).
There are many facts useful relating to divisibility; let’s examine one we’ll use a
little later. If d | a and d | ka + b for some integers k and b, then d | b.
Proof. Since d | a, there exists an integer c1 so that c1 d = a. Similarly there exists
an integer c2 so that c2 d = ka + b = kc1 d + b. But then c2 d − kc1 d = b and so
(c2 − kc1 )d = b. This gives that d | b, since c2 − kc1 is an integer.
If d | a and d | b, then d is a common divisor of a and b. The largest such divisor
is known as the greatest common divisor or GCD of a and b and is often denoted
gcd(a, b). For example, the positive divisors of 20 are 1, 2, 4, 5, 10, and 20 and the
positive divisors of 16 are 1, 2, 4, 8, and 16 and hence gcd(20, 16) = 4.
One natural question that arises is “How can we compute GCDs, especially of
large numbers?” One method we just saw was to list all the (positive) divisors of
both numbers and then see what the biggest common one was. But, how do we find
all the divisors of a number? One method is to factor it, but that leaves us another
question: “How do we factor large numbers?” We will discuss this question in depth
later, but for now, it is enough to say there is no natural method to do it quickly.
Hence, we must use some other approach.
Our approach will rely on the following theorem: If a = qb + r, for any integers q
and r, then gcd(a, b) = gcd(b, r). Let’s try to prove this.
Proof. Let d = gcd(a, b). We know d | a and so d | (qb + r). We also know d | b and
hence, from our fact above, d | r. So we know that d is a common divisor of b and

1
r. Now suppose e is any common divisor of b and r. In an exercise below you will
prove that e divides qb + r = a. But then, e | a and e | b and so e ≤ d by definition
of GCDs. Hence, d = gcd(b, r).
Notice that if a (mod b) = r, then we can write a = qb + r for some integer q and
hence gcd(a, b) = gcd(b, r). So provided b is positive, we can use this simplification
to help us find the GCD. It’s easy to show gcd(a, b) = gcd(a, −b), and so, in fact, we
can always use this simplification. We’ll now describe an algorithm for computing
GCDs assuming b ≥ 0.
The Euclidean Algorithm:

1. Set r0 = a and r1 = b and i = 1.

2. If ri = 0 then gcd(a, b) = bi .

3. Write ri−1 = qi ri + ri+1 , where 0 ≤ ri+1 ≤ ri − 1 and increment i by 1.

4. Go to step 2.

Let’s do an example to see this in action by computing gcd(135,99). The algorithm

consists of a series of equations as seen below.

135 = (1)99 + 36
99 = (2)36 + 27
36 = (1)27 + 9
27 = (3)9 + 0.

Since we see a remainder of 0 in the last equation, the remainder in the previous
equation is the GCD. Thus, gcd(135, 99) = 9.
This algorithm turns out to be very efficient. Without going into too many details
about what exactly I mean by “efficient”, I will say that it can be used to compute
the GCDs of very large numbers very quickly using a computer. For example, I was
able to compute the GCD of two 500-digit numbers in less than a second using a
completely unoptimized version of the algorithm.
Now that we have a concept of GCDs and how to compute them. We will turn
our attention back to inverses mod n. In particular, we still want to know when a
number has an inverse mod n. We’ll prove that to be invertible, a number must be
congruent to 1 mod n.
Proof. It’s not too hard to see that if ak ≡ 1 (mod n), then ak = 1 + qn for some
integer q. Hence, ak −qn = 1. Now suppose d = gcd(a, n). Once again, by an exercise
later, you will see that this means d divides the left-hand side of this equation. Thus,
d divides 1 and hence d = 1. So we have just seen that if a has an inverse mod n,
then gcd(a, n) = 1.

2
It turns out, that it’s also true that if gcd(a, n) = 1, then a has an inverse mod
n. We will look at why this is true and how to find the inverse next.
By subbing each equation generated by the Euclidean algorithm into the next
one we can find the inverse of a (mod b), when it exists. It’s easiest to see how the
extended Euclidean algorithm works by seeing an example. Earlier we saw

135 = (1)99 + 36
99 = (2)36 + 27
36 = (1)27 + 9
27 = (3)9 + 0.

We know that the GCD is 9 and from the second last equation we can see that
9 = 36 − (1)27. We can substitute into this the (rewritten) equation above to give
that
9 = 36 − (1)(99 − (2)36) = 3(36) − 99.
Further substitution gives that

9 = 3(135 − (1)(99)) − 99 = (3)135 − (2)99.

In this way we can find integers x and y so that gcd(a,b) = ax + by. When gcd(a, b) =
1, x ≡ a−1 (mod b). So we have seen when a number has an inverse mod n and how
to find that inverse.

2 Primes
A prime number is an integer greater than 1 whose only positive divisors are one
and itself. Numbers that are not prime are called composite. Primes will play an
important role in the RSA cryptosystem we will talk about next time. The most
important property of primes for us has to do with factoring.
The Unique Factorization Theorem: Every positive integer can be expressed
as a unique product of primes up to ordering. That is every integer n can be written
as
pe11 pe22 · · · pekk
for some integer k, where the pi ’s are primes and there is only one choice for the pi ’s
and the exponents ei . As a brief example 100 = 22 · 52 and this is the only way to
factor 100 (every factorization will contain two 2s and two 5s). The proof of this
theorem involves a few too many details to talk about in this series and so is skipped.
So we know that every integer n can be factored, but how can it be done? Is
there anyway to do it quickly? One method you might use is trial division where you
test to see if every number less than n divides it. This can be improved significantly
√
by noticing that you only need to test numbers that are at most as big as n. This

3
√ √
works since if n = ab, then either a ≤ n or b ≤ n. But even that improvement
is not enough to create a fast algorithm. Trying this method to factor one of the
500-digit numbers whose GCD could be computed in less than a second would lead
to a computation that would take longer than the lifetime of our sun to complete.
The hardest numbers to factor are those that are the product of two primes p and
q, where p ≈ q. That is the two primes are relatively close together (have the same
number of digits or bits). The largest such well-generated number to be successfully
factored had 232-digits, took 2 years of work to complete, and used over 2000 years of
computation time. In summary, there is no known method to efficiently factor very
large numbers using a classical computer. (The problem can efficiently be solved with
a quantum computer, should anyone ever build a big enough one.) The difficulty of
factoring will play an important role in the security of RSA.
Since we will need to use very large primes in our upcoming cryptosystem, it
would be good to make sure that such numbers exist. That is, we want to guarantee
that even very large numbers can be prime. We will prove that there are, indeed,
infinitely many primes.
Proof. Suppose, by way of contradiction, that there are finitely many primes

p1 , p 2 , · · · , p k ,

for some integer k. Consider the integer

n = p1 p2 · · · pk + 1.

Since n is positive, it can be written as a product of primes, by the unique factorization

theorem. But, since n ≡ 1 (mod pi ), we can tell that pi - n, for all 1 ≤ i ≤ k.
Hence, there must be some prime that divides n that is not in our list, contradicting
our assumption that we had listed all primes. Thus, our assumption that there are
finitely many primes must be false.
We will finish this portion of the series by looking at one more property of primes.
It turns out that if p is a prime and a 6≡ 0 (mod p), then ap−1 ≡ 1 (mod p). This
is known as Fermat’s Little Theorem (F`T). Using this, we will show that if p and q
are distinct primes, and gcd(a, pq) = 1, then a(p−1)(q−1) ≡ 1 (mod pq).
Proof. First, we can see that gcd(a, p) = gcd(a, q) = 1, since any number that divides
p or q divides pq as well. So we know,

a(p−1)(q−1) ≡ (ap−1 )q−1 ≡ 1q−1 ≡ 1 mod p

and
a(p−1)(q−1) ≡ (aq−1 )p−1 ≡ 1p−1 ≡ 1 mod q.
Let n = a(p−1)(q−1) . We have just shown that n = 1 + k1 p and n = 1 + k2q for some
integers k1 and k2 . Hence, k1 p = k2 q. We know p | k1 p and so p | k2 q. In one of the

4
exercises below you will show that if r is prime and r | ab then r | a or r | b. Using
this fact, and the fact that p - q, we can see that p | k2 . Hence, pq | k2 q and so the
equation n = 1 + k2 q gives that n ≡ 1 (mod pq).

3 Problem Set
1. Compute gcd(539,273).

2. Prove that if a | b and a | c then a | (k1 b + k2 c) for any integers k1 and k2 . (This
is the exercise that fills in the missing gaps in the first two proofs above.)

3. Prove that if a | b and b | c, then a | c.

4. Using the Extended Euclidean Algorithm, find the inverse of 42 mod 79.

5. Factoring a 300-digit number using trial division would take around 10150 di-
visions. Assuming a computer is capable of doing 1 million (106 ) divisions per
second, how many seconds would it take the computer to complete factoring
by trial division? How about if you used 1 billion (109 ) such computers to do
the computation? To give a little context, the universe is believed to be on the
order of 1017 seconds old.

6. Suppose p is prime. Show that if a 6≡ 0 (mod p), then a has an inverse mod p.

7. Prove that if p and q are distinct primes, then gcd(p, q) = 1.

8. (a) Suppose p is a prime and p | ab. Prove that p | a or p | b.

(b) Show that the condition that p is prime in part (a) is necessary. That is,
find a counterexample to the proposition when p is composite.

9. (Challenge Problem) Prove Fermat’s Little Theorem. (Hint: Show that

a(2a) · · · (p − 1)a ≡ 1(2) · · · (p − 1) (mod p)

and then use this congruence together with 6. to prove the desired result.)