# peculiarity of prime numbers.

sarathian
Posers and Puzzles 30 Jul '06 14:00
1. 30 Jul '06 14:005 edits
Can someone prove why does it happen? I will use the notation
n! for the factorial of n.
If p is a prime number, then
it always divides (p - 1)! +1. But for any other (non-prime) number n,
(n - 1) ! + 1 is not necessarily ( rather never) divisible by the first prime which is greater than n.
And of course it is never divisible by n too.
Why?
2. 30 Jul '06 15:14
http://primes.utm.edu/notes/proofs/Wilsons.html
3. royalchicken
CHAOS GHOST!!!
31 Jul '06 04:17
Originally posted by sarathian
Can someone prove why does it happen? I will use the notation
n! for the factorial of n.
If p is a prime number, then
it always divides (p - 1)! +1. But for any other (non-prime) number n,
(n - 1) ! + 1 is not necessarily ( rather never) divisible by the first prime which is greater than n.
And of course it is never divisible by n too.
Why?
Let p be a prime. Then Z/pZ is a field, so without zero, Z/pZ is a group under multiplication (ie the numbers 1, 2, ... p-1 all have multiplicative inverses). (p-1)! is the product of all of the elements in this group. It's easy to show that the inverses are unique for any group, and if n^2 = 1 (mod p) for some p, then algebra shows n = +-1 (mod p). Thus 1 and p-1 are self inverse, and for each other a in the group, there exists a unique b such that ab = 1 (mod p). Thus the product cancels everything except p-1, so (p-1)! = p-1 = -1 (mod p), ie p divides (p-1)! + 1.

If for some integer n, n divides (n-1)! + 1, then n does not divide (n-1)!. If some integer m between 1 and n not inclusive divides n, then m divides (n-1)! and m divides (n-1)! + 1, a contradiction. Thus such and m cannot exist, so n is prime. Thus composite n cannot divide (n-1)!.

Suppose n is non-prime and that p is the smallest prime greater than n. Then (p-1)! = -1 (mod p). Now since 2 < n-1 < p-1, (n-1)! divides (p-1)!, so say (p-1)! = k(n-1)!. Then k(n-1)! = -1 (mod p). If p divides (n-1)! + 1, then we have k = (p-1)(p-2)...n = 1 (mod p), a clear contradiction unless n = p.
4. 01 Aug '06 11:381 edit
Originally posted by royalchicken
Let p be a prime. Then Z/pZ is a field, so without zero, Z/pZ is a group under multiplication (ie the numbers 1, 2, ... p-1 all have multiplicative inverses). (p-1)! is the product of all of the elements in this group. It's easy to show that the inverses are unique for any group, and if n^2 = 1 (mod p) for some p, then algebra shows n = +-1 (mod p). ...[text shortened]... es (n-1)! + 1, then we have k = (p-1)(p-2)...n = 1 (mod p), a clear contradiction unless n = p.
Sorry. I am a layman . What do you mean by Z/pZ ? Doesn't a field have both multiplicative as well as additive inverses? By Z/pZ do you mean the set of compex numbers modulo p ?
5. genius
Wayward Soul
01 Aug '06 11:442 edits
Originally posted by ranjan sinha
Sorry. I am a layman . What do you mean by Z/pZ ? Doesn't a field have both multiplicative as well as additive inverses? By Z/pZ do you mean the set of compex numbers modulo p ?
without 0, it's a group under multiplication. it's like the integers-they are a group under addition but not under multiplication. but Z\0 is a group under multiplication.

EDIT: do you know what groups are?...
6. 01 Aug '06 12:331 edit
Originally posted by ranjan sinha
Sorry. I am a layman . What do you mean by Z/pZ ? Doesn't a field have both multiplicative as well as additive inverses? By Z/pZ do you mean the set of compex numbers modulo p ?
Oh yeh, you're a true layman, you are!

Just a quiet nod to the true layman... don't panic, folks... he's an imposter. You're not extra stupid if you're a layman and you didn't know that ðŸ˜›ðŸ˜µ
7. 01 Aug '06 12:48
Originally posted by genius
without 0, it's a group under multiplication. it's like the integers-they are a group under addition but not under multiplication. but Z\0 is a group under multiplication.

EDIT: do you know what groups are?...
yes group has only multiplicative inverse and a multiplicative identity.Each element has a unique inverse. but certainly the Z/pZ notation is greek to me.
8. 01 Aug '06 12:54
Originally posted by AussiePete
Oh yeh, you're a true layman, you are!

Just a quiet nod to the true layman... don't panic, folks... he's an imposter. You're not extra stupid if you're a layman and you didn't know that ðŸ˜›ðŸ˜µ
The real stupid ones are not those who don't know group theory or field theory. Rather it is those who claim to know more than they really know.
9. 01 Aug '06 12:56
Originally posted by ThudanBlunder
http://primes.utm.edu/notes/proofs/Wilsons.html
I have visited the site. It proves only the first part. It does not prove the second part.
10. genius
Wayward Soul
01 Aug '06 12:59
Originally posted by ranjan sinha
yes group has only multiplicative inverse and a multiplicative identity.Each element has a unique inverse. but certainly the Z/pZ notation is greek to me.
i think it means and integer divided by (a prime times another (different) integer). although i'm not sure-i haven't actually read the proof...it's the summer holidays! ðŸ˜›
11. 01 Aug '06 18:251 edit
Originally posted by ranjan sinha
yes group has only multiplicative inverse and a multiplicative identity.Each element has a unique inverse. but certainly the Z/pZ notation is greek to me.
Z is the ring of integers (an integral domain, actually).

pZ is the subset of Z consisting of those integers divisible by p. Actually, pZ is an (principal) ideal in the ring Z. Therefore we can form the quotient ring

R = Z/pZ

(look up any book on abstract algebra). This ring R has p elements, and can be thought of as the set of integers with + and x done mod p. R is a field (and therefore, by definition (R,+) and (R/ { 0 } , x) are abelian groups.)
12. 01 Aug '06 18:25
Originally posted by genius
i think it means and integer divided by (a prime times another (different) integer). although i'm not sure-i haven't actually read the proof...it's the summer holidays! ðŸ˜›
No, that's not correct. See my previous post.
13. 01 Aug '06 18:271 edit
Originally posted by genius
without 0, it's a group under multiplication. it's like the integers-they are a group under addition but not under multiplication. but Z\0 is a group under multiplication.

EDIT: do you know what groups are?...
No you're wrong.

Z/0 cannot be a group under multplication as (say) 2 has no multiplicative inverse in Z/0.

(Edit: By Z/0 I assume you mean the set of non-zero integers?)
14. genius
Wayward Soul
01 Aug '06 18:53
Originally posted by SPMars
No you're wrong.

Z/0 cannot be a group under multplication as (say) 2 has no multiplicative inverse in Z/0.

(Edit: By Z/0 I assume you mean the set of non-zero integers?)
touche. as i said, it's the summer holidays and i wasn't thinking. i was getting confused with the reals and doing it from memory. my bad.

also, in the notation is it not \ as opposed to / for without? / is dividing? that's what threw me. as i said, i didn't read the proof...
15. 01 Aug '06 19:28
Originally posted by genius
touche. as i said, it's the summer holidays and i wasn't thinking. i was getting confused with the reals and doing it from memory. my bad.

also, in the notation is it not \ as opposed to / for without? / is dividing? that's what threw me. as i said, i didn't read the proof...
It's normally a forward slash / for set complement, but it really doesn't matter. As long as people understand what you're talking about. As Gauss once said "What is needed are notions rather than notations".