Prove that for every prime p, there exists another prime q such that p and q-1 are coprime.
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.
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)
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 $ ...