# Natural numbers large enough can be written as $ab+ac+bc$ for some $a,b,c>0$

Conjecture: Any integer $n>462$ can be written as $n=ab+ac+bc$, where $a,b,c\in\mathbb Z_+$.

Tested for all $n\leq 100,000$, but I would like to see a proof.

The exceptions seems to be $\{1,2,4,6,10,18,22,30,42,58,70,78,102,130,190,210,330,462\}$

It's funny, I played around with BigZ and found that every odd prime seemed to be on the form. I was going to post on that, but then I found that almost any number where on this form. And now it turns out that it depends on the Generalized Riemann Hypothesis.

• are a ,b and c unique ? – user451844 Jul 27 '17 at 14:28
• @RoddyMacPhee, no they are allowed to be equal. – Lehs Jul 27 '17 at 14:32
• Using Jaap's formula, If $n+c^2=r^2$ you are done, so if $n$ is odd or divisible by $4$ you can use $c=\frac{n-1}{2},r=\frac{n+1}{2}$ when $n$ odd. If $n$ is divisible by $4$, then $c=\frac{n}{4}-1,r=\frac{n}{4}+1$. So you only need to consider the case $n\equiv 2\pmod{4}$. This gives $(a,b,c)=\left(1,1,\frac{n-1}{2}\right)$ for $n$ odd and $(a,b,c)=\left(2,2,\frac{n}{4}-1\right)$ when $n$ divisible by $4$. – Thomas Andrews Jul 27 '17 at 14:49
• See Bowein and Choi, On the representations of $xy + yz + zx,$ Exper. Math. 2000, 153-158 $\ \$ – Bill Dubuque Jul 27 '17 at 15:20
• @Lehs: Correction. You have it opposite. The remaining possibility cannot occur if we assume the Generalized Riemann Hypothesis. Thus, if GRH is true, your list is complete. – Tito Piezas III Jul 27 '17 at 15:50

In their paper On the representations of xy+yz+zx,xy+yz+zx, Exper. Math. 2000, 153-158, Borwein and Choi prove that only one other possible solution exists ($> 10^{11}$) and that cannot occur if we assume the Generalized Riemann Hypothesis.

This problem is closely connected to old problems on class numbers of imaginary quadratic fields, e.g. see the excerpt below from the Putnam collection by Kedlaya, Poonen, Vakil.

• As a related topic, the idoneal number might be helpful, though that has $0<a<b<c$, compared to the OP's $0<a\leq b\leq c$. – Tito Piezas III Jul 27 '17 at 15:54

Not an answer, just a reduction to one particular class of cases.

Claim: If there is a prime $p<2\sqrt{n}$ such that $p\not\mid n$ and $-n$ is a square modulo $p$, then such $a,b,c$ exist.

When $n>1$ is odd, we have $(a,b,c)=\left(1,1,\frac{n-1}{2}\right)$.

When $n>4$ is divisible by $4$, we have $(a,b,c)=\left(2,2,\frac{n}{4}-1\right)$.

So we only need to solve for $n\equiv 2\pmod{4}$.

As JG pointed out, if $n+1$ is not prime, with factorization $n+1=uv$, $u,v>1$, then we get $(a,b,c)=(1,u-1,v-1)$.

So we've reduced to when $n+1\equiv 3\pmod{4}$ is a prime.

[I suppose that all these cases can be seen via Jaap's comment about seeking $c$ so that $n+c^2=rs$ with $r,s>c$. In the case $c=1$ give us the odd case or $n+1$ composite, the case $c=2$ gives the case $n$ divisible by $4$.]

We will proceed using Jaap's comment:

If there exists $c$ such that $n+c^2=rs$ for some $r,s>c$, then we can choose $(a,b,c)=(r-c,s-c,c)$.

Let $p$ be a prime relatively prime to $n$ such that $-n$ is a square modulo $p$.

Then $n+c^2$ is divisible by $p$ for some $\frac{p-1}{2}<c<p$.

If $d=\frac{n+c^2}{p}$, we want $d>c$ to ensure a solution.

So we want $$pc<n+c^2$$

But $c^2-pc+n=\left(c-\frac{p}{2}\right)^2+n-\frac{p^2}{4}$.

So if $p^2\leq 4n$ then this value is positive, and we get $d>c$ and hence $(a,b,c)=(p-c,d-c,c)$.

This explains why $462$ is a good candidate to fail - $462=2\cdot 3\cdot 7\cdot 11$, so $-462$ needs to not be square modulo $5,13,17,19,23,29,31,37,41$. Essentially, for large $n$ we need a lot of distinct prime factors.

It also explains why $n$ tends to be square-free in the examples.

If $p^2\mid n$ then $n+p^2=p^2\left(1+\frac{n}{p^2}\right)$ so if $p^2\mid n$ then $1+\frac{n}{p^2}\leq p$, and it must be prime. If it is not prime, then $n+p^2=(pa)(pb)$ where $ab=1+\frac{n}{p^2}$. That gives us that if $n$ has a square factor then $n=p^2(q-1)$ for some prime $q\leq p$, and there must be no solution to $ab+ac+bc=q-1$.

If $d\mid n$ then $d+\frac{n}{d}$ must not be factorizable as $ab$ with $a>1,b>d$, or otherwise, $n+d^2$ is factorizable as $(ad)(b)$.

But if $d+\frac{n}{d}\geq d^2$ this means that $d+\frac{n}{d}$ must be prime.

So, if $d\mid n$ and $d\leq \sqrt[3]{n}$, you must have $d+\frac{n}{d}$ prime.

• all odd numbers>1 are covered take a=b=c=1 we get 1+1+1 = 3 increasing a by 1 we get 2+2+1=5 , then doing so again we get 3+3+1 =7 etc. – user451844 Jul 27 '17 at 15:21
• okay never said I was smart, to say so would be a lie. – user451844 Jul 27 '17 at 15:25