Results 1 to 7 of 7

Math Help - Prove that for every prime p, there exists another prime q such that p and q-1 are...

  1. #1
    Newbie
    Joined
    Jul 2010
    Posts
    20

    Prove that for every prime p, there exists another prime q such that p and q-1 are...

    Prove that for every prime p, there exists another prime q such that p and q-1 are coprime.
    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 oleholeh View Post
    Prove that for every prime p, there exists another prime q such that p and q-1 are coprime.
    Note  p must be odd.

    Pick a prime of the form  q=ap+2 (Dirichlet tells us there are infinitely many in fact).

    Now what does this say about  q-1?
    Last edited by chiph588@; August 26th 2010 at 01:50 PM.
    Follow Math Help Forum on Facebook and Google+

  3. #3
    Newbie
    Joined
    Jul 2010
    Posts
    20
    Is there some other way, without trivializing it with Dirichlet's theorem?
    Follow Math Help Forum on Facebook and Google+

  4. #4
    Senior Member
    Joined
    Jul 2010
    From
    Vancouver
    Posts
    432
    Thanks
    17
    You can use Bertrand's postulate in the following way.

    Given p, there is a prime q between p and 2p. Now q-1 is between p-1 and 2p-1. The only way for gcd(p,q-1) > 1 is when p|q-1. This can only happen if q-1 = p since q-1<2p-1, but this means q = p+1 which is a contradiction.
    Follow Math Help Forum on Facebook and Google+

  5. #5
    Lord of certain Rings
    Isomorphism's Avatar
    Joined
    Dec 2007
    From
    IISc, Bangalore
    Posts
    1,465
    Thanks
    6
    Quote Originally Posted by oleholeh View Post
    Prove that for every prime p, there exists another prime q such that p and q-1 are coprime.
    My proof is a long one (but elementary), so I will expect you fill in the minor details.
    Let {\cal P} = \{p_1,p_2,p_3,.....\} be a ordering of the infinite primes. p_1 =2
    Pick an arbitrary prime say, p_k.

    We will prove the statement by contradiction.
    Suppose p_k and p_j - 1 are not co-prime for all j > k.

    Prove the following: (these are the steps of the proof)

    1) p_k | p_j - 1 for all j > k .

    2) p_k | p_j^n - 1 for all j > k and for all n \in \mathbb{N}.

    3) Let a, b \in \mathbb{N}, if p_k | a - 1 and p_k | b - 1 then p_k | ab - 1

    4) Let A be a natural number whose prime factors are from the set  \{p_{k+1},p_{k+2},p_{k+3},.....\}, then p_k | A - 1

    5) Let N = p_2p_3p_4 \cdots p_k + 2. Prove that:
      i \leq k \implies p_i does not divide N.

    6) Prove that p_k cannot divide N - 1


    Actually 5) shows that N has prime factors from the set  \{p_{k+1},p_{k+2},p_{k+3},.....\} and thus from 4), p_k | N - 1. But 6) contradicts this!!!!

    Thus proved
    (Nice Problem)
    Follow Math Help Forum on Facebook and Google+

  6. #6
    Super Member
    Joined
    Jan 2009
    Posts
    715
    Just factorize  2p-1 for  p >2 , then all the primes satisfy the requirement .

    Is  q greater than  p actually , if not  q = 2 perhaps satisfies the condition for all  p  ...
    Follow Math Help Forum on Facebook and Google+

  7. #7
    Lord of certain Rings
    Isomorphism's Avatar
    Joined
    Dec 2007
    From
    IISc, Bangalore
    Posts
    1,465
    Thanks
    6
    Quote Originally Posted by simplependulum View Post
    Just factorize  2p-1 for  p >2 , then all the primes satisfy the requirement .

    Is  q greater than  p actually , if not  q = 2 perhaps satisfies the condition for all  p  ...
    Let us assume q is greater than p (or else the problem is not interesting!).

    I do not understand how factorizing 2p - 1 will help. In fact 2p-1 may have all prime factors less than p.

    Consider p = 5, for which 2p-1 = 9 = 3^2.
    Follow Math Help Forum on Facebook and Google+

Similar Math Help Forum Discussions

  1. Replies: 1
    Last Post: October 22nd 2011, 01:37 PM
  2. Replies: 0
    Last Post: September 24th 2011, 12:23 PM
  3. Replies: 1
    Last Post: June 19th 2011, 01:56 PM
  4. Show only one group exists for Groups of prime order
    Posted in the Advanced Algebra Forum
    Replies: 8
    Last Post: May 30th 2010, 03:52 PM
  5. if ((2^n) -1 ) is prime, prove n is prime ?! >.<
    Posted in the Number Theory Forum
    Replies: 3
    Last Post: March 18th 2009, 02:47 PM

Search Tags


/mathhelpforum @mathhelpforum