This post walks you through how I almost solved Twin Prime Conjecture, which is considered as one of the classic and open-ended question in the field of number theory.
Euclidean algorithm is considered as one of the efficient methods for computing greatest common divisor(gcd) of two numbers. Euclid algorithm is based on the simple principle that greatest common divisor of two numbers does not change if the larger number is replaced by its difference with smaller number.
In number theory, two integers a & b are said to be coprime if the only positive integer dividing both of them is 1. i.e. gcd(a, b) = 1. The probability that any number divisible given number(p) is 1/p, so probability that two numbers are coprime is given by a product over all primes.
“There exists an infinite number of positive integers p with p and p+2 both prime.”
My solution for Twin Prime Conjecture
Let p be any odd number since if p is even it can’t be prime (except p = 2)
Since p is odd p+2 will be odd and any odd number can be written as p = 1 mod 2 and (p + 2) = 1 mod 2
From Euclid’s algorithm we know if a & b are two coprime numbers there exists integers x, y such that ax+by = 1
Since p & p+2 are odd they are coprime to 2 so, we can write
px1 + 2y1 = 1
(p+2)x2 + 2y2 = 1
where x1, y1, x2, y2 are integers.
We can equate both equations
px1 + 2y1 = (p+2)x2 + 2y2
By solving this equation, we will get
(p+2)y1 - py2 = 1
let’s say k is a common factor of y1 and y2 then the above equation becomes k(something) = 1 but that’s only possible when k = 1 since something must be an integer.
So, from Euclid’s algorithm we know (p+2) and pare coprime to each other
Any number can be written as multiples of primes if 2,3,5,7…. n is known prime then (2x3x5x7x……. xn) + 1 is also a prime since it gives remainder 1 when divided by any prime or combination of primes.
Similarly, if 2,3,5,7, ……. n is known prime then we can infer (2x3x5x7x……. xn) -1 and (2x3x5x7x……. xn) +1 are also primes, so we can prove there exists infinite twin primes (i.e. if p is prime p+2 is also prime) but there exists some exception of two types like 209 which is (2x3x5x7)-1 and 30031 which is (2x3x5x7x11x13) +1
But if we carefully observe the exceptions, they must have two prime factors greater than n (as n in 2x3x5x…xn) since if it is any other number then it will be divisible by primes less than or equal to n (i.e. 2,3,5…n)
can be written as (2x3x5x7) – 1, but 11 and 19 are its factors
30,031 can be written as (2x3x5x7x11x13) +1, but 59 and 509 are its factors
In both cases the factors are prime numbers that are greater than n and that has to be because if there is any other divisor it would be divisible by existing primes and we will get remainder of ±1.
 D. H. Lehmer (1938) Euclid’s Algorithm for Large Numbers, The American Mathematical Monthly, 45:4, 227-233.
Any natural number n must be divisible by atleast one of the prime number less than n otherwise n itself is a prime