30 Jul 06
5 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?
31 Jul 06
Originally posted by sarathianLet 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.
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?
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.
01 Aug 06
1 edit
Originally posted by royalchickenSorry. 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 ?
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.
01 Aug 06
2 edits
Originally posted by ranjan sinhawithout 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.
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 ?
EDIT: do you know what groups are?...
01 Aug 06
1 edit
Originally posted by ranjan sinhaOh yeh, you're a true layman, you are!
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 ?
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 😛😵
01 Aug 06
Originally posted by geniusyes 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.
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?...
01 Aug 06
Originally posted by AussiePeteThe 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.
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 😛😵
01 Aug 06
Originally posted by ranjan sinhai 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! 😛
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.
01 Aug 06
1 edit
Originally posted by ranjan sinhaZ is the ring of integers (an integral domain, actually).
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.
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.)
01 Aug 06
1 edit
Originally posted by geniusNo you're wrong.
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?...
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?)
01 Aug 06
Originally posted by SPMarstouche. 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.
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?)
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...
01 Aug 06
Originally posted by geniusIt'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".
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...