Consider the following question:



> 
> 1) For a given natural number $a$, are there finitely or infinitely many natural numbers that are not of the form $anm \pm n\pm m$, where $m$ and $n$ range over positive integers? (For $a=1$ or $a=2$ you have all the natural numbers.)
> 
> 
> 


Does this problem appear in the literature? 


As one can see at MO Scribe's question [Chen's Theorem with congruence conditions.](https://mathoverflow.net/questions/49751/chens-theorem-with-congruence-conditions/49782#49782) it is the same like asking if there are infinitely many $k$ such that both $ak+1$ and $ak-1$ do not have any non-trivial factors of the form $\pm 1 \mod a$.


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$? Is the problem for $a=100$ or more of the same difficulty?



> 
> 2) Is the density (Szemeredi's or Schnirelman's), of the numbers that are not of the form, zero for any value of $a$?
> 
> 
> 3) From Viggo Brun's theorem we have that the sum of the reciprocals of the twin primes converges. Does the sum of the reciprocals for any value of $a$ of the numbers that are not of this form converge?
> 
> 
> 4)For a given natural number $a$ are there infinitely many $k$ such that both $ak+1$ , $ak-1$ do not have any $prime$ factors of the form $\pm 1 \mod a$? (the same questions for these $k$ as in 2) and 3) ) 
> 
> 
> 5) And the most easy : for which $a$ do we have a proof that there are infinetely many $k$ such that such that both $ak+1$ , $ak-1$ are either prime or can be written as a product of two numbers both not of the form $\pm 1 \mod a$? I guess that if $φ(a)$ is big enough we can have such a proof (the same questions for these $k$ as in 2) and 3) )
> 
> 
> 


NOTE: In 1) and 4) both both $ak+1$ and $ak-1$ can be either primes or the product of primes not of the form $\pm 1 \mod a$ ,but in the 1) no subproduct of them can be of this form.


As MO Scribe noticed the conjectural answer is that there should be infinetely many such pairs because we are aspecting to have infinitely many prime pairs of any reasonable congruence condition.


<https://math.stackexchange.com/questions/15075/do-we-have-a-proof-of-the-infiniteness> 




---


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$.


NOTE: After i have edited this observasion-question I realised that it is well known that for $a=6$ it is equivalent to twin prime conjecture (as it is written on the answer by Luis below too), a notice that S.Golomb seems to have done first, but my question is focused to the other values of $a$.


If someone want to add something <http://mathoverflow.tqft.net/discussion/921/reedited/#Item_1>



Is this a (well known)  open problem?(infinitness and more on $anm \pm n\pm m$ )
$\newcommand\Z{\mathbf{Z}}$
$\newcommand\Q{\mathbf{Q}}$


(Caveat: normally I wouldn't answer a question with such a limited knowledge of the general theory, but classical analytic number theory seems not so well represented by active MO members.)


Suppose that $A$ is a finite abelian group. Then I claim that given any set of at least $|A| + 1$ (not necessarily distinct) elements of $A$ one can find a proper subset whose sum is the identity. Proof: Denote the elements $a\_i$ for $i = 1$ to $|A|+1$. By the pigeonhole principle, either one of the $|A|$ sums $\sum\_{i=1}^{r} a\_i$ for $r = 1$ to $|A|$ is the identity, or two of the sums are the same element of $|A|$, in which case consider the difference. We deduce from this the following: Let $n$ be any integer coprime to $a$ with more than $r:=|(\Z/a \Z)^{\times}|$ prime factors. Then $n$ has a proper divisor of the form $1 \mod a$. 


Suppose that $k$ cannot be represented by the form $amn \pm m \pm n$, and suppose that $a > 2$. It is simple to deduce that this is equivalent to asking that $ak+1$ and $ak-1$ have no proper divisors of the form $\pm 1 \mod a$. It follows that $ak+1$ and $ak-1$ each have *at most* $r=|(\Z/a \Z)^{\times}|$ prime 
factors. The integers with at most $r$ prime factors
are sometimes called *$r$-almost primes*. If $\pi\_r(x)$ counts the number of $r$-almost
primes $\le x$ then 
$$\pi\_r(x) \sim \frac{x (\log \log x)^{r-1}}{\log(x)}.$$
(Compare this to the prime number theorem when $r = 1$.) In particular, we see that the
 $r$-almost primes have zero density (in any sense), and thus:



> 
> 2) The density of integers that can not be represented in the form $amn + m + n$ is zero.
>  Similarly, the density of integers that cannot be represented in the form $amn + m -n$ is zero. In particular, the density of the *$a$-asterios* numbers, the integers that can neither
>  be represented in the form $amn+m+n$ *nor* $amn+m-n$, is zero.
> 
> 
> 


