Page 1 of 2 12 LastLast
Results 1 to 15 of 16

Math Help - Number Theory problem

  1. #1
    Newbie
    Joined
    Jun 2010
    Posts
    9

    Number Theory problem

    hello number theorists ,

    I'm beginner and I have troubles with this lemma which i belive it is true ,

    let p a prime number greater than $3$, and let P be the set of primes less than p, show that there exist p_1 , p_2 ... ,p_n from P, such that p divides  \prod_{i=1}^{i=n} p_i  -1

    Thanks in ADvance
    Follow Math Help Forum on Facebook and Google+

  2. #2
    MHF Contributor chiph588@'s Avatar
    Joined
    Sep 2008
    From
    Champaign, Illinois
    Posts
    1,163
    Quote Originally Posted by shostakovich View Post
    hello number theorists ,

    I'm beginner and I have troubles with this lemma which i belive it is true ,

    let p a prime number greater than 3, and let P be the set of primes less than p, show that there exist p_1 , p_2 ... ,p_n from P, such that p divides  \prod_{i=1}^{i=n} p_i  -1

    Thanks in Advance
    What is this problem for? The context of the problem may make it easier to solve.
    Follow Math Help Forum on Facebook and Google+

  3. #3
    Newbie
    Joined
    Jun 2010
    Posts
    9
    well , the original problem says : let A a set of prime numbers , such that for all finite subset S of A , and S<> A, we have: all prime divisors of :  (\prod_ {p\in S}p )-1 are also in A, Show that A is the set of prime numbers
    I had the idea to use induction and the lemma above
    Follow Math Help Forum on Facebook and Google+

  4. #4
    MHF Contributor Also sprach Zarathustra's Avatar
    Joined
    Dec 2009
    From
    Russia
    Posts
    1,506
    Thanks
    1
    Maybe this will help you!
    I find similarity between the problems... Euclid's Proof of the Infinitude of Primes (c. 300 BC)
    Follow Math Help Forum on Facebook and Google+

  5. #5
    MHF Contributor chiph588@'s Avatar
    Joined
    Sep 2008
    From
    Champaign, Illinois
    Posts
    1,163
    Quote Originally Posted by shostakovich View Post
    well , the original problem says : let A a set of prime numbers , such that for all finite subset S of A , and S<> A, we have: all prime divisors of :  (\prod_ {p\in S}p )-1 are also in A, Show that A is the set of prime numbers
    I had the idea to use induction and the lemma above
    What does  S<>A mean?
    Follow Math Help Forum on Facebook and Google+

  6. #6
    Newbie
    Joined
    Jun 2010
    Posts
    9
    well it means that S is different of A, sorry I'm not good at latex

    Actually I found the solution in the internet , it is very elegant , I will share it here as soon as I can
    Follow Math Help Forum on Facebook and Google+

  7. #7
    MHF Contributor chiph588@'s Avatar
    Joined
    Sep 2008
    From
    Champaign, Illinois
    Posts
    1,163
    Quote Originally Posted by shostakovich View Post
    well it means that S is different of A, sorry I'm not good at latex

    Actually I found the solution in the internet , it is very elegant , I will share it here as soon as I can
    Can't wait! This problem is stumping me for some reason.
    Follow Math Help Forum on Facebook and Google+

  8. #8
    Super Member Bacterius's Avatar
    Joined
    Nov 2009
    From
    Wellington
    Posts
    927
    Scratch that I didn't see your next post. Hang on ...
    Yeah, I like this problem. I'll be thinking about it, feel free to post the solution you found
    Follow Math Help Forum on Facebook and Google+

  9. #9
    Member
    Joined
    Jun 2008
    Posts
    148
    The original conjecture sounds wrong. For instance, if you take p = 5, Then P = {3}, which implies 5 | 3 - 1.
    Follow Math Help Forum on Facebook and Google+

  10. #10
    Newbie
    Joined
    Jun 2010
    Posts
    9
    TO Jamix , what about 2*3-1? , anyway here is the solution

    ( I apologize , I forgot to mention that A contains at least 3 elements )

    First of all we shall prove that A is infinite , indeed suppose it is finite for sake of contradiction, consider S= \prod_{p\in A}p, let a\in A , by conditions \frac{S}{a} -1 has all prime divisors in A, but \frac{S}{a}-1 is prime with each element of A Except a, we conclude that \frac{S}{a}-1= a^k for some positive integer k , that is S= a^{k+1}+a,

    now it is easy to prove that 2,3,5 are in A , in particuler S= 2^{a}+2 and S= 3^{b}+3 , for some positive integers a,b since S \geq  2*3*5= 30, we conclude that a \geq 4, looking mod 16 we get S= 2 [16] that is 3^b=-1 [16] which is is a contradiction ,

    let q a prime number , since A is infinite , there exist at least q-1 prime number which have the same residue in F_q, we can suppose that this residue isn't 0 , let c_1,c_2,.......c_{q-1} those primes , hence by Fermat little theorem , we have c_1c_2....c_{q-1}=1[q] and we are done
    Follow Math Help Forum on Facebook and Google+

  11. #11
    MHF Contributor chiph588@'s Avatar
    Joined
    Sep 2008
    From
    Champaign, Illinois
    Posts
    1,163
    I wonder if the original lemma you posted is false or not.
    Follow Math Help Forum on Facebook and Google+

  12. #12
    Member
    Joined
    Jun 2008
    Posts
    148
    Quote Originally Posted by shostakovich View Post
    TO Jamix , what about 2*3-1? , anyway here is the solution

    ( I apologize , I forgot to mention that A contains at least 3 elements )

    First of all we shall prove that A is infinite , indeed suppose it is finite for sake of contradiction, consider S= \prod_{p\in A}p, let a\in A ,
    I thought S was suppose to be a finite subset of A which contains only primes?

    In any case, if you define S as you did above, couldn't you just conclude that A must have infinitely many primes based on the fact that S - 1 doesn't share any primes in common with A?
    Follow Math Help Forum on Facebook and Google+

  13. #13
    Super Member
    Joined
    Aug 2009
    From
    Israel
    Posts
    976
    Quote Originally Posted by jamix View Post
    I thought S was suppose to be a finite subset of A which contains only primes?
    2 is a prime indeed.
    Follow Math Help Forum on Facebook and Google+

  14. #14
    Member
    Joined
    Jun 2008
    Posts
    148
    I made a mistake, but that doesn't have anything to do with my last post.
    Follow Math Help Forum on Facebook and Google+

  15. #15
    Newbie
    Joined
    Jun 2010
    Posts
    9
    Quote Originally Posted by jamix View Post
    I thought S was suppose to be a finite subset of A which contains only primes?

    In any case, if you define S as you did above, couldn't you just conclude that A must have infinitely many primes based on the fact that S - 1 doesn't share any primes in common with A?
    WEll read carefully the conditions , S is different of A

    to chiph588@ : I'm not sure , may be some one good with programming can verify big value with computer !
    Follow Math Help Forum on Facebook and Google+

Page 1 of 2 12 LastLast

Similar Math Help Forum Discussions

  1. Number theory problem
    Posted in the Number Theory Forum
    Replies: 7
    Last Post: September 16th 2009, 02:29 PM
  2. Number Theory Problem
    Posted in the Number Theory Forum
    Replies: 3
    Last Post: August 28th 2009, 02:44 PM
  3. Number Theory problem
    Posted in the Number Theory Forum
    Replies: 5
    Last Post: December 30th 2008, 12:07 PM
  4. Replies: 2
    Last Post: December 18th 2008, 05:28 PM
  5. Number Theory GCD Problem
    Posted in the Number Theory Forum
    Replies: 2
    Last Post: October 10th 2006, 04:59 PM

Search Tags


/mathhelpforum @mathhelpforum