The smallest power congruent to 1: Fermat's theorem

We will begin with a prime modulus p. Choose any a from 1 to p-1and consider the multiples

$$1\cdot a, \; 2\cdot a,\; 3\cdot a, \; \dotsb \; , \; (p-1)a$$

Remembering our experience with multiplicative ciphers, we know that these numbers are all different modulo p. That is, modulo p, these are precisely all the numbers from 1 to p-1.

Here is the trick! Multiply all the numbers together and the result must be the same as multiplying all the numbers from 1 to p-1. Thus,

$$(a)(2a)(3a)\dotsb((p-1)a) \equiv (p-1)! \pmod p$$

The left side also has (p-1)! in it as well. After some rearrangement

$$(p-1)! \; a^{p-1} \equiv (p-1)! \pmod p$$

The prime p does not divide (p-1)!. That means that we can cancel it from both sides of the congruence, and at last obtain

Fermat's Theorem: For any number a relatively prime to the prime p, we have

$$a^{p-1} \equiv 1 \pmod p$$

By this theorem, we can conclude immediately that $3^{18}\equiv 1 \pmod {19}$. As a word of caution, it may turn out that a smaller power will produce 1. For example, if a=9, then $9^9 = (3^2)^9 = 3^{18}\equiv 1 \pmod {19}$. So a smaller power of 9 is congruent to 1 mod 19.

For some further examples, you can appreciate Fermat's theorem by checking $2^6 = 64 =9\cdot 7 +1 \equiv 1\pmod 7$, $2^{10} = 1024 \equiv 1 \pmod {11}$, etc. It really is amazing.

It is a little unusual that the smallest power of 3 that is 1 mod 19 is the largest that can be under Fermat's theorem. Such a number is called a primitive root modulo p. That is, a primitive root a has the property that the smallest k for which $a^k\equiv 1 \pmod p$ is p-1. A subtle and extremely important fact is that every prime number p has some primitive root g. Then the powers g⁰, g¹, g², ... , g^p-2, cover every congruence class from 1 to p-1.

Euler discovered the generalization of Fermat's theorem to an arbitrary modulus m. The trick is to consider only numbers a which are relatively prime to m. Then similar reasoning leads to:

Euler's Theorem: For any a relatively prime to m, we have

$$a^{\phi(m)} \equiv 1 \pmod m$$

In the case m=12, that would imply $5^4 \equiv 1 \pmod {12}$. In fact, we already observed that the square of any such a is 1 mod 12. There is then no primitive root for 12.