Polynomials aren’t the only types of formulas we will see. Here, we introduce two famous theorems about other types of congruences modulo \(p\) (a prime) that will come in very handy in the future.
where the exclamation point here indicates the factorial.
Proof.
If \(p=2\) this is very, very easy to check. So assume \(p\neq 2\text{,}\) hence \(p-1\) is even. Now we will think of all the numbers from \(1\) to \(p-1\text{,}\) which will be multiplied to make the factorial. (We will put the example \(p=11\) in bullets to help follow.)
For each \(n\) such that \(1 \lt n \lt p-1\text{,}\) we know that \(n\) has a unique inverse modulo \(p\text{.}\) Pair up all the numbers between (not including) 1 and \(p-1\) in this manner.
If \(p=11\text{,}\) we pair up \((2,6)\text{,}\)\((3,4)\text{,}\)\((5,9)\text{,}\) and \((7,8)\text{.}\)
Then multiplying out \((p-1)\) factorial, we can reorder the terms using the pairs, and notice much cancellation:
The only loose end is that perhaps some number pairs up with itself, which would mess up that all the numbers pair off nicely. However, in that case, \(a^2\equiv 1\) (mod \(p\)), so by definition \(p\mid (a-1)(a+1)\text{;}\) since \(p\) is a prime greater than two, it must divide one (and only one) of these factors (recall Lemma 6.3.6). In these cases \(a\equiv 1\) or \(a\equiv p-1\text{.}\) But we were not pairing off \(1\) or \(p-1\text{,}\) so this can’t happen.
Exercise 7.7.7 is to show that the conclusion of Wilson’s theorem fails for \(p=10\text{.}\) That is, that \((10-1)!\not\equiv -1\) (mod \(10\)). So does it work or not for other moduli?
Remark7.5.2.
See Exercise 7.7.11 once you have explored this for a while. The first known modern proofs were by Lagrange, but (while solving a general system of linear congruences, see [E.7.47]) Ibn Al-Haytham had already enunciated this statement by the eleventh century! For nice combinatorial proofs, see Subsection 7.8.2 or [E.7.27]. If you are really curious, see Wikipedia 3
for a generalization due to Gauss; a somewhat different approach to generalization is taken in [E.7.28].
Subsection7.5.2Fermat’s Little Theorem
If one explores a little with powers of numbers modulo \(p\) a prime, one usually notices some pattern of those powers. This is the best-known, and soon we’ll reinterpret it in a powerful way.
If \(\gcd(a,p)=1\) and \(p\) is prime, show that \(\{a,2a,3a,\ldots,(p-1)a,pa\}\) is a complete residue system (mod \(p\)).
That is, show that the set \(\{[a],[2a],[3a],\ldots,[pa]\}\) is the same as the complete set of residues \(\{[0],[1],[2],\ldots,[p-1]\}\text{,}\) though possibly in a different order.
If \(p\) is prime and \(p\) does not divide \(a\text{,}\) show that
Like with most important theorems, there are many other ways to prove it as well; in Section 7.8 we’ll provide a counting-based proof. See [E.7.40] for an analysis of interrelationship with a focus on mechanizing proof. We’ll see a more abstract approach after we introduce the concept of groups in Chapter 8; see Exercise 9.6.2.
So despite the innocuous appearance of this result as a corollary of another theorem, do not be fooled; it is incredibly powerful. As an example, it provides the primary tool in Fermat’s proof that \(2^{37}-1\) is not prime 5