Let $\pi\_{r,2}(x)$ denote the number of *twin* $r$-almost primes less than or equal to $x$, that is, the number of integers $n \le x$ such that $n$ and $n+2$
are *both* $r$-almost primes. 
(For example, $\pi\_{1,2}(x)$ counts the number of twin primes less than $x$.)
What do we know about this function? Brun was the first to give an upper bound
for $\pi\_{r,2}(x)$ using sieving techniques. Refinements by others (in particular
Selberg) allowed one to obtain the estimate
$$\pi\_{1,2}(x) \ll \frac{x}{(\log x)^2},$$
which gives the correct (conjectural) order of magnitude.
Without going into the Selberg sieve, let me say that what these arguments 
really
give is decent upper *and* lower bounds of the following kind (for large $x$):
$$\frac{A x}{(\log x)^2} <
\left\{n < x, \ p \nmid n(n+2) \ \text{if} \ p < x^{\alpha}\right\}
< \frac{B x}{(\log x)^2}$$
for non-zero constants $A$ and $B$,
where $0 < \alpha < 1$ is some fixed small constant, which we might imagine for the
sake of argument is $1/10$. Since every twin prime $>x^{\alpha}$ contributes to
this sum, this gives the correct (up to a constant) upper bound for
$\pi\_{1,2}(x)$. It also gives a *lower* bound for $\pi\_{10,2}(x)$, since if every
factor of $n < x$ is at least $x^{1/10}$, then $n$ has at most $10$ prime factors.


The motto I learnt about sieving was the following: upper bounds are easy, lower bounds are hard. Thus, since we are interested in bounding $\pi\_{r,2}(x)$, it seems that we are in good shape.
However, there is a subtlety here. Let $\pi(x,z)$ denote the number of integers $n$ less
than $x$ such that every prime factor of $n$ is at least $z$. It's clear by the
argument of the last paragraph that
$\pi\_r(x) \ge \pi(x,x^{1/r})$. One might imagine that these numbers are roughly of the
same magnitute. However, it turns out that $\pi\_r(x)$ is much bigger than $\pi(x,x^{1/r})$.
The latter is comparable to the number of primes less than $x$, where the former has
an extra factor of $(\log \log x)^{r-1}$. The reason is that $\pi\_r(x)$ is dominated
by numbers with (a few) small prime factors. In fact, 
as Kowalski pointed out to me, it is not even obvious that
one can easily obtain the
correct upper bound for $\pi\_r(x)$ simply by sieving over primes.
From the asymptotic for $\pi\_{r}(x)$, one expects that
$$(\*): \qquad \pi\_{r,2}(x) =^{?} \ O\left(\frac{x (\log \log x)^{2r-2}}{(\log x)^2}\right).$$ 
(EDIT: My resident expert reports that this is known. Here is a sketch of the idea in the simpler case where we want to count pairs $n$ and $n+2$ where $n$ is a $2$-almost prime and $n+2$ is prime.
First, for a small prime $p$, we want to find an upper bound for the number of $n < x$ such that $n$ is divisible by $p$ and both $n/p$ and $n+2$ are prime. This is a similar problem to counting twin primes, and in a similar way one obtains a bound of the form $O(x/\log x)$ (key point: the implied constant does not depend on $p$). If we wish to bound the number of pairs $(n,n+2)$ such that $n+2$ is prime and $n$ is a $2$-almost prime, we may instead count the triples $(p,n,n+2)$ where
$p < x$ is prime, $n < x$ is divisible by $p$, $n/p$ is prime, and $n+2$ is prime. If for each $p < x$ we have a upper bound of $Ax/\log x$ (for the same $A$), in total we obtain the upper bound:
$$ \frac{Ax}{\log x} \cdot \sum\_{p < x} \frac{1}{p} \sim \frac{Ax \log \log x}{\log x}.$$
Of course, the devil is in the details! END EDIT)
All one needs to answer 3) is that 
 the exponent of $\log(x)$ in the denominator is $> 1$. 



