# Do we have a proof of the infiniteness?

Crossposted on Mathoverflow.

Given a natural number $a$, are there infinitely many natural numbers not of the form $anm \pm m \pm n$, $n, m$ positive natural?

I give a proof that for $a=6$ the question is equivalent to the twin prime conjecture so it is known that we don't have any proof. But what about other values of $a$?

There are infinitely many twin primes if and only if there are infinitely many natural numbers that are not of the form $6nm \pm n \pm m$.

Proof: Every number that is not a multiple of $2$ or $3$ is of the form $6N\pm 1$. So the only pairs that are not divisible by $2$ or $3$ are $(6N-1,6N+1)$ for any $N$. Now are there infinitely many such prime pairs (twin primes)?

If the number $6N-1$ is prime it should not be written as a product of some numbers $6n+1,6m-1$ for any $n,m > 0$. So $(6n+1)(6m-1)=6(6nm-n+m)-1$, which means that $N$ should not be of the form $6nm-n+m$ for any $n,m>0$.

Similarly, if $6N+1$ is a prime it should not be a product of some numbers $(6n-1)(6m-1) =6(6nm-n-m)+1$, or $(6n+1)(6m+1) =6(6nm+n+m)+1$. Which means that we have a prime couple of the form $(6N-1,6N+1)$ if and only if $N$ is not of the form $6nm \pm n \pm m$ for any $n,m$.

-
Please try to use formatting! Put your math in dollar signs and it will help immensely. –  Hans Parshall Dec 21 '10 at 17:44
Also, try and make more than one paragraph out of this. –  Hendrik Vogt Dec 21 '10 at 17:58
i try if you can edit better please do –  minasteris Dec 21 '10 at 18:19
for a=2 or a=1 of course you can have all the natural numbers –  minasteris Dec 22 '10 at 13:34

Added: Unfortunately, the answer below as originally written was wrong. It answered a related, but easier, question. I have added some bracketed remarks to point out where the blunder happens, and appended some remarks about the expected answer to the actual question.

It might help to explicitly reformulate the question. (This is implicit in the proof that the question is equivalent to the twin prime conjecture for $a = 6$, but it seems worthwhile to make it explicit.)

If $k = a m n \pm m \pm n,$ then $a k \pm 1 = (a m \pm 1) (a n \pm 1).$

If $a = 2$ then we can write $1 = (2\cdot 1 - 1)$, and so for any $k$, we have $2 k - 1 = (2 \cdot 1 - 1)(2 k -1)$, and (as the OP noted) every integer $k$ can be written in the desired form. Thus we suppose from now on that $a > 2$.

The problem is then equivalent to asking if we can find infinitely many numbers congruent to $\pm 1 \bmod a$ which have no proper factors congruent to $\pm 1 \bmod a$. [Added: This is wrong. The problem is rather to find infintely many multiples $a k$ of $a$ so that both $a k +1$ and $a k - 1$ have no proper factors congruent to $\pm 1 \bmod a$.]

This shows that the answer to the question depends a lot on whether or not every residue class mod $a$ which is coprime to $a$ is congruent to $\pm 1 \bmod a$, i.e. on whether or not $\varphi(a) = 2$. [Added: It is not so clear to me now what difference the condition on $\varphi(a)$ makes, if any.]

If $\varphi(a) = 2$, then we are simply asking whether we can find infinitely many numbers coprime to $a$, which differ by $2$, and which have no proper factors, i.e. we asking for infinitely many twin primes. This is a well-known open problem!

On the other hand, suppose that $\varphi(a) > 2$ (which in particular is the case if $a > 6$). We may then choose $b$ and $c$ so that $b, c \not\equiv \pm 1 \bmod a$, and $b c \equiv 1 \bmod a$.

By Dirichlet's theorem, we may choose infinitely primes $p$ and $q$ such that $p \equiv b \bmod a$ and $q \equiv c \bmod a$.

For any such $p$ and $q$, the product $pq \equiv 1 \bmod a$, but by construction has no proper factors congruent to $\pm 1 \bmod a$. So if we set $k = (p q - 1)/a$, then $k$ cannot be written in the given form. This gives infinitely many $k$, as desired. [Added: Rather, this gives infinitely many $k$ that are not of the form $a m n + m + n$ or $a m n - m - n$, but doesn't address whether these can be written in the form $a m n - m + n$, since we don't have any control over $a k - 1 = p q - 2.] Added: It is not clear to me how to gain control over the factors of$p q - 2$, other than to assume it is prime. So one way to solve the problem would be to find infinitely many primes$r \equiv -1 \bmod a,$such that$r + 2$is either prime, or is of the form$r + 2 = p q,$where$p,q \not\equiv \pm 1 \bmod a$. This is then related to Chen's theorem, indeed is a strengthening of it. Thus we are led to MO Scribe's question on MO which was inspired by the initial posting of the present question on MO. There is no doubt that this result (on the existence of such primes$r$) is true. (Indeed, standard conjectures predict that there should be infinitely many twin primes$r, r+2$with$r\equiv -1 \bmod a$.) But it is not clear (to me) whether or not it is in reach of current methods; that is the thrust of MO Scribe's question. So what is the conclusion: Well, there is no doubt that one should be able to find infintely many such$k$, since it follows from standard conjectures on twin primes satisfying congruence conditions. On the other hand, proving this may be tricky, since it seems to require results that are at the edge of what is currently possible via seiving techniques. - Thank you very much :what about if we have φ(α)=2? – minasteris Dec 22 '10 at 16:07 @minasteris: If$\varphi(a) = 2$then$a = 3, 4,$or$6$, and it seems to be equivalent to the twin prime conjecture, as you already noticed. – Matt E Dec 22 '10 at 16:12 so the only value that you haven't answered yet is 5? – minasteris Dec 22 '10 at 16:31 Since$\phi(5) = 4$, the same argument as in my answer works for$a = 5\$. I will edit this into the answer. –  Matt E Dec 22 '10 at 16:31
@minasteris: Dear Minasteris, You're welcome (and you weren't rude, so there's nothing to apologize for). Regards, –  Matt E Dec 22 '10 at 16:55