Art of Problem Solving
AoPS Online
Math texts, online classes, and more
for students in grades 5-12.
Visit AoPS Online ‚
Books for Grades 5-12 Online Courses
Beast Academy
Engaging math books and online learning
for students ages 6-13.
Visit Beast Academy ‚
Books for Ages 6-13 Beast Academy Online
AoPS Academy
Small live classes for advanced math
and language arts learners in grades 2-12.
Visit AoPS Academy ‚
Find a Physical Campus Visit the Virtual Campus

Difference between revisions of "Twin Prime Conjecture"
(→‎Elementary proof)
Line 12: Line 12:
  
 
===Elementary proof===
 
===Elementary proof===
 +
Proof of the Twin Prime Conjecture
  
−
Let <math>P_s</math> be the multiplication of the first s prime numbers.
+
Let <math>p_n</math> be the nth prime number
−
Let <math>p_s</math> be the sth prime number
+
<math>p_1=2,p_2=3,p_3=5</math>
−
Let <math>A_s</math> be the set of numbers relatively prime to <math>P_s</math> and less than <math>P_s</math>.
 
  
 +
Let <math>P_n</math> be the first n prime numbers multiplied together
 +
<math>P_1=p_1,P_2=p_1 \times p_2,P_3=p_1 \times p_2 \times p_3</math>
  
−
<math>\{m_1P_s + a_1\}</math> and <math>\{m_2P_s + a_2\}</math> where <math>a</math> in <math>A_s</math> and <math>0 \leq m<P_s</math> and <math>a_1+2=a_2</math>
+
Arithmetic Progression
−
Pair up numbers generated from two arithmetic progression where <math>m_1 = m_2</math>
 
−
If it is not possible to generate a non-prime in each pair then there exist a twin prime.
 
  
 +
<math>\{mP_n+a\}</math>
 +
where <math>a</math> in <math>A_n</math> where <math>a</math> is relatively prime to <math>P_n</math> and less than <math>P_n</math> and <math>0 \leq m < p_{n+1}</math>
  
−
The base case for numbers which differ by <math>2</math> in <math>A_3</math> is <math>11</math> and <math>13</math>. Induction there will always be two numbers which differ by <math>2</math> in <math>A_s</math> <math>s \geq 3</math>.
+
There always exist numbers <math>a_1</math> and <math>a_2</math> in <math>A_s</math> succh that <math>a_1+2=a_2</math> where <math>s \geq 3</math>
  
−
Let <math>0 \leq m < p_{s+1}</math>
+
Base Case <math>11,13</math> in <math>A_3</math>
  
−
<math>\{mP_s+a_1\}</math> and <math>\{mP_s+a_2\}</math> will propagate <math>p_{s+1} - 1</math> pairs of elements in <math>A_{s+1}</math> which differ by <math>d</math> where <math>a_1+d=a_2</math> and <math>d=np_{s+1}</math> and <math>n>0</math>  because only the unique values <math>m_1P_s+a_1</math> and <math>m_2 P_s+a_2</math> in their respective arithmetic progression has the factor of <math>p_{s+1}</math> when <math>m_1=m_2</math>
+
Induction Case
  
−
<math>\{mP_s+a_1\}</math> and <math>\{mP_s+a_2\}</math> will propagate <math>p_{s+1} - 2</math> pairs of elements in <math>A_{s+1}</math> which differ by <math>d</math> where <math>a_1+d=a_2</math> and <math>d \neq np_{s+1}</math> and <math>n>0</math>  because only the unique values <math>m_1P_s+a_1</math> and <math>m_2 P_s+a_2</math> in their respective arithmetic progression has the factor of <math>p_{s+1}</math> when <math>m_1 \neq m_2</math>
+
Let <math>a_1</math> and <math>a_2</math> in <math>A_n</math> such that <math>a_1+d=a_2</math> will propagate at least <math>p_{n+1}-2</math> pairs of numbers which differs by <math>d</math> in <math>A_{n+1}</math>
  
 +
There are a total of <math>p_{n+1}</math> elements generated by arithmetic progression <math>\{mP_n+a_1\}</math> and out of all of the generated elements there is unique element <math>m_1P_n+a_1</math> divisible by <math>p_{n+1}</math>
  
 +
There are a total of <math>p_{n+1}</math> elements generated by arithmetic progression <math>\{mP_n+a_2\}</math> and out of all of the generated elements there is unique element <math>m_2P_n+a_2</math> divisible by <math>p_{n+1}</math>
  
