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

• Aug 26th 2010, 10:15 AM
oleholeh
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.
• Aug 26th 2010, 10:52 AM
chiph588@
Quote:

Originally Posted by oleholeh
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?$
• Aug 26th 2010, 01:16 PM
oleholeh
Is there some other way, without trivializing it with Dirichlet's theorem?
• Aug 26th 2010, 09:24 PM
Vlasev
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.
• Aug 26th 2010, 10:01 PM
Isomorphism
Quote:

Originally Posted by oleholeh
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 :D
(Nice Problem)
• Aug 26th 2010, 10:05 PM
simplependulum
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$ ...
• Aug 28th 2010, 12:44 AM
Isomorphism
Quote:

Originally Posted by simplependulum
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.