5
$\begingroup$

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.

  • 0
    ok ill try that, but can you answer my question please?2012-05-17

2 Answers 2

12

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.

  • 1
    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.2012-05-17
2

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.

  • 0
    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!2012-05-17