Number Theory: A Very Short Introduction

if the number n is written in canonical form as a product of primes—that is, if , then

This can also be written as

for example, 100 has prime factors 2 and 5, and so

as we saw earlier.

These formulas can be used for calculation, and also to prove some general results about φ(n). For example, we can prove that

If , then φ(n) is even,

as indicated in our table of φ-values. This is because either n is a power of 2 (larger than 2) or it has an odd prime factor p. In the former case, if , where , then , which is even. In the latter case, the formula for φ(n) must include the factor which is even, and so φ(n) is even.

But some even numbers can never appear as φ-values: for example, our table includes the even numbers 2, 4, 6, 8, 10, 12, 16, and 18, but not 14. To see why, suppose that . Now if n has a prime factor p, then must divide 14, and this can happen only when p is 2 or 3. So n must be 2^r, or 3^s, or , for some numbers r and s, and so , or , or , respectively. But none of these has 7 as a factor, and so φ(n) cannot be 14.

Euler’s φ-function has some interesting properties. For example, what do we get if we’re given a number n and we add up the φ-values of all its factors? If , then its factors are 1, 2, 5, and 10, and their sum is

More generally, it turns out that if we add up the φ-values of the factors of any number n, then we get n itself.Euler’s theorem

We’ll now return to the task of extending Fermat’s little theorem about the powers of a number (mod p) to powers of a number (mod n), where n may be composite. When we introduced Fermat’s result we started by looking at the powers of certain numbers (mod 7). We’ll now imitate the process by looking at the first few powers of certain numbers (mod 9):

It turns out that, apart from the powers of 0, 3, and 6, every 6th power is 1.

Now , and we can summarize this by saying:

If a is coprime to 9, then .

This result is a special case of the result we were seeking:

Euler’s theorem: If n is a positive integer, and if a is any integer with , then .

For example, if and , then and , and we deduce that , which is correct because

To see why Euler’s theorem is true, let’s imitate what we did earlier and look at the first few positive multiples of the numbers coprime to 9—that is, 1, 2, 4, 5, 7, and 8—and reduce them (mod 9). Multiplying these numbers by 4 gives 4, 8, 16, 20, 28, 32, and reducing them (mod 9) gives 4, 8, 7, 2, 1, 5. Likewise, multiplying them by 7 gives 7, 14, 28, 35, 49, 56, and reducing them (mod 9) gives 7, 5, 1, 8, 4, 2. In each case we get a rearrangement of the numbers 1, 2, 4, 5, 7, and 8.

To prove Euler’s theorem in this case, we’ll mimic the proof of Fermat’s little theorem. Multiplying the numbers 1, 2, 4, 5, 7, and 8 by a (where ) gives 1a, 2a, 4a, 5a, 7a, and 8a, and reducing these (mod 9) gives 1, 2, 4, 5, 7, and 8, though possibly in a different order. So, on multiplying them all together, we get

Cancelling the numbers 1, 2, 4, 5, 7, and 8 (which are all coprime to 9) then gives , as we saw above.

The general proof is similar. We begin by listing the φ(n) numbers up to n that are coprime to n—we’ll call them b₁, b₂, …, b_k, where . We then multiply them by a, to give the multiples b₁a, b₂a, …, b_ka, and reduce them (mod n). The results will all be different, and must therefore be b₁, b₂, …, b_k in some order.

Multiplying these multiples of a together and equating the two products, as above, gives

Cancelling the terms b₁, b₂, …, b_k (which are all coprime to n) then gives

as we wished to prove.

We conclude this section by noting that if n is a prime number p, then , and we get , which is Fermat’s little theorem, as we’d expect.

Factorizing large numbers

Before we see how Euler’s theorem makes its appearance in cryptography, let’s consider briefly the subject of trying to factorize a number into its prime factors.

Many real-life processes are irreversible: for example, it’s easy to squeeze toothpaste from a tube but difficult to reverse the operation, and it’s easy to break an egg but impossible to ‘unbreak’ it, especially if it’s Humpty Dumpty.

Another example is the factorization of large numbers. It’s generally straightforward to multiply two primes together, but if we’re given the product, then it’s often more difficult to factorize it into its two prime constituents: for example, we can easily multiply 23 and 89 to give 2047, but given the number 2047 it may take us some time to find its factors by hand. If the primes are large—say, 250 digits—then their product can easily be calculated by machine, but no current computer can factorize their 500-digit product in a reasonable amount of time.

A traditional method for testing whether a given number n is prime is due to Fermat, and works particularly well when n is the product of two numbers that are close to each other. The