# A diophantine equation in $\mathbb{N}$

While I was working on a paper on graph theory, I encountered a problem which I think is a number-theory-problem. I don't know if there are any tools to answer the question.

Find all natural numbers $n$, or prove there are infinitely many $n$, such that the equation $ab+bc+ca=n$ has no answer in $\mathbb{N}$.

Can help me or introduce some tools to answer this question?

Thanks

• Setting $a = 0$ we always get a solution (if this is allowed). If not, setting $a = 1$ it is not that hard to see how to get a solution whenever $n+1$ is not prime. I don't know if there is a way to find solutions for $n+1$ prime yet... (edit: For clarity: If $a = 1$, we have $n+1 = (b+1)(c+1)$, this has always a solution if $n+1$ is not prime). – Dirk Sep 27 '17 at 11:39
• oeis.org/A025052 (the remark "probably the list is complete" means that your question "probably" will not be settled here). – Mikhail Tikhomirov Sep 27 '17 at 11:45
• Related discussions at mathoverflow.net/questions/6388/… and mathoverflow.net/questions/33411/… – Gerry Myerson Sep 27 '17 at 13:28
• Actually, the OEIS entry comments that According to Borwein and Choi, if the Generalized Riemann Hypothesis is true, then this sequence has no larger terms, otherwise there may be one term greater than $10^{11}$. So, while there is uncertainty about the full list, there are definitely only finitely many. – Emil Jeřábek Sep 27 '17 at 13:33

This is an elaboration of Emil Jeřábek's important comment, and contains no original contribution. The OP's problem was examined in depth by Borwein-Choi (1999), and their article is available for free here. I will summarize the content of this article below.

Let us consider an integer $n\geq 2$ that cannot be written as $ab+bc+ca$ with integers $a,b,c\geq 1$. Using Lemma 1.1 with $k=1$, we see that $n$ is even. Using Theorem 2.6, it follows that either $n\in\{4,18\}$ or $n=2p_1\dots p_r$ with distinct odd primes $p_j$. The proof of these two results are elementary but highly nontrivial. Then, using some results of Andrews and Crandall, the authors deduce that the class number $h(-4n)$ equals $2^r$ (which is the number of genera of discriminant $-4n$). It is classical that $h(-4n)$ is of size $n^{1/2+o(1)}$ while $2^r=n^{o(1)}$, hence the list of exceptional $n$'s is certainly finite. In fact, Weinberger (1973) analyzed the condition $h(-4n)=2^r$ carefully, and this way we know that either $$n\in\{2,4,6,10,18,22,30,42,58,70,78,102,130,190,210,330,462\},$$ or $n$ is possibly a further single number beyond $10^{11}$. The last possibility can only occur if the Generalized Riemann Hypothesis (GRH) fails for the $L$-function of some quadratic Dirichlet character.

To summarize, there are $18$ exceptional integers $n\geq 1$ if GRH holds, and possibly one further exceptional $n\geq 1$ if GRH fails. (In the above paragraph I restricted to $n\geq 2$ for convenience.)

equation:

$$XY+XZ+YZ=N$$

Solutions in integers can be written by expanding the number of factorization: $N=ab$

And using solutions of Pell's equation: $p^2-(4k^2+1)s^2=1$

$k$ -some integer which choose on our own.

Solutions can be written:

$$X=ap^2+2(ak+b+a)ps+(2(a-2b)k+2b+a)s^2$$

$$Y=2(ak-b)ps+2(2ak^2+(a+2b)k+b)s^2$$

$$Z=bp^2-2(2b+a)kps+(4bk^2-2ak-b)s^2$$

And more:

$$X=-2bp^2+2(k(4b+a)+b)ps-2((4b+2a)k^2+(2b-a)k)s^2$$

$$Y=-(2b+a)p^2+2(k(4b+a)-b-a)ps-(8bk^2-(4b+2a)k+a)s^2$$

$$Z=bp^2-2(2b+a)kps+(4bk^2-2ak-b)s^2$$

Perhaps these formulas for someone too complicated. Then equation:

$$XY+XZ+YZ=N$$

If we ask what ever number: $p$

That the following sum can always be factored: $p^2+N=ks$

Solutions can be written.

$$X=p$$

$$Y=s-p$$

$$Z=k-p$$

• The OP is asking for $n$ for which there aren't positive integer solutions to $ab + ac + bc = n$. – Todd Trimble Sep 27 '17 at 12:17
• @ToddTrimble can't be an infinite number of such numbers. – individ Sep 27 '17 at 12:27
• I am looking for $n$ such that the equation has no answer in positive integers... – A. Mpi Sep 27 '17 at 12:55
• @individ Would love to see a proof for that. – Mikhail Tikhomirov Sep 27 '17 at 13:03