Results 1 to 12 of 12

Math Help - Regarding Wilson's Theorem

  1. #1
    Member
    Joined
    Aug 2009
    Posts
    170
    Thanks
    8

    Regarding Wilson's Theorem

    I was just wondering something

    (p-1)! = -1 mod p

    I was investigating the number (p-1)! + 1, which is divisible by p. I was wondering if n = ((p-1)! + 1)/p, then does the prime factorization of n consists of primes all of which are to the power of 1 (except for the case of p = 2, since n = 1)?

    I couldn't really test much because of the factorial, it makes the numbers huge ... I tried till p = 37 ... after that I get problems with factoring the huge number generated by the factorial ...

    Could someone test out a few more primes please ... or if someone is familiar with this idea, could you point me to more information about this ... thanks!
    Follow Math Help Forum on Facebook and Google+

  2. #2
    MHF Contributor chiph588@'s Avatar
    Joined
    Sep 2008
    From
    Champaign, Illinois
    Posts
    1,163
    This looks like an interesting result! Wolfram alpha would be able to factor what you're looking for.
    Follow Math Help Forum on Facebook and Google+

  3. #3
    Member
    Joined
    Aug 2009
    Posts
    170
    Thanks
    8
    Thanks!! That's a neat site

    Wolfram worked up to p=59 (except for p=47, not sure why, might be an internet problem on my part), after that, it doesn't work (at least up to p=101) ... but at least it's giving me hope. Everything I've tested so far seems to work

    I was thinking that it might be a potential way to generate candidates for the largest prime , but then again, I'm not familiar with how it's usually done, hehehe.

    Any other resources I could tap?
    Last edited by Bingk; November 20th 2010 at 02:05 PM. Reason: clarified
    Follow Math Help Forum on Facebook and Google+

  4. #4
    MHF Contributor chiph588@'s Avatar
    Joined
    Sep 2008
    From
    Champaign, Illinois
    Posts
    1,163
    Quote Originally Posted by Bingk View Post
    Thanks!! That's a neat site

    Worked up to p=59 (except for p=47, not sure why, might be an internet problem on my part), after that, it doesn't work (at least up to p=101) ... but at least it's giving me hope. Everything I've tested so far seems to work

    I was thinking that it might be a potential way to generate candidates for the largest prime , but then again, I'm not familiar with how it's usually done, hehehe.

    Any other resources I could tap?
    I'm not sure this would be the best way to find the largest known prime. Google GIMPS to learn more about the preferred method to date.

    I'm more interested in why  (p-1)!+1 seems to be square free!
    Follow Math Help Forum on Facebook and Google+

  5. #5
    Super Member Matt Westwood's Avatar
    Joined
    Jul 2008
    From
    Reading, UK
    Posts
    807
    Thanks
    27
    Good page on wikipedia which you might like to start at

    Wilson's theorem - Wikipedia, the free encyclopedia
    Follow Math Help Forum on Facebook and Google+

  6. #6
    Member
    Joined
    Aug 2009
    Posts
    170
    Thanks
    8
    Um, it's actually, \displaystyle{\frac{(p-1)!+1}{p}} that is square free. for 5 and 13, you'll see that the prime factors of (p-1)!+1 involves 5^2 and 13^2
    Follow Math Help Forum on Facebook and Google+

  7. #7
    Super Member Bacterius's Avatar
    Joined
    Nov 2009
    From
    Wellington
    Posts
    927
    p = 47 works. I think we're not going to be able to go much further than p = 101, as factorization cannot be done efficiently. However, I wonder if some polynomial time algorithm exists to check whether an integer is square-free ? I don't think so but perhaps ...
    Follow Math Help Forum on Facebook and Google+

  8. #8
    Super Member Bacterius's Avatar
    Joined
    Nov 2009
    From
    Wellington
    Posts
    927
    I was thinking that it might be a potential way to generate candidates for the largest prime
    Don't think so either, the numbers don't seem deemed to be prime with high probability at all ... however their prime factorization is quite .. ah .. unusual. This has to be explored.
    Follow Math Help Forum on Facebook and Google+

  9. #9
    Super Member Bacterius's Avatar
    Joined
    Nov 2009
    From
    Wellington
    Posts
    927
    Here's a mathematical headstart anyway :

    Theorem

    (p - 1)! is not squarefree for prime p > 5.

    Proof

    Let q be the greatest prime number that satisfies 2q < p - 1. Then kq | (p - 1)! for k \in \{1, 2\}, thus q^2 | (p - 1)!. Since no q exists for p \leq 5, we need p > 5.

    ____________________


    Maybe someone can put a condition on "if x is not squarefree then x + 1 is squarefree", which could potentially prove the conjecture if the condition is cleverly chosen ...
    Follow Math Help Forum on Facebook and Google+

  10. #10
    Banned
    Joined
    Oct 2009
    Posts
    4,261
    Thanks
    2
    Quote Originally Posted by Bacterius View Post
    Here's a mathematical headstart anyway :

    Theorem

    (p - 1)! is not squarefree for prime p > 5.

    Proof

    Let q be the greatest prime number that satisfies 2q < p - 1. Then kq | (p - 1)! for k \in \{1, 2\}, thus q^2 | (p - 1)!. Since no q exists for p \leq 5, we need p > 5.

    ____________________


    Maybe someone can put a condition on "if x is not squarefree then x + 1 is squarefree", which could potentially prove the conjecture if the condition is cleverly chosen ...

    I don't know if there's some mistake on your theorem, but it is a rather trivial, boring one: n! is not square free whenever  n\geq 4, as it is trivially divisible by 2^2=4.

    Tonio
    Follow Math Help Forum on Facebook and Google+

  11. #11
    Super Member Bacterius's Avatar
    Joined
    Nov 2009
    From
    Wellington
    Posts
    927
    Quote Originally Posted by tonio View Post
    I don't know if there's some mistake on your theorem, but it is a rather trivial, boring one: n! is not square free whenever  n\geq 4, as it is trivially divisible by 2^2=4.

    Tonio
    You are right, I missed the trivial proof ... I must be tired.
    I think my proof is all right though ... but it's obvious the trivial proof is a lot simpler !
    Follow Math Help Forum on Facebook and Google+

  12. #12
    MHF Contributor chiph588@'s Avatar
    Joined
    Sep 2008
    From
    Champaign, Illinois
    Posts
    1,163
    Wilson prime - Wikipedia, the free encyclopedia

    Not exactly what you're after, but close.
    Last edited by chiph588@; August 5th 2010 at 03:55 PM.
    Follow Math Help Forum on Facebook and Google+

Similar Math Help Forum Discussions

  1. [SOLVED] Wilson's Theorem
    Posted in the Number Theory Forum
    Replies: 6
    Last Post: November 30th 2011, 10:26 AM
  2. Prove Wilson's theorem by Lagrange's theorem
    Posted in the Number Theory Forum
    Replies: 2
    Last Post: April 10th 2010, 01:07 PM
  3. Wilson theorem
    Posted in the Number Theory Forum
    Replies: 9
    Last Post: May 16th 2009, 02:30 AM
  4. Wilson's Theorem
    Posted in the Number Theory Forum
    Replies: 1
    Last Post: October 23rd 2008, 07:52 AM
  5. Wilson's Theorem
    Posted in the Number Theory Forum
    Replies: 1
    Last Post: October 7th 2008, 11:41 AM

Search Tags


/mathhelpforum @mathhelpforum