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 $\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$divide $\displaystyle N - 1$__cannot__

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 PMsimplependulum
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 PMIsomorphism