# Can somebody simply explain Wilson's theorem (for a 13 year old)

I am Rohan Kapur. This is my first time posting on the Mathematics site, although I am quite active on StackOverflow, the programming site. I am doing a Islamic Maths assignment at the moment for Humanities, and I came across the historical fact that Ibn al-Haytham proved Wilson’s theorem. I have seen on this wiki page: Wilson's theorem Wiki

a natural number $n > 1$ is a prime number if and only if: ￼

$(n-1)! \equiv -1 \pmod n$

So I know what $(n-1)!$ means, its a factorial. But what does $\equiv$ with three lines there $(\mathrm{mod}\ n)$ mean. How does that mean its a prime number? $5$ is a prime number, ok.

$5-1!$ is $4 \cdot 3 \cdot 2\cdot 1$

that equals $24$

and then $24$, $\equiv$ with three lines again, $(\mathrm{mod}\ n)$.

What does this mean? Been looking for a simple answer, but can't find one...

UPDATE

Yes, I know what modular arithmetic is. It is a system where a number wraps around after a certain value in a loop. Like a clock time for example, but what does this mean in proving that the number is a prime.

-
Have a look here for an explanation of modular arithmetic. – Tara B May 17 '12 at 11:26
yes, i read that. I understand what it means, just not how it applies to this situation and how it can help prove whether a number is prime or not – MCKapur May 17 '12 at 11:32
Oh, I assumed you had not read it, since you asked what '= with three lines (mod n)' means. – Tara B May 17 '12 at 11:34
can you answer my previous question? yes, i read that. I understand what it means, just not how it applies to this situation and how it can help prove whether a number is prime or not – Rohan Kapur 18 mins ago – MCKapur May 17 '12 at 11:51
In that case you could probably get a better answer by removing the sentence "But what does = with three lines there (mod n) mean" from the question, since it makes it look like you know less than you do. By the way, to get $\equiv$, you can type \$\equiv\$. – Tara B May 17 '12 at 11:54

Wilson's Theorem, written without congruences, says that $n$ is prime if and only if $(n-1)!+1$ is a multiple of $n$.

Let's see that it gives us the right answers for $n=4$ and $n=5$.

$n=4$: $(n-1)!+1$ is $3!+1$ which is 7 which is not a multiple of 4, and 4 is not prime - good!

$n=5$: $(n-1)!+!$ is $4!+1$ which is 25 which is a multiple of 5, and 5 is prime - good!

So, it works for $n=4$ and $n=5$.

Now instead of proving it works for every prime, I'll show you why it works for 11, and claim the same idea always works.

For $n=11$, we have to look at $10!$, which is $(1)(2)(3)(4)(5)(6)(7)(8)(9)(10)$. I'll rearrange that as $(1)((2)(6))((3)(4))((5)(9))((7)(8))(10)$, which is $(1)(12)(12)(45)(56)(10)$. Now notice that each of those numbers, $1,12,12,45,56$, is 1 more than a multiple of 11. That implies that when you multiply them together, you get 1 more than a multiple of 11. But the number I didn't account for, 10, is one less than a multiple of 11. So when you multiply that in, you get 1 less than a multiple of 11, as Wilson's Theorem asserts.

Well, what happens for $n=11$ happens for every prime, although it takes a bit of work to establish it: you can always pair off all the numbers so that each pair multiplies to 1 more than a multiple of $n$, except the last number, $n-1$, which is one less than a multiple of $n$. So the whole $(n-1)!$ is one less than a multiple of $n$, as Wilson says.

-
thank you this is a very valuable answer... – MCKapur May 17 '12 at 12:38
Very nicely explained. I'm quite glad I didn't have time to type a proper answer, since I wouldn't have done it as well anyway. – Tara B May 17 '12 at 12:43

I don't have time to answer your question fully right now, because I'm about to go to lunch. But why don't you try, for a start, showing that for any composite $n$ (except $n=4$), $(n-1)!$ is divisible by $n$. (This is the same as saying $(n-1)! \equiv 0 \pmod{n}$.) This, along with the observation that $(4-1)!\equiv 2 \pmod{4}$, gives you one half of the proof.

The other half is harder, and uses some things which I expect you don't know yet. But let me know whether you can get the first half for a start. I'll be back in about half an hour.

-
Ok, Im still kind of stuck. If n is 4, (4-1)! would be 6. 6/1 works, 6/2 works, 6/3 works, but 6/4 doesn't work.... but 4 isn't prime.... and for if n was 5, (5-1)! would be 24. 24/1 works, 24/2 works, 24/3 works, 24/4 works, 24/5 however doesn't work... and that is prime... So I'm a bit muddled up – MCKapur May 17 '12 at 12:20
Just to check if I understand you correctly: by '$6/1$ works', do you mean that $1$ divides $6$? I don't really understand what you are thinking, but anyway it looks like you're happy with Gerry's nice answer, which is great! – Tara B May 17 '12 at 12:41