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 be a ordering of the infinite primes.
Pick an arbitrary prime say, .
We will prove the statement by contradiction.
Suppose and are not co-prime for all .
Prove the following: (these are the steps of the proof)
1) for all .
2) for all and for all .
3) Let , if and then
4) Let A be a natural number whose prime factors are from the set , then
5) Let . Prove that:
does not divide .
6) Prove that cannot divide
Actually 5) shows that N has prime factors from the set and thus from 4), . But 6) contradicts this!!!!
Thus proved
(Nice Problem)