Problem
A [tex]prime\left trio[/tex] is a collection of three prime numbers [tex]\{p, q, r\}[/tex] in arithmetic progression, with common difference [tex]q-p=r-q[/tex]. For example, the prime trio [tex]\{3, 5, 7\}[/tex] has common difference 2.
Prove that there is no prime trio with common difference 70.
P.S. I want actual proof.

Respuesta :

Answer:

Proof below

Step-by-step explanation:

General outline

  1. Lemma regarding remainders of non-small primes divided by 6
  2. Check [tex]p=2[/tex] and [tex]p=3[/tex] directly
  3. Proof the rest by contradiction

Lemma

If [tex]p[/tex] is prime such that [tex]p \neq2[/tex] and [tex]p \neq 3[/tex], then [tex]p[/tex] divided by 6 has remainder of 1 or 5.

Case 1: p/6 has remainder 0, 2, or 4.

Then there exists some natural number [tex]n[/tex] such that either [tex]p=6n[/tex], [tex]p=6n+2[/tex], or [tex]p=6n+4[/tex].  However,

  • if [tex]p=6n[/tex], then [tex]p=2*3n[/tex],
  • if [tex]p=6n+2[/tex], then [tex]p=2*(3n+1)[/tex], and
  • if [tex]p=6n+4[/tex], then [tex]p=2*(3n+2)[/tex].

By definition of divisibility, [tex]p[/tex] is divisible by 2.  Since [tex]p \neq2[/tex], [tex]p[/tex] cannot be prime.  This contradiction implies [tex]p[/tex] cannot have a remainder of 0, 2, or 4 when divided by 6.

Case 2: p/6 has remainder 3.

Then there exists some natural number [tex]n[/tex] such that [tex]p=6n+3[/tex].  However, if [tex]p=6n+3[/tex], then [tex]p=3*(2n+1)[/tex], so [tex]p[/tex] is divisible by 3.  Since [tex]p \neq 3[/tex], [tex]p[/tex] is not prime.  This contradiction implies [tex]p[/tex] cannot have a remainder of 3 when divided by 6.

Therefore, if [tex]p[/tex] is a prime number such that  [tex]p \neq2[/tex] and [tex]p \neq 3[/tex], then when divided by 6, [tex]p[/tex] must have a remainder of 1 or 5.

Main proof of no prime trio with common difference of 70.

Check p=2

Consider [tex]p=2[/tex].  Then [tex]q=2+70=72[/tex].  However, [tex]72=2*36[/tex], so [tex]q[/tex] is not prime.  Hence, [tex]p \neq2[/tex].

Check p=3

Consider [tex]p=3[/tex].  Then [tex]q=3+70=73[/tex], and [tex]r=73+70=143[/tex].  However, [tex]143=11*13[/tex], so [tex]r[/tex] is not prime.  Hence, [tex]p \neq 3[/tex].

So, thus far, we've proven that if there is a prime trio with a common difference of 70, that [tex]p \neq2[/tex] and [tex]p \neq 3[/tex].

Proof of the rest of primes by contradiction

By way of contradiction, assume that there does exist some prime trio [tex]\{ p,q,r \}[/tex] such that [tex]q-p=r-q=70[/tex], and [tex]p \neq2[/tex] and [tex]p \neq 3[/tex].

Then, by the Lemma proven earlier, when [tex]p[/tex] is divided by 6, it must have a remainder of 1 or 5.

Case 1: p/6 has remainder 5

Assume that [tex]p[/tex] has remainder 5 when divided by 6.  Then, there exists some natural number [tex]n[/tex], such that [tex]p=6n+5[/tex].  

[tex]q=p+70\\q=(6n+5)+70\\q=6n+75\\q=3*(2n+25)[/tex]

Since [tex]n[/tex] was a natural number, and the natural numbers are closed over multiplication and addition (meaning, multiplying and adding more natural numbers results in another natural number), then [tex]q[/tex] is divisible by 3.

Since [tex]p[/tex] is prime, [tex]0 < p[/tex], which implies [tex]0+70 < p+70[/tex]

Since [tex]q=p+70[/tex], [tex]70 < q[/tex], so [tex]q[/tex] cannot equal 3.  Since [tex]q[/tex] is divisible by 3, but [tex]q \neq 3[/tex], [tex]q[/tex] is not prime, which is a contradiction to the existence of this prime trio.

Therefore, either [tex]p[/tex] cannot have a remainder of 5 when divided by 6, or the prime trio does not exist.

Case 2: p/6 has remainder 1

Assume that [tex]p[/tex] has remainder 1 when divided by 6.  Then, there exists some natural number [tex]n[/tex], such that [tex]p=6n+1[/tex].  

[tex]q=p+70\\q=(6n+1)+70\\r=q+70\\r=((6n+1)+70)+70\\r=6n+141\\r=3*(2n+47)[/tex]

Since [tex]n[/tex] was a natural number, and the natural numbers are closed over multiplication and addition (meaning, multiplying and adding more natural numbers results in another natural number), [tex]r[/tex] is divisible by 3.

Since [tex]q[/tex] is prime, [tex]0 < q[/tex], implying [tex]0 +70 < q+70[/tex].

Since [tex]r=q+70[/tex], then [tex]70 < r[/tex].  Therefore, [tex]r\neq 3[/tex].

Since [tex]r[/tex] is divisible by 3, but [tex]r\neq 3[/tex], [tex]r[/tex] is not prime, which is a contradiction to the existence of this prime trio (with a common difference of 70).  Therefore, either [tex]p[/tex] cannot have a remainder of 1 when divided by 6, or the prime trio does not exist.

Since [tex]p[/tex] was prime, by our lemma [tex]p[/tex] must have either a remainder of 1 or 5.  Since both remainder possibilities resulted in a contradiction, our contradiction assumption is false, so there cannot exist a prime trio such that their common difference is 70.