- 30 Jul '06 14:00 / 5 editsCan 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 04:17

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.*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?

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 11:38 / 1 edit

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 ?*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.** - 01 Aug '06 11:44 / 2 edits

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.*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 ?**

EDIT: do you know what groups are?... - 01 Aug '06 12:33 / 1 edit

Oh yeh, you're a true layman, you are!*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 ?**

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 12:48

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.*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?... - 01 Aug '06 12:54

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.*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 - 01 Aug '06 12:59

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!*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.** - 01 Aug '06 18:25 / 1 edit

Z is the ring of integers (an integral domain, actually).*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.**

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 18:27 / 1 edit

No you're wrong.*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?...

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 18:53

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.*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?)

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 19:28

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".*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...