Motivation
Multiplying every nonzero residue modulo gives , and . So the product leaves remainder , which is the residue class of . Modulo the same happens: . Modulo , however, leaves remainder .
This chapter explains these outcomes. The key observation is structural. In a multiplicative system where every element has an inverse, a product over all elements can be regrouped into inverse pairs, and each pair contributes . Only the elements that are their own inverses survive. So the problem reduces to locating the solutions of . Whether those solutions are just depends on whether arithmetic modulo allows cancellation, which is exactly where primes and composites part ways.
Throughout, is an integer. Arithmetic modulo takes place in , which is a commutative ring but need not be a field. We write for equality of residue classes. When we say that an integer "is" a residue such as , we mean its least nonnegative residue: the unique with and . Thus is an integer, is its least nonnegative residue modulo , and names the same class. These are different objects, and they should not be confused.
Definitions
Definition 2.2.1
(Units and the unit group)
A residue is a unit if there is with . Such a is an inverse of . The set of units, under multiplication, is denoted , or . It is a finite abelian group. A residue is a unit exactly when .
Inverses are unique. If and , then . This uniqueness is what makes "pair each element with its inverse" well defined.
Definition 2.2.2
(Self-inverse element and zero divisor)
A unit is self-inverse if . A nonzero residue is a zero divisor if there is a nonzero residue with .
If is prime, then has no zero divisors. This follows from Euclid's lemma: if , then or . Also, every nonzero residue modulo is a unit, by Bézout's identity applied to . In contrast, modulo we have , so and are zero divisors.
The general pairing principle
Theorem 2.2.3
(Product of a finite abelian group)
Let be a finite abelian group, written multiplicatively. Then the product of all elements of equals the product of the self-inverse elements of .
Proof
(Proof by inverse pairing)
The map is a bijection of that is its own inverse. So splits into disjoint classes of the form . A class has two elements when , and one element when .
Because is abelian, the full product may be computed in any order. We therefore group it class by class. Each two-element class contributes . Each one-element class contributes its single self-inverse element. Hence the full product equals the product of the self-inverse elements.
Commutativity is used essentially here: without it, rearranging factors would not be legitimate.
Applied to , the principle shows that computing reduces to understanding the solutions of . It does not say how many solutions there are; that is an arithmetic question about .
Theorem 2.2.4
(Square roots of one modulo a prime)
Let be prime. The solutions of are exactly and . When these two coincide, so there is exactly one solution. When is odd they are distinct, so there are exactly two.
Proof
(Cancellation in a field)
If , then . Since has no zero divisors, one factor is zero, so or . Both values do satisfy the equation.
Now compare the two roots. We have exactly when , that is, when . So for the only root is . For odd the roots and are distinct.
Wilson's theorem
Theorem 2.2.5
(Wilson's theorem)
For an integer ,
Proof
(Forward direction: primes)
Let be prime. Then , so is the product of all elements of .
By the pairing principle, this product equals the product of the self-inverse elements. These are the roots of .
- If is odd, the roots are and . Their product is , so .
- If , the only root is . So , and .
In both cases .
Proof
(Converse: composites fail directly)
Suppose is composite, so it has a divisor with . Since , the integer appears among the factors of , so .
Suppose, for contradiction, that . Since , congruence modulo implies congruence modulo . So . But . Therefore , which means . This contradicts .
Proof X-ray
What each direction of Wilson's theorem really uses
The two directions rest on different facts. The forward direction uses primality twice. First, every residue is a unit, so is exactly the product of all elements of and the pairing principle applies. Second, the absence of zero divisors leaves only and as self-inverse elements, so the surviving product is ; for the single survivor happens to equal . If either fact is missing, the conclusion changes. For the four units are self-inverse and the product of all units is , as computed in the worked examples. Moreover also contains the non-units , and in fact .
The converse uses no group theory at all. Its single move is that a proper divisor of occurs as a factor of ; reducing the assumed congruence modulo gives . Put differently, for composite the factorial shares the factor with , so it is not a unit modulo , whereas is a unit. This is why the converse closes in one line, and why the next theorem can determine the composite residue exactly.
The converse needs only one proper divisor, and it never touches the unit group. A sharper statement is available.
Theorem 2.2.6
(Factorials modulo composite integers)
If is composite and , then . If , then .
Proof
(Two distinct factors below )
For , compute directly: .
Now let be composite. Let be its smallest prime divisor, and write with . Then .
Case . Then , and both lie strictly between and . Being distinct integers in , they occur as separate factors of . Hence divides .
Case , so . We cannot use twice, since it appears only once among . Because , we have , and so . Thus and are distinct integers in . Their product divides , and therefore .
The case is precisely where this fails: gives , which is not below .
Proof X-ray
Why a prime square needs a second multiple
The aim is to write , or a multiple of , as a product of distinct integers from , because each such integer occurs only once in . When with , the two factors themselves do this. Taking to be the smallest prime divisor only orders them, , so that already means . The real difficulty is a prime square , where the factor is available once only. The proof replaces the second copy of by . This is a different factor below exactly when , that is, when , and the product is a multiple of .
The hypothesis is used only at this point: the only composite number of the form with is . The boundary is sharp, since . By contrast, is not a square and falls under the first case with the distinct factors and .
So for every , the residue of is if is prime, if , and otherwise.
A characterization, not an algorithm
Wilson's theorem gives an exact test for primality, but it is not an efficient one. Complexity of arithmetic is measured in bit operations, as a function of the input length . Computing directly takes about multiplications. After reducing modulo at each step, schoolbook multiplication of -bit numbers costs at most bit operations per multiplication. The resulting upper bound is ; the individual multiplication steps already make this direct method exponential in . Without reduction, the integer itself has roughly bits, so even writing it down is exponential in .
For a -bit , the step count alone is around . Wilson's theorem is therefore a structural characterization of the primes, valuable for proofs, and not a practical primality test.
Half-factorials and the square root of minus one
Theorem 2.2.7
(Squared half-factorial)
Let be an odd prime and . Then
Proof
(Pair with )
The residues split into the pairs for , with . Therefore
By Wilson's theorem, . Multiply both sides by and use . This gives .
This statement concerns , not itself. When , the number is even and . So is an explicit square root of , and for it is neither nor . When , the number is odd, so and . Both signs genuinely occur. For example, , while , so .
To show that has no square root when , we prove Fermat's little theorem rather than assume it.
Theorem 2.2.8
(Fermat's little theorem)
If is prime and , then .
Proof
(Multiplication permutes the units)
Consider the map on . It sends units to units. It is injective: if , then multiplying by gives . A finite set mapped injectively into itself is mapped bijectively, so the map permutes .
Hence the products agree:
As a product of units, is a unit, so we may cancel it. This gives . No appeal to Wilson's theorem is needed.
Theorem 2.2.9
(When minus one is a square)
Let be an odd prime. If , then satisfies . If , the congruence has no solution.
Proof
(Parity of decides)
The first claim is the squared half-factorial theorem with even.
For the second, suppose . Then , so Fermat's theorem applies. We get , because is odd. So , which means . This is impossible for odd .
Composite moduli: more square roots of one
For composite , the pairing principle still applies to . What fails is the field argument. Modulo , all four units are self-inverse: , , and are each . The same holds for . In , all eight units are self-inverse; for instance, , , and . Note also that the product of the units of is a different quantity from when is composite, because includes non-units.
Worked examples
Worked example 2.2.10
(Wilson's theorem for )
The inverse pairs modulo are and . The self-inverse elements are and . So
This agrees with the integer computation .
Worked example 2.2.11
(Wilson's theorem and a square root of for )
The inverse pairs are:
Each is , since , , , and . With the self-inverse elements and , we get , matching the remainder found in the Motivation.
Here , and , so . Then . So , and likewise , is a square root of modulo .
Worked example 2.2.12
(Composite moduli )
For : . The residue is neither nor , so is an exceptional case.
For : the square case uses the distinct factors and of . Their product is , so . Indeed .
For : the distinct factors and appear in , so .
Worked example 2.2.13
(Extra square roots of 1 modulo 15)
We have . Squaring gives:
So there are four self-inverse units: . The remaining units pair off as and .
By the pairing principle, the product of all units is
The result is , not .
Common mistakes
Counterexample mode
Canceling through a zero divisor
Mistaken claim. "From we get ."
Why it fails. The no-zero-divisors argument is valid in an integral domain; in a ring with zero divisors it cannot be used in general. Modulo , take : then , yet . Modulo , take : then . The product of two nonzero residues can vanish, so neither factor need be zero.
Repair. The implication is valid when is prime, because has no zero divisors. For composite the roots of must be found another way, for example by solving modulo each prime-power factor and combining the results.
The remaining two pitfalls are not about cancellation. They concern which object is being computed: the half-factorial rather than its square, and an integer rather than its residue class.
Counterexample mode
Assuming the half-factorial is always $\pm1$
Mistaken claim. "The half-factorial is always modulo ."
Why it fails. Modulo , we found , which is neither nor . Only is always .
Common mistake
(Treating the residue as the integer)
Mistaken claim. "Since , we have ."
Why it fails. The integer equals . The residue , or equivalently , describes only its class modulo .
Exercises
Quick check
(Let . Compute and verify .)
Compute first.
Solution · Answer
Here and . Then . Since , the predicted value is , which agrees. Because , the residue is a square root of . So is , since .
Quick check
(Verify Wilson's theorem for by inverse pairing, then compute .)
Find the inverse of each residue from to modulo .
Solution
The inverse pairs modulo are:
Each is , since , , and . With the self-inverse elements and , we get .
For the half-factorial, and , so . This is consistent with . Here happens to be ; for it is .
Quick check
(Show that using the square case of the classification. Identify the two factors used.)
Use the case with .
Solution
We have , and the smallest prime divisor is . The factors and are distinct and both lie below , so both occur in . Their product is . Hence , so .
The factor alone would not suffice, because it appears only once among .
Quick check
(Compute the product of the elements of and explain why it is not .)
Square each unit modulo .
Solution
We have , and every element is self-inverse. The product is .
The prime argument fails because has four roots here, not two. Separately, , as the classification predicts.
Quick check
(Explain why the convention is needed in Wilson's theorem.)
Ask what congruence modulo means.
Solution · Answer
For , every integer is congruent to every other modulo . So holds, yet is not prime. The ring is the zero ring, in which . Neither the forward argument (which requires or ) nor the meaning of "prime" applies. Excluding keeps the equivalence true.
Quick check
(Prove Fermat's little theorem by the permutation argument. Check the boundary case , and explain why the no-root argument for needs odd.)
Show first that multiplication by is injective on .
Solution
General proof. Let . Then is injective on , since we may cancel by . So it is a permutation of . Equating the products gives , and canceling the unit yields .
Boundary case . Here , the permutation is the identity, and for odd . The theorem holds.
Why the no-root argument needs odd. That argument derives and calls it a contradiction. Modulo , however, is true, and indeed . So does have a square root modulo , and the contradiction disappears.
Quick check
(Find a square root of modulo from a half-factorial, and find all square roots.)
Compute modulo , then use that is prime.
Solution
Here and . Then .
If , then . Since is prime, there are no zero divisors, so or . Check: . The square roots of modulo are exactly and .