Results 1 to 7 of 7

Thread: 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 $\displaystyle p $ must be odd.

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

    Now what does this say about $\displaystyle q-1? $
    Last edited by chiph588@; Aug 26th 2010 at 12: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 $\displaystyle {\cal P} = \{p_1,p_2,p_3,.....\}$ be a ordering of the infinite primes. $\displaystyle p_1 =2$
    Pick an arbitrary prime say, $\displaystyle p_k$.

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

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

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

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

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

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

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

    6) Prove that $\displaystyle p_k$ cannot divide $\displaystyle N - 1$


    Actually 5) shows that N has prime factors from the set $\displaystyle \{p_{k+1},p_{k+2},p_{k+3},.....\}$ and thus from 4), $\displaystyle 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 $\displaystyle 2p-1 $ for $\displaystyle p >2 $ , then all the primes satisfy the requirement .

    Is $\displaystyle q $ greater than $\displaystyle p $ actually , if not $\displaystyle q = 2 $ perhaps satisfies the condition for all $\displaystyle 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 $\displaystyle 2p-1 $ for $\displaystyle p >2 $ , then all the primes satisfy the requirement .

    Is $\displaystyle q $ greater than $\displaystyle p $ actually , if not $\displaystyle q = 2 $ perhaps satisfies the condition for all $\displaystyle 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: Oct 22nd 2011, 12:37 PM
  2. Replies: 0
    Last Post: Sep 24th 2011, 11:23 AM
  3. Replies: 1
    Last Post: Jun 19th 2011, 12: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, 02:52 PM
  5. if ((2^n) -1 ) is prime, prove n is prime ?! >.<
    Posted in the Number Theory Forum
    Replies: 3
    Last Post: Mar 18th 2009, 01:47 PM

Search Tags


/mathhelpforum @mathhelpforum