Please turn on javascript in your browser to play chess.
Posers and Puzzles

Posers and Puzzles

  1. 30 Jul '06 14:00 / 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?
  2. 30 Jul '06 15:14
    http://primes.utm.edu/notes/proofs/Wilsons.html
  3. Standard member 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:38 / 1 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. Standard member genius
    Wayward Soul
    01 Aug '06 11:44 / 2 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:33 / 1 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. Standard member 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:25 / 1 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:27 / 1 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. Standard member 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".