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

Printable View

- Aug 26th 2010, 09:15 AMoleholehProve 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 AMchiph588@
- Aug 26th 2010, 12:16 PMoleholeh
Is there some other way, without trivializing it with Dirichlet's theorem?

- Aug 26th 2010, 08:24 PMVlasev
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 PMIsomorphism
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 thatdivide__cannot__

Actually 5) shows that N has prime factors from the set and thus from 4), . But 6) contradicts this!!!!

Thus proved :D

(Nice Problem) - Aug 26th 2010, 09:05 PMsimplependulum
Just factorize for , then all the primes satisfy the requirement .

Is greater than actually , if not perhaps satisfies the condition for all ... - Aug 27th 2010, 11:44 PMIsomorphism