6
$\begingroup$

Wilson's Theorem: $p$ is prime $\iff$ $(p-1)!\equiv -1\mod p$

I can use Wilson's theorem in questions, and I can follow the proof whereby factors of $(p-1)!$ are paired up with their (mod $p$) inverses, but I am struggling to gain further insight into the meaning of the theorem.

To try and find a more tangible expression, I tried rewriting the theorem as:

  • $p$ prime $\iff (p-1)!+1\equiv 0\mod p$
  • $p$ prime $\iff (p-1)!\equiv p-1\mod p$
  • $p$ prime $\iff p|(p-1)!+1 \implies (p-1)!+1=kp,k\in\mathbb{Z}$
  • $p$ prime $\iff (p-1)!=kp-1$

But I found none of these particularly instructive.

We have $(p-1)!$, containing no factors of $p$, which somehow evaluates to one less than a multiple of $p$ if and only if $p$ is prime. What can we say about $(m-1)!$ if $m$ is composite?

I guess what I'm asking for is some 'informal' or more conceptually based justification of this theorem.

$\endgroup$
  • 5
    $\begingroup$ If $m > 4$ is composite, then $(m-1)! \equiv 0 \pmod{m}$. Because if the smallest prime factor of $m$ is $p$, then $p$ and $m/p$ are $\leqslant m-1$, and unless $p^2 = m$, the two are distinct. If $m = p^2$ for an odd prime $p$, then $2p \leqslant m-1$, so again $m \mid (m-1)!$. $\endgroup$ – Daniel Fischer Aug 28 '13 at 12:29
5
$\begingroup$

When $m$ is composite, we can write $m=ab$ where $a,b<m$. If $a \ne b$, then $ab=m \mid (m-1)!$ as they are two distinct numbers less than $m$ and are seen in the factorial product.

If $a=b$, then $m=a^2$. If $m>2$, then $a<2a<m \implies 2a^2 \mid (m-1)! \implies m \mid (m-1)!$

If $a=2$, then $m=4$ for which $3! \equiv 2 \pmod{4}$

If $m$ is prime, the main intuition is that all the numbers from $1$ to $m-1$ are relatively prime to $m$ and can be paired into pairs of multiplicative inverses (congruence) except $1$ and $p-1$.

$\endgroup$
0
$\begingroup$

First let's understand why for prime $p$, $(p-1)!\equiv -1\mod p$. Understanding why that never happens for composite numbers actually ends up being a bit messy (although fundamentally not very complicated), so we'll cover that later.

The important intuition here is that the multiplicative group of $\mathbb Z/p\mathbb Z$ is cyclic. If you don't know what that means, it means that modulo a prime $p$, we can always find some number $r$ such that the sequence $1, r, r^2, ..., r^{p-2}$ runs through all of the non-zero values modulo $p$, and $r^{p-1}=1$. What this means is that multiplication modulo $p$ works just like addition modulo $p-1$, since $r^ar^b=r^{a+b}$, and as we have $r^{p-1}=1$, we have the familiar "wrap around" effect of modular addition: $r^{p-1+k}=r^k$. In other words, doing multiplication modulo $p$ on some numbers is just doing addition modulo $p-1$ on the exponents of those numbers. This means that any time we have a problem involving multiplying modulo a prime $p$, we can basically pretend it's a problem about addition modulo $p-1$.

In this translation scheme, $-1$ becomes $\frac{p-1}2$, since $r^{\frac{p-1}2}=-1\mod p$. So the question becomes: when we're doing addition modulo an even number $n$, why do we always have $1+2+3+...n-1=\frac n2\mod n$? We can use the same famous trick Gauss used to calculate $1+2+3+...+100$. Pair up $1$ with $n-1$, $2$ with $n-2$, and so on. All of these couples become $0$ modulo $n$, and only $\frac n 2$ remains.

This explains why the phenomenon occurs for prime numbers. To see why it never occurs for composite numbers we can reason one step at a time:

  1. First of all, the main reason why is that for most composite numbers $n$, there are two distinct numbers $a,b<n$ with $n=ab$, and those two numbers will show up in the factorial $(n-1)!$, guaranteeing that this factorial will be a multiple of $n$.

  2. But this logic doesn't work if $a=b$, and sometimes that's our only option, namely in the case of a number $n$ which is the square of a prime, $p^2$. The theorem continues to work in this case, and an example makes it clear why: $1\cdot2\cdot3\cdot4\cdot5\cdot6\cdot7\cdot8$ is a multiple of $9=3^2$ since $3$ and $6$ give us "two threes" in $8!$, giving us our $3^2$ and making $8!$ a multiple of $9$. In general, as long as $p>2$, $p$ and $2p$ will both appear in $(p^2-1)!$ and therefore that factorial will be a multiple of $p^2$.

  3. And when $p=2$, well, basically, we get lucky: it so happens that $(2^2-1)!$ is not $-1$ modulo $2^2$.

$\endgroup$
0
$\begingroup$

Edited heavily:

I'm not a fan of modulo math at this stage, but maybe what appears below might be helpful for the OP's request for "some 'informal' or more conceptually based justification of this theorem" (or maybe lead to something better from others).

Leaving aside math formatting technicalities, my current understanding of Wilson's Theorem (WT) is: p is prime iff [(p - 1)! + 1]/p = m where m is a positive integer.

It might be helpful to go back to Euclid's proof of infinitely many primes (as seen in https://en.wikipedia.org/wiki/Euclid%27s_theorem):

"Several variations on Euclid's proof exist, including the following:

The factorial n! of a positive integer n is divisible by every integer from 2 to n, as it is the product of all of them. Hence, n! + 1 is not divisible by any of the integers from 2 to n, inclusive (it gives a remainder of 1 when divided by each). Hence n! + 1 is either prime or divisible by a prime larger than n. In either case, for every positive integer n, there is at least one prime bigger than n. The conclusion is that the number of primes is infinite."

Whereas this proof indicates there is at least one prime > n up to (n! + 1), WT establishes that where a prime p happens to follow n, p will always have the 'magical' property of being evenly divisible into (n! + 1). I suppose that might very well be the part that the OP wanted elucidated in a less mathematical manner; but, unfortunately, I'm actually finding it difficult to translate what I'm seeing on paper etc into a proper descriptive form. I can "see" that the OP's query about (m - 1)! will be interesting to try examining without the modulo stuff, but that will have to wait.

The only other potentially helpful insight that currently comes to mind is the primes seeming to be the perfect example of the expression "A place for everything, and everything in its place". It's as if the whole number system was complete at the outset, such that the way things move forward seems to be partly based on what will happen later rather than being entirely based on what has happened in the past.

A big mistake in my prior answer that Jack M addressed was erroneously thinking (n! + 1) might yield only a single new prime that divides evenly. I subsequently tried something like 15! and confirmed three. I'll still avoid modulo math if possible, but at least I can come back here and read up on it if that's where my work leads.

Supplement 1:

With respect to the OP’s (m - 1)! query (even though he or she probably won't be back), here’s a hands-on approach that might be useful. Grab some paper and start writing the numbers. 2 might be thinking “What good is 1 anyway?”. 3 hits it off with 2 and they produce 6. Then 4 comes along to make 24, and we’ll skip over its idiosyncrasy. 5 sees a few strangers but likes to play, so we’re up to 120. Since you can see a prior 6, the next 6 presumably takes comfort in knowing someone’s cleared the way and happily ups things to 720. I'm not sure if 7 feels left out or superior, but it doesn't hold a grudge and brings the proceedings to 5,040. 8 already sees a buddy in 2x4, and our happy bunch is up to 40,320. 9 might find it odd not seeing both of its most familiar progenitors, but 3x6 are waiting to welcome it. ...

Supplement 2:

Building on the “intuition” aspect of the heading of the OP’s question, I haven’t regarded modulo math to be an important enough tool to put in my limited toolbox, but I have an appreciation of remainders. It occurred to me that in order for (p - 1)! to have a ‘magical’ property, there must be some kind of “overflow” from (p - 2)! . For the unfamiliar but interested, I would encourage you to give some thought to this. For those who want to dive into a pithy explanation of the infrequently mentioned extension of WT, see http://www.numericana.com/wilson.htm

$\endgroup$
  • $\begingroup$ I don't think you quite understand what Wilson's theorem states. It states that for prime $p$, $(p-1)!$ is one less than a multiple of $p$. $\endgroup$ – Jack M Feb 18 at 17:54
  • $\begingroup$ @Jack M, It looks like you're saying (p-1)! + 1 = mp, which is the same as [(p-1)! + 1]/p = m. The OP's issue was "I guess what I'm asking for is some 'informal' or more conceptually based justification of this theorem." $\endgroup$ – PrimeNumberHobbyist Feb 18 at 18:12
  • $\begingroup$ @Jack M, does your issue relate to the Wiki quote saying n! + 1 could be a prime whereas Wilson's Theorem is supposed to be for m > 1 ? $\endgroup$ – PrimeNumberHobbyist Feb 18 at 18:30
  • $\begingroup$ No, it's just that there isn't much of a connection between the two statements. WT states that if $p$ is prime, $(p-1)!+1$ is a multiple of the prime $p$. In Euclid's proof it's true that there is a line which claims that $n!+1$ is a multiple of some prime, but other than that superficial similarity (both are talking about one more than a factorial being divisible by something) there doesn't seem to be any connection. $\endgroup$ – Jack M Feb 18 at 19:13
  • $\begingroup$ @Jack M, okay, I see my silliness now. WT results in single prime while n! + 1 only guarantees unique prime where n = p - 1 (being WT). I'll see if I can salvage my answer. $\endgroup$ – PrimeNumberHobbyist Feb 19 at 0:42

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.