If m, n are natural numbers, does the sequence m, m+n, m+2n, ... contain prime numbers? How many?
Elaborate on history, relation to other prime number problems, solutions.
It has long been conjectured that there are arithmetic progressions of primes of arbitrary lengths . For instance the longest known arithmetic sequence of consecutive primes is of length 26 and is given by 43142746595714191+23681770*223092870n for n = 0,1, ... ,25. Throughout history, Many mathematicians have worked for years trying to prove or disprove this conjecture, and more so to come up with a particular algorithm to find arithmetic progressions of primes of any given length. This conjecture has created many questions and problems that to this day, remain unanswered. If m, n are natural numbers, does the sequence m, m+n, m+2n, ... contain prime numbers? How many? Finite or infinite? Lengths of progressions?
History and Development
Starting as early as 1770, Lagrange and Waring questioned and researched how large the common difference of an arithmetic progression of n primes must be. In 1923, Hardy and Littlewood made a came up with a conjecture that there are infinitely prime n-tuples of the form p, p + a1, .... ,p + an for any positive integers a1, ..... ,an. This idea was then adapted to the case where a1, ... ,an is a geometric sequence in the form a1, 2*a1, 3*a1, .... ,n*a1. Ever since, there has been a plethora of questions (some answered and some not) regarding primes in arithmetic progressions.
The first theoretical development on the conjecture of arithmetic progressions of primes was given by van der Corput in 1939, who proved that there are infinitely many arithmetic progressions of consecutive primes of length 3 by using analytic methods. Heath-Brown proved that there are infinitely many four-term progressions consisting of three primes and a number that is either a prime or semiprime in 1981. The more recent Green-Tao theorem generalized van der Corput's and Heath-Brown's work and states the same result for any given length. However this theorem only proves the existence of such progressions, but not a method of finding them. In 2004, Benjamin Green and Terrence Tao used Szemerédi's theorem in combination with work done by mathematicians Goldston and Yildirim. Forty eight pages of dense and technical mathematics later, they had established the fundamental theorem that the prime numbers in fact do contain arithmetic progressions of length k for all k.
Outline of Proof
In this outline we will consider three things: Szemeredi's Theorem, a generalized version of Szemeredi's Theorem with a k-pseudorandom measure, and a proposition by Goldston and Yildirim.
Now we consider a generalization of the above theorem below.
The generalized theorem is very similar to the original. However notice the subtle difference that we use the assumption that we replace the constant function with a k-pseudorandom measure in the generalized theorem.
Next we consider the proposition by Goldston and Yildirim.
Then apply the Generalized Szemeredi's Theorem to the above choice of f and v . From that point it follows quite easily that
the prime numbers contain an arithmetic progression of arbitrary length k.
Now that it is apparent that the prime numbers do contain arithmetic progressions of any length, we question how many primes such a progression contains?
If the sequence m, m+n, m+2n, ... actually contains primes, how many does it contain?
Dirichlet's Theorem
The above question was considered by renowned mathematician Dirichlet as early as the 1830's. Dirichlet used what later became known as his L-function to formulate his famous theorem in 1837.
Arithmetic Progression can be thought of as a modulus function with a minimum number. That is to say every number that is equal to m mod n and is greater than m is a term in the arithmetic progression.
In order for m + X*n to be prime at some x value, it is enough to prove that m and n must be coprime. If they are not and the gcd(m,n) ≠ 1 then we can show that if the gcd(m,n) = y then gcd(m,y) = y and the gcd(X*n,y) = y For Every value of X, then the gcd(m,X*n) ≠ 1 for every X value with X > 0 and therefore no primes occur in this sequence.
Using the Euler-φ-function, we know φ(p) = p-1 if p ϵ Primes. In order to determine which numbers are co-prime with m or n we just take φ(m) (assuming m is larger) and the φ function will give the number of options for n that a co-prime with m.
For example, if we took m = 8 and n = 4. All we will have is even terms in the sequence which are all divisible by 2 and therefore none are primes.
The last thing to check is when X = 0. It is possible that m by itself is a prime and if n is not coprime with it; every sequential term is not a prime. This means that there can also be a single prime in the sequence.
This shows that in order for any primes to exist in the arithmetic progression, m and n must be coprime. Dirichlet's Theorem on Primes in Arithmetic Progressions (1837) proves that if m and n are coprime, then there are an infinite number of primes in the arithmetic progression.
This means that for any arithmetic progression there are no primes, only 1 prime, or an infinite number of primes.
