Chapter 2.4, Problem 40MS

A prime magic trick. Pick a prime number and call it p. Now pick any natural number smaller than p and call it a. Compute $a^{p-1}$ mod p. What do you notice? You can use this observation as the basis for a magic trick. Have a friend think of a natural number less than p (but keep it to him- or herself). Tell that person that you will predict and write what the remainder will be when $a^{p-1}$ is divided by p. Write your answer and seal it in an envelope, and then ask what the person’s number was. Now, to your friend’s amazement, compute the remainder when $a^{p-1}$ is divided by p and reveal the hidden prediction. Record your friend’s reaction. The next section uses this observation in a powerful way. Check it out.