| | |
We've seen how to solve linear congruences using the Euclidean Algorithm, what if we now wanted to look at higher-order congruences -- ones that involve squares, cubes, and other higher powers of a variable in a given modulus. How do higher powers behave$\pmod{m}$?
Consider $a, a^2, a^3, ... \pmod{m}$ for various values of $a$ and $m$, as shown below. Do you notice anything?
$$\begin{array}{ccc} \begin{array}{c||c|c|c} a & a^2 & a^3 & a^4\\\hline 0 & 0 & 0 & 0\\\hline 1 & 1 & 1 & 1\\\hline 2 & 1 & 2 & 1\\ \end{array} & \quad & \begin{array}{c||c|c|c|c|c} a & a^2 & a^3 & a^4 & a^5 & a^6\\\hline 0 & 0 & 0 & 0 & 0 & 0\\\hline 1 & 1 & 1 & 1 & 1 & 1\\\hline 2 & 4 & 3 & 1 & 2 & 4\\\hline 3 & 4 & 2 & 1 & 3 & 4\\\hline 4 & 1 & 4 & 1 & 4 & 1 \end{array}\\ a^k \pmod{3} & \quad & a^k \pmod{5} \end{array}$$ $$\begin{array}{c} \begin{array}{c||c|c|c|c|c|c|c} a & a^2 & a^3 & a^4 & a^5 & a^6 & a^7 & a^8\\\hline 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0\\\hline 1 & 1 & 1 & 1 & 1 & 1 & 1 & 1\\\hline 2 & 4 & 1 & 2 & 4 & 1 & 2 & 4\\\hline 3 & 2 & 6 & 4 & 5 & 1 & 3 & 2\\\hline 4 & 2 & 1 & 4 & 2 & 1 & 4 & 2\\\hline 5 & 4 & 6 & 2 & 3 & 1 & 5 & 4\\\hline 6 & 1 & 6 & 1 & 6 & 1 & 6 & 1 \end{array}\\ a^k \pmod{7} \end{array}$$
One thing that should stand out is that each has a column almost entirely filled with 1's (with the exception of the very top entry, which is zero). Furthermore, there seems to be a pattern as to which column this is. This observation is known as Fermat's Little Theorem (although it was first proven by Leibniz).
| Fermat's Little Theorem For every prime $p$ and $a \not\equiv 0 \pmod{p}$, $$a^{p-1} \equiv 1 \pmod{p}$$ |
Suppose we consider $3 \cdot x$ for each possible value$\pmod{7}$ not congruent to zero, as shown in the table below $$\begin{array}{c||c|c|c|c|c|c} x & 1 & 2 & 3 & 4 & 5 & 6\\\hline 3 \cdot x & 3 & 6 & 2 & 5 & 1 & 4 \end{array} \pmod{7}$$ Notice how the numbers in the second row above are the exact same values as those seen in the first row, just not in the same order. Some experimentation suggests this is a phenomenon not unique to just 3 and$\pmod{7}$. For example, $$\begin{array}{c||c|c|c|c|c|c} x & 1 & 2 & 3 & 4\\\hline 2 \cdot x & 2 & 4 & 1 & 3\\ \end{array} \pmod{5}$$ and $$\begin{array}{c||c|c|c|c|c|c|c|c|c|c} x & 1 & 2 & 3 & 4 & 5 & 6 & 7 & 8 & 9 & 10\\\hline 8 \cdot x & 8 & 5 & 2 & 10 & 7 & 4 & 1 & 9 & 6 & 3\\ \end{array} \pmod{11}$$ It remains to prove this, but if it is true, notice what it affords us. In$\pmod{7}$, we have $$(3 \cdot 1)(3 \cdot 2)(3 \cdot 3) \cdots (3 \cdot 6) \equiv 1 \cdot 2 \cdot 3 \cdots 6 \pmod{7}$$ which leads to $$3^6 \cdot 6! \equiv 6! \pmod{7}$$ and noting that $1, 2, 3, ..., 6$ are all relatively prime to 7, which allows them to be cancelled from both sides, we arrive at $$3^6 \equiv 1 \pmod{7}$$ This is a specific instance of the result we hope to prove.
More generally, if for some prime $p$ and $a \not\equiv 0\pmod{p}$, we have $a, 2a, 3a, ..., (p-1)a\pmod{p}$ identical in values, but possibly not order, to $1, 2, 3, ..., (p-1)\pmod{p}$, then $$(a \cdot 1)(a \cdot 2)(a \cdot 3) \cdots (a \cdot (p-1)) \equiv 1 \cdot 2 \cdot 3 \cdots (p-1) \pmod{p}$$ which similarly gives us $$a^{p-1} (p-1)! \equiv (p-1)! \pmod{p}$$ As $1,2,3,...,(p-1)$ are all relatively prime to $p$, we are free to cancel these factors from both sides as was done above to arrive at $$a^{p-1} \equiv 1 \pmod{p},$$ which is what we hope to show.
So it all comes down to whether or not we can prove that $a, 2a, 3a, ..., (p-1)a\pmod{p}$ are identical in values, but possibly not order, to $1, 2, 3, ..., (p-1)\pmod{p}$.
First, note that we have $(p-1)$ values in the list $a, 2a, 3a, ..., (p-1)a\pmod{p}$. Since there are only $(p-1)$ distinct nonzero values$\pmod{p}$, showing all of the multiples of $a$ above are distinct and nonzero should be sufficient to guarantee the result.
Showing that these values are nonzero is trivial as $a \not\equiv 0\pmod{p}$.
To show they are distinct, suppose any two distinct values above are congruent$\pmod{p}$: $$i \cdot a \equiv j \cdot a\pmod{p}$$ Since $a \not\equiv 0\pmod{p}$ and $p$ is prime, $a$ must be relatively prime to $p$, which allows us to cancel $a$ from both sides to obtain $i \equiv j\pmod{p}$ and consequently $$i-j \equiv 0\pmod{p}$$ Now consider the size of $|i-j|$. Since $1 \le i,j \le (p-1)$, it must be true that $|i-j| \lt p-1$. As zero is the only multiple of $p$ with magnitude less than $(p-1)$, we have $i=j$, which then contradicts the fact that $ia$ and $ja$ were distinct values $\pmod{p}$.
This last observation concludes the proof.