Number Theory: A Very Short Introduction

can be counted in p ways, depending on where we start: for example, the necklace in Figure 28 arises from five different strings of beads,

28. A necklace with five beads.

where R, B, and Y stand for red, blue, and yellow.

How many different necklaces can there be? Because there are p beads in up to a colours, there are a^p possible strings of beads, or strings when we exclude the a single-colour ones (such as RRRRR) that can each be coloured in only one way. But each necklace arises from p different strings, and so the number of different necklaces is . Because this must be an integer, must be divisible by p—that is, , which is Fermat’s little theorem.Shuffling cards

An amusing application of Fermat’s result is to the shuffling of cards (sometimes called ‘Faro shuffling’). Starting with a normal pack of cards we first cut it into two piles, so that the cards in one pile are in positions 1 to 26 and those in the other pile are in positions 27 to 52. We now shuffle the cards so that the cards in positions 1, 2, 3, …, 26 are moved to positions 2, 4, 6, …, 52, and the cards in positions 27, 28, 29, …, 52 are moved to positions 1, 3, 5, …, 51, giving the new ordering

(see Figure 29). It follows, as we can easily check, that for each a, the card initially in position a has moved to the new position 2a (mod 53).

29. Shuffling cards.

How many shuffles are needed to restore the pack of cards to its original order? After n shuffles, the card initially in position a has moved to position (mod 53), so after the pack has been restored to its original order, for all numbers a. Now gcd , so we can cancel the a, giving us . But by Fermat’s little theorem, , so the pack is certainly restored to its original order after 52 shuffles.

But can this happen earlier? If so, the number of shuffles must be a factor of 52, by our remark following the first statement of Fermat’s result—that is, 2, 4, 13, or 26. But, after some calculation, we find that

None of these works, so the order of the cards is restored for the first time after 52 shuffles.

What happens if we now add two Jokers to the pack, making 54 cards in total? Carrying out a similar analysis, we seek the smallest value of n for which . Now is not prime, and we can no longer apply Fermat’s result directly. But Fermat’s little theorem tells us that , and so . It also tells us that , and so . Combining these results (which we can, because , we deduce that , and so the order of the cards is certainly restored after 20 shuffles.

Can this happen earlier? If so, the number of shuffles must be a factor of 20—that is, 2, 4, 5, or 10. But

None of these works, so the order of the cards is restored for the first time after 20 shuffles.

Generalizing Fermat’s little theorem

We’ve presented Fermat’s little theorem, that if p is a prime number and a is any integer that isn’t divisible by p, then . But what happens if p is replaced by a composite number? Is Fermat’s result still true, and if not, can we adapt it so that it holds in this more general case?

To show that Fermat’s result can fail when the modulus is not prime, let’s look at congruences (mod 10), and let (which is coprime to 10). Then , which is not congruent to 1 (mod 10).Euler’s φ-function

Before we answer the questions above, we’ll first need to introduce what Euler called the ‘totient function’; the choice of the Greek letter φ (phi) to denote it was made by Gauss in 1801. We define it as follows:

For each positive integer n, let φ(n) be the number of positive integers up to n that are coprime to n—that is, the number of positive integers for which .

For example, , because the numbers (up to 10) that are coprime to 10 are 1, 3, 7, and 9; likewise, , where the relevant integers are 1, 3, 7, 9, 11, 13, 17, and 19. A table of values of φ(n) for appears in Table 5:

Table 5. Values of φ(n), for

There are a few things to notice here. For a start,

If p is a prime number, then ,

because every number up to p is coprime to p, except for p itself.

Also, , because every number up to p² is counted, except for the p multiples of p: for example, , because we count every number up to 9 except for 3, 6, and 9. Likewise, for any power p^e,

For example,

Also, if p and q are different primes, then

because we need to discount the p multiples of q and the q multiples of p, and then restore the number pq (which we had discounted twice). We’ll need this result later.

More generally, if , where a and b are coprime, then : for example, , and so

This multiplicative idea holds in general: if n is any product of numbers that are coprime in pairs, then φ(n) is the product of the φ-values of the separate numbers: for example,

if , then

We can also rewrite this product as

or as

and both of these forms are useful. In general,