> 
> 3). Assuming the expected result (\*), the inverse sum of the *$a$-asterios* primes converges.
> 
> 
> 


Consider the set of integers $S\_a$
which do not have any prime factors of the form
$\pm 1 \mod a$. This is a reasonable thing to do whenever
$|(\Z/a\Z)^{\times}| > 2$. This is a weaker condition, so there are more of these numbers 
and consequently obtaining upper bounds is harder. 
We may form the Dirichlet series
$$L(s) = \sum\_{S\_a} \frac{1}{n^s}$$
which has an Euler product:
$$L(s) = \prod\_{p \not\equiv \pm 1} \left(1 - \frac{1}{p^s}\right)^{-1}$$
Now let $K = \Q(\zeta\_a)^{+}$ be the totally real subfield of $\Q(\zeta\_a)$.
It has degree $r/2 = \phi(a)/2$, where $r > 2$ unless $a = 1,2,3,4$ or $6$.
(What we say now only makes sense for $r \ge 2$, in which case $r/2 \in \Z$.)
A prime splits completely in $K$ if and only if it is of the form
$\pm 1 \mod a$. Looking at the Euler product of $\zeta\_K(s)$, we see that,
up to a constant 
 which can be explicitly written as some product over primes,
$$\zeta\_K(s) L(s)^{r/2} \sim \zeta\_{\Q}(s)^{r/2}$$
as $s \rightarrow 1^{+}$, and hence $L(s) \sim (s-1)^{(2-r)/r}$ 
(up to some constant)
 as $s \rightarrow 1^{+}$. We deduce (Perron's formula) that the number
of integers $\le x$
all of whose prime factors are not of the form $\pm 1 \mod a$ is
asymptotic to
$$ \kappa \cdot \frac{x}{(\log x)^{2/r}},$$
for some non-zero
constant $\kappa$. This is the same analysis that gives the asymptotic
formula for the number of integers $\le x$ which can be written as a sum
of two squares (a result of Landau). 
We immediately deduce:



> 
> 4a) The number of integers $a$ such that $ak+1$ (or $ak-1$) has no
>  prime factors of the form $\pm 1 \mod a$ has zero density.
> 
> 
> 


If $r > 2$ (so $a \ge 3$ and $a \ne 3,4,6$) then the power $2/r$ of
 $(\log x)$ is at most $1/2$. Thus, we actually
are led to the following guess:



> 
> 4b) If $r = \phi(a) > 2$, then one would heuristically expect the inverse
>  sum of integers $k$ such that none of the prime factors of $ak-1$ and $ak+1$ 
>  are $\pm 1 \mod a$ diverges. If $r = 2$, so $a = 3$, $4$, or $6$, then (Brun) the series converges.
> 
> 
> Here is a related problem of the very same kind: can one count the number of
>  integers $n \le x$ such that both $n$ and $n+1$ can be expressed as the sum of
>  two squares, and prove that there are $\sim x/\log(x)$ such integers
>  (perhaps up to non-zero constant factors)?
> 
> 
> 


Any integer $n$ can be written as the product of two numbers not
of the form $\pm 1$ *unless* every prime factor of $n$ is of the
form $\pm 1 \mod a$. The integers all of whose prime factors are
$\pm 1 \mod a$ can be analyzed exactly as in the last paragraph.
In this case, the number of integers all of whose prime factors are of the
form $\pm 1 \mod a$ is asymptotic to
$$ \kappa \cdot \frac{x}{(\log x)^{(1-2/r)}}.$$
Suppose that $r > 2$. Then the set of such integers has density zero, and thus the
set of integers which have a factor *not* of the form $\pm 1 \mod a$
has density one. Any set of density one has infinitely many 
"twins" satisfying any fixed congruence condition.
Hence:



> 
> 5) If $r = \phi(a) > 2$, then there are infinitely many $k$ such that both
>  $ak+1$ and $ak-1$ have a factor *not* of the form $\pm 1 \mod a$. Indeed, such numbers have density one.
> 
> 
> 


Finally, I have nothing to say about problem 1) besides the remarks I made in my rephrasing of the original question here:


[Chen's Theorem with congruence conditions.](https://mathoverflow.net/questions/49751/chens-theorem-with-congruence-conditions)


