# Sets of Prime and Composite Numbers

We know that all primes are of the form $6k ± 1$ with the exception of 2 and 3.

We also know that not all numbers of the form $6k ± 1$ are prime.

This leads to four distinct sets of pairs adjacent to a multiple of six:

1. Twin Primes, Example: $5, 7$ (prime followed by a prime)
2. Twin Composites, Example: $119, 121$ (composite followed by a composite)
3. Prime-Composite, Example: $23, 25$ (prime followed by a composite)
4. Composite-Prime, Example: $35, 37$ (composite followed by a prime)

The Twin Prime Conjecture states that there are infinitely many Twin Primes, but has yet to be proven.

Could it be proven that any of these four sets are infinite?

• prime composites and composite primes are badly chosen terms – Marc van Leeuwen Oct 22 '15 at 13:11
• @Marc van Leeuwen: Based on what criteria? Have they been established? What would you name them? – Tony Oct 22 '15 at 13:41
• "prime composite" is a prima facie oxymoron. I might recommend the four names "PP", "PC", "CP", and "CC", although those names aren't great. (I heartily endorse proposed improvements.) – Eric Towers Oct 22 '15 at 16:02
• It can be proven that at least one of these four sets is infinite. – John Dvorak Oct 22 '15 at 20:05

The composite-composite case is easy. By the Chinese remainder theorem there are infinitely many solutions of, for example, $$x\equiv0\pmod6\ ,\quad x\equiv1\pmod5\ ,\quad x\equiv-1\pmod7\ .$$ And for any such $x$ greater than $6$ we have $x-1,x+1$ are adjacent to a multiple of $6$, and $x-1$ is a multiple of $5$ and hence composite, and $x+1$ is a multiple of $7$ and hence composite.

The composite-prime case follows from Dirichlet's theorem (which is not easy to prove). Consider the numbers $x=30k+6$. Then the numbers $x-1,x+1$ are adjacent to a multiple of $6$; and the numbers $x+1$ are prime infinitely often; and the numbers $x-1$ are always composite.
Similarly, $x=30k-6$ covers the prime-composite case.
And as you mentioned, the prime-prime case is still unsolved.
Alternative proof for the composite case: consider the numbers $$x=6\times119\times121k+120\ .$$ Then $x-1$ is always a multiple of $119$, and $x+1$ is always a multiple of $121$.

Or to keep the numbers a bit smaller, $x=6\times7\times11k+120$.

• Very nice. +1. . – Shailesh Oct 22 '15 at 6:25
• Has a probability distribution been established for these four sets? Such that the probability of a random multiple of six, or a multiple of six below or above a certain number, belongs to either of these four sets? – Tony Oct 22 '15 at 6:48
• Not that I'm aware of. However I am definitely not an expert in this subject. – David Oct 22 '15 at 6:52
• @lurker: Given that a nonzero lower bound for the asymptotic probability of prime+prime would solve the twin primes conjecture, I think we can safely say that no such lower bound is known. – Henning Makholm Oct 22 '15 at 13:44

It is very simple to construct an infinite sequence for the Prime-Composite case:

$$23+60n,25+60n$$

$25+60n$ will generate an infinite amount of composite numbers, all of which are divisible by $5$ (in fact, it will generate only composite numbers).

$23+60n$ will generate an infinite amount of prime numbers, since $23$ and $60$ are coprime integers (according to Dirichlet's theorem on arithmetic progressions).

It is very simple to construct an infinite sequence for the Composite-Prime case:

$$35+60n,37+60n$$

$35+60n$ will generate an infinite amount of composite numbers, all of which are divisible by $5$ (in fact, it will generate only composite numbers).

$37+60n$ will generate an infinite amount of prime numbers, since $37$ and $60$ are coprime integers (according to Dirichlet's theorem on arithmetic progressions).

Case $2$ is answered so I will address the others. For case $3$, by Dirichlet's theorem there are an infinite number of primes of the form $10 \cdot n + 3$, and $10 \cdot n + 5$ is always divisible by $5$. There is a similar example for case $4$.

• But the OP also wants the "in between" number to be a multiple of $6$, if I read the question correctly. – David Oct 22 '15 at 6:13
• @David Correct. All four sets contain numbers adjacent to a multiple of six. – Tony Oct 22 '15 at 6:28