Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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.

share|improve this question
    
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
2  
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

2 Answers 2

up vote 8 down vote accepted

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.

share|improve this answer
    
thank you this is a very valuable answer... –  MCKapur May 17 '12 at 12:38
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. –  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.

share|improve this answer
    
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

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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