−
All non-primes numbers generated by <math>\{mP_s+a\}-\{1\}</math> where <math>a</math> in <math>A_s</math> and <math>0 \leq m<P_s</math> can also be found in <math>\{f \times g | 1<f<P_s, 1<g, f=2n+1, 1 \leq n\}</math>
+
When <math>m_1 \neq m_2</math> there are <math>p_{n+1}-2</math> pairs of numbers <math>(\{mP_n+a_1\},\{mP_n+a_2\})</math> differs by <math>d, a_1+d=a_2</math> in <math>A_{n+1}</math>
−
Therefore removing all numbers from <math>\{m P_s+a\}-\{1\}</math> with odd factors between and including <math>3</math> to <math>P_s-1</math> will either leave an empty set or a set only containing prime numbers.
 
  
−
Using the fact that there is a fix set of sequential numbers between numbers with the same factor f in arithmetic progression.
+
When <math>m_1 = m_2</math> there are <math>p_{n+1}-1</math> pairs of numbers <math>(\{mP_n+a_1\},\{mP_n+a_2\})</math> differs by <math>d, a_1+d=a_2</math> in <math>A_{n+1}</math>
  
−
<math>\{mP_s + a_1\}</math> where <math>0 \leq m</math> and <math>a_1</math> is an unique pick from <math>A_s</math>
+
Arithmetic Progression
−
if <math>f</math> is a factor of a number in <math>\{m P_s + a_1\}</math> then there is an unique value in <math>\{mP_s + a_1\}</math> which <math>f</math> is a factor when <math>n \leq m<n+f</math>,  <math>0 \leq n</math>
 
  
−
Mark possible non-prime in pair values generated from arithmetic progression <math>m_1P_s+a_1</math> and <math>m_2P_s+a_2</math> where values are paired if <math>m_1=m_2</math>.
+
<math>\{mP_n+a\}</math> where <math>a</math> in <math>A_n</math> where a is relatively prime to <math>P_n</math> and less than <math>P_n</math> and <math>0 \leq m < P_n</math>
  
−
The largest factor to eliminate <math>P_s-1</math> is smaller than the number of pairs elements generate by two arithmetic progressions in <math>\{mP_s+a\}</math> where <math>0 \leq m<P_s</math> and <math>a</math> in <math>A_s</math>
+
If there exist an element in <math>\{mP_n+a_1\}</math> divisible by <math>f</math> than in <math>f</math> consecutive elements <math>x \leq m < x+f</math> generated by arithmetic progression <math>\{mP_n+a_1\}</math> there exist unique element <math>m_1P_n+a_1</math> divisble by <math>f</math>
−
Can guarantee there are <math>P_s-1-2</math> elements without the factor of <math>P_s-1</math> in a consecutive sequence of <math>P_s-1</math> elements from arithmetic progression <math>\{mP_s+a\}</math> where the two numbers with factor of <math>P_s-1</math> are generated in two different arithmetic progression in two different pairs. Assume the remaining <math>P_s-1-2</math> pairs without factor of <math>P_s-1</math> are in a consecutive sequence eliminate the next smaller odd number which differs by <math>2</math>.
+
 
−
Assume the remaining <math>P_s-1-2-2</math> pairs without factor of <math>P_s-1-2</math> are in a consecutive sequence eliminate the next smaller odd number which differs by <math>2</math>.
+
Proof of twin prime conjecture by contradiction
−
Repeat until the number of elements in consecutive sequence is <math>P_s-1-2n =3</math>. Removing numbers with factor of <math>3</math>. There must be a pair of numbers where both of them are prime numbers.
+
 
−
There must be infinite number of twin primes.
+
For there to not exist two prime numbers which differs by <math>d, a_1+d=a_2</math>
 +
There must exist a non-prime number for every value of <math>m, 0 \leq m <P_n</math> in either <math>\{mP_n+a_1\}</math> or <math>\{mP_n+a_2\}</math>
 +
 
 +
All non-prime numbers greater than 1 in <math>\{mP_n+a\}</math> where <math>a</math> in <math>A_n</math> where <math>a</math> in relatively prime to <math>P_n</math> and less than <math>P_n</math> and <math>0 \leq m < P_n</math> must be divisible by an odd number <math>f</math> where <math>3 \leq f \leq P_n-1</math>
 +
 
 +
Removing pairs of numbers from <math>(\{mP_n+a_1\},\{mP_n+a_2\})</math> where either <math>\{mP_n+a_1\}</math> or <math>\{mP_n+a_2\}</math> divisible by <math>f=P_n-1-2o</math> where <math>3 \leq f \leq P_n-1</math>
 +
 
 +
Consider <math>f=P_n-1</math> consective elements <math>x \leq m < x+f</math> generated by arithmetic progression <math>\{mP_n+a_1\}</math> Assume there exist <math>m_1P_n+a_1</math> divisible by <math>f</math> it is unique in these consecutive elements.
 +
 
 +
Consider <math>f=P_n-1</math> consective elements <math>x \leq m < x+f</math> generated by arithmetic progression <math>\{mP_n+a_2\}</math> Assume there exist <math>m_2P_n+a_2</math> divisible by <math>f</math> it is unique in these consecutive elements.
 +
 
 +
Assume <math>m_1 \neq m_2</math>
 +
 
 +
Assume the remaining <math>f-2</math> pairs not divisible by <math>f</math> are consective.
 +
 
 +
Taking the remaining consecutive <math>f-2</math> pairs not divisible by <math>f</math> remove pairs divisible by <math>f-2</math>
 +
 
 +
Consider <math>f=P_n-1-2</math> consective elements <math>x \leq m < x+f</math> generated by arithmetic progression <math>\{mP_n+a_1\}</math> Assume there exist <math>m_1P_n+a_1</math> divisible by <math>f</math> it is unique in these consecutive elements.
 +
 
 +
Consider <math>f=P_n-1-2</math> consective elements <math>x \leq m < x+f</math> generated by arithmetic progression <math>\{mP_n+a_2\}</math> Assume there exist <math>m_2P_n+a_2</math> divisible by <math>f</math> it is unique in these consecutive elements.
 +
 
 +
Assume <math>m_1 \neq m_2</math>
 +
 
 +
Assume the remaining <math>f-2</math> pairs not divisible by <math>f</math> are consective.
 +
 
 +
Continue repeating until with all smaller odd numbers <math>f=P_n-1-2o</math> where <math>o=0,1,2,3,\ldots</math> until <math>f=3</math>
 +
 
 +
There must exist a prime number in <math>\{m_1P_n+a_1\}</math> and <math>\{m_2P_n+a_2\}</math> where <math>m_1=m_2</math> and <math>0 \leq m < P_n</math>
 +
 
 +
Therefore there are infinite number of prime numbers which differ by 2.
  
 
==Alternative statements==
 
==Alternative statements==

Revision as of 08:00, 19 March 2020

The Twin Prime Conjecture is a conjecture (i.e., not a theorem) that states that there are infinitely many pairs of twin primes, i.e. pairs of primes that differ by $2$.

Failed Proofs

Using an infinite series

One possible strategy to prove the infinitude of twin primes is an idea adopted from the proof of Dirichlet's Theorem. If one can show that the sum

$B=\frac{1}{3}+\frac{1}{5}+\frac{1}{5}+\frac{1}{7}+\frac{1}{11}+\frac{1}{13}+\frac{1}{17}+\frac{1}{19}+\cdots$

of the reciprocals of twin primes diverges, this would imply that there are infinitely many twin primes. Unfortunately, it has been shown that this sum converges to a constant $B$, known as Brun's constant. This could mean either that there are finitely many twin prime pairs or that they are spaced "too far apart" for that series to diverge.

Yitang Zhang approach

A weaker version of twin prime conjecture was proved by Yitang Zhang in 2013. This version stated that there are infinitely many pairs of primes that differ by a finite number. The number Yitang chose was 7,000,000. Terence Tao and other people have reduced that boundary to 246 more numbers.

Elementary proof

Proof of the Twin Prime Conjecture

Let $p_n$ be the nth prime number $p_1=2,p_2=3,p_3=5$

Let $P_n$ be the first n prime numbers multiplied together $P_1=p_1,P_2=p_1 \times p_2,P_3=p_1 \times p_2 \times p_3$

Arithmetic Progression

$\{mP_n+a\}$ where $a$ in $A_n$ where $a$ is relatively prime to $P_n$ and less than $P_n$ and $0 \leq m < p_{n+1}$

There always exist numbers $a_1$ and $a_2$ in $A_s$ succh that $a_1+2=a_2$ where $s \geq 3$

Base Case $11,13$ in $A_3$

Induction Case

Let $a_1$ and $a_2$ in $A_n$ such that $a_1+d=a_2$ will propagate at least $p_{n+1}-2$ pairs of numbers which differs by $d$ in $A_{n+1}$

There are a total of $p_{n+1}$ elements generated by arithmetic progression $\{mP_n+a_1\}$ and out of all of the generated elements there is unique element $m_1P_n+a_1$ divisible by $p_{n+1}$

There are a total of $p_{n+1}$ elements generated by arithmetic progression $\{mP_n+a_2\}$ and out of all of the generated elements there is unique element $m_2P_n+a_2$ divisible by $p_{n+1}$

When $m_1 \neq m_2$ there are $p_{n+1}-2$ pairs of numbers $(\{mP_n+a_1\},\{mP_n+a_2\})$ differs by $d, a_1+d=a_2$ in $A_{n+1}$

When $m_1 = m_2$ there are $p_{n+1}-1$ pairs of numbers $(\{mP_n+a_1\},\{mP_n+a_2\})$ differs by $d, a_1+d=a_2$ in $A_{n+1}$

Arithmetic Progression

$\{mP_n+a\}$ where $a$ in $A_n$ where a is relatively prime to $P_n$ and less than $P_n$ and $0 \leq m < P_n$

If there exist an element in $\{mP_n+a_1\}$ divisible by $f$ than in $f$ consecutive elements $x \leq m < x+f$ generated by arithmetic progression $\{mP_n+a_1\}$ there exist unique element $m_1P_n+a_1$ divisble by $f$

Proof of twin prime conjecture by contradiction

For there to not exist two prime numbers which differs by $d, a_1+d=a_2$ There must exist a non-prime number for every value of $m, 0 \leq m <P_n$ in either $\{mP_n+a_1\}$ or $\{mP_n+a_2\}$

All non-prime numbers greater than 1 in $\{mP_n+a\}$ where $a$ in $A_n$ where $a$ in relatively prime to $P_n$ and less than $P_n$ and $0 \leq m < P_n$ must be divisible by an odd number $f$ where $3 \leq f \leq P_n-1$

Removing pairs of numbers from $(\{mP_n+a_1\},\{mP_n+a_2\})$ where either $\{mP_n+a_1\}$ or $\{mP_n+a_2\}$ divisible by $f=P_n-1-2o$ where $3 \leq f \leq P_n-1$

Consider $f=P_n-1$ consective elements $x \leq m < x+f$ generated by arithmetic progression $\{mP_n+a_1\}$ Assume there exist $m_1P_n+a_1$ divisible by $f$ it is unique in these consecutive elements.

Consider $f=P_n-1$ consective elements $x \leq m < x+f$ generated by arithmetic progression $\{mP_n+a_2\}$ Assume there exist $m_2P_n+a_2$ divisible by $f$ it is unique in these consecutive elements.

Assume $m_1 \neq m_2$

Assume the remaining $f-2$ pairs not divisible by $f$ are consective.

Taking the remaining consecutive $f-2$ pairs not divisible by $f$ remove pairs divisible by $f-2$

Consider $f=P_n-1-2$ consective elements $x \leq m < x+f$ generated by arithmetic progression $\{mP_n+a_1\}$ Assume there exist $m_1P_n+a_1$ divisible by $f$ it is unique in these consecutive elements.

Consider $f=P_n-1-2$ consective elements $x \leq m < x+f$ generated by arithmetic progression $\{mP_n+a_2\}$ Assume there exist $m_2P_n+a_2$ divisible by $f$ it is unique in these consecutive elements.

Assume $m_1 \neq m_2$

Assume the remaining $f-2$ pairs not divisible by $f$ are consective.

Continue repeating until with all smaller odd numbers $f=P_n-1-2o$ where $o=0,1,2,3,\ldots$ until $f=3$

There must exist a prime number in $\{m_1P_n+a_1\}$ and $\{m_2P_n+a_2\}$ where $m_1=m_2$ and $0 \leq m < P_n$

Therefore there are infinite number of prime numbers which differ by 2.

Alternative statements

One alternative statement of the Twin Prime Conjecture, is that there exists infinitely many natural numbers not of forms: \[6ab+a+b,6ab+a-b,6ab-a+b,6ab-a-b\] with natural number inputs greater than 0. Because, letting $n$ be of one of these forms one of $6n\pm 1$ factors so only if one of variables is 0 will the factorization be trivial (contain only 1 and itself).

Another is that there are infinitely many values $12m$ that have goldbach partitions of distance from $m$ of 1.

This article is a stub. Help us out by expanding it.

Retrieved from "https://artofproblemsolving.com/wiki/index.php?title=Twin_Prime_Conjecture&oldid=119773"