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

• Aug 26th 2010, 09: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, 09: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 $\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?$
• Aug 26th 2010, 12:16 PM
oleholeh
Is there some other way, without trivializing it with Dirichlet's theorem?
• Aug 26th 2010, 08: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, 09: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 $\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 :D
(Nice Problem)
• Aug 26th 2010, 09:05 PM
simplependulum
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$ ...
• Aug 27th 2010, 11:44 PM
Isomorphism
Quote:

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