Express an integer as ac + bd

Which positive integers $$n$$ can be expressed in the form $$n = ac + bd$$, where $$a,b,c,d$$ are positive integers and satisfy $$\gcd(a,b) = \gcd(c,d) = 1$$? I know that all numbers that are not divisible by 4 or by a prime $$p$$ of the form $$p = 4m + 3$$ can be represented this way due to the "primitive" sum of two squares theorem (see https://math.stackexchange.com/questions/1282550/asymptotic-for-primitive-sums-of-two-squares).

Edit: The interesting case is $$a \neq b, c \neq d$$.

• You probably meant some additional condition, since $a=n-1$ and $b=c=d=1$ satisfies $n=ac+bd$ and your gcd condition! Maybe you want $a,b,c,d$ to be at least $2$? – Joe Silverman Jan 22 at 18:51
• @JoeSilverman yes you are correct. I have edited the question. – Rahul Sarkar Jan 22 at 18:56
• @JoeSilverman actually the weaker condition $a \neq b, c \neq d$ is the case I want. – Rahul Sarkar Jan 22 at 19:06
• If cd is allowed to be prime, then all sufficiently large integers should be so expressible. Gerhard "Primes Make So Many Numbers" Paseman, 2020.01.22. – Gerhard Paseman Jan 22 at 19:32

More elementarily, letting a=d=1 turns the problem into representing numbers as b+c with b and c larger than 1, giving all numbers greater than 3 as possibilities.

If only d is allowed to be 1, then let bd be one of 2,4, or 6. For odd n bigger than 9, n-bd is odd and composite,for one of these choices and often not a multiple of three. The problem is if it is a power of three, in which case make a=1, c the power of three, and d=2 and b=3. For even n pick bd a prime not dividing n, then n-bd will sometimes be composite and coprime to bd (otherwise there are too many primes). There should be no n over thirty that do not succumb to such a decomposition if one of the numbers is allowed to be 1 and the two gcd conditions and inequalities apply.

When all numbers are required to be greater than 1 and mutually coprime, there should also be all but finitely many numbers so decomposed. I do not have a construction to cover all cases, but picking two coprime composites near n/2 would be a good start.

Update 2020.01.23:

So I wrote a program to generate positive integers which are not a prime nor a power of a prime.

I then ran a routine to pick a small number diff, and if d and diff were coprime and d and d+diff were both numbers generated above, then record the sum d+d+diff if it had not already been recorded.

The smallest such sum is 29, and I expected few small numbers below 100 to be represented as sums. I also expected to hit most if not all sums by keeping diff below 10 or 20.

That wasn't the case. I needed to have diff go up to 300 before I could find that numbers like 570 and 870 were sums of two coprime and properly composite numbers. I am finding 168,180,204,210,240,270,330, and 420 not of this form. (Since I am excluding prime powers and summands sharing a prime, the list of non representable numbers is larger than suggested in the original post.)

Currently I am finding numbers above 420 representable, and if I constrain diff to less than 200, all but 570 and 870 remain so within the limits of the computation. (If a number near 2*LIM is not realized, I consider that an artifact from not generating enough summands.)

This suggest the conjecture that not only are there finitely many such nonrepresentable positive integers, but that diff does not have to exceed a finite bound to realize such a sum. It may be possible to modify the answer by GH from MO to prove both statements.

End Update 2020.01.23.

Gerhard "Trying To Balance All Sides" Paseman, 2020.01.22.

• this answer is very helpful. Can you explain a bit how to show that at most finitely many numbers cannot be represented this way (when all numbers are required to be greater than 1 and mutually coprime)? – Rahul Sarkar Jan 22 at 20:07
• For odd n, if n-2 and n-4 are both prime, then n-6 is a nontrivial multiple of three. Set a=3^k, c=(n-6)/a, b=2, and d=3. Choose k so that the gcd conditions hold, and c is the only number that might be 1. For even n, choose odd numbers ac which are composite and coprime to n. If n is larger than 30, this should be possible. Then n-ac = bd is coprime to ac and sometimes is composite. If it isn't set d=1. Gerhard "It Really Is That Simple" Paseman, 2020.01.22. – Gerhard Paseman Jan 22 at 20:15
• The program listed in the updates has some curious artifacts. For example (taking sums in increasing order of diff), no sums with diff = 15,21, 27, or 33 are needed, and only 2 with diff 25 are recorded. Numbers needing diff greater than 150 are 570,660,870,4830, and 57330, with LIM=400000. Gerhard "Surprising As Covering With NearPrimes" Paseman, 2020.01.23. – Gerhard Paseman Jan 23 at 20:24

Every $$n\neq 3$$ can be written as $$n=ac+bd$$ with $$a\neq b$$ and $$c\neq d$$. Simply, take $$a=2$$, $$b=1$$, $$c=1$$, $$d=n-2$$.

It is more interesting to ask how many representations $$n=ac+bd$$ there are with $$a\neq b$$ and $$c\neq d$$. Let $$d(m)$$ and $$\sigma(m)$$ denote the number of divisors and sum of divisors of a number $$m$$. Then the number of representations of the form $$n=ac+bd$$ equals $$\sum_{k=1}^{n-1}d(k)d(n-k)=\left(\frac{6}{\pi^2}+o(1)\right)\sigma(n)(\log n)^2$$ by a result of Ingham (J. London Math. Soc. 2 (1927), 202-208). The number of representations with $$a=b$$ or $$c=d$$ is less than $$2\sigma(n)$$, hence in fact the above asymptotic formula also counts the number of representations with $$a\neq b$$ and $$c\neq d$$. In particular, the number of representations tends to infinity as $$n\to\infty$$.

• many thanks for these references though. I certainly find this very interesting! – Rahul Sarkar Jan 22 at 20:07
• Are there a lot of terms remaining (do the asymptotics remain) if a) we let k run from n/2 -1000 to n/2 + 1000, and b) also use only terms with k coprime to n? If you get in addition that each k have at least two distinct prime factors, that would also help. Gerhard "Wondering About More Restricted Sums" Paseman, 2020.01.24. – Gerhard Paseman Jan 24 at 21:19
• @GerhardPaseman: If you restrict $k$ to be coprime to $n$, then surely the right hand side needs to be modified. This is because there are more ways to write $n$ as a sum of two positive integers than as a sum of two positive integers coprime to $n$. – GH from MO Jan 24 at 21:52
• Yes, but maybe the modification is to drop the o(1) when leaving out k not coprime to n? Gerhard "That's How I'm Seeing It" Paseman, 2020.01.24. – Gerhard Paseman Jan 24 at 22:00
• @GerhardPaseman: No, I meant that the asymptotic behaviour will be different. In particular, I expect that $\sigma(n)$ would need to be adjusted as well (which is more dramatic than fiddling with the constant). – GH from MO Jan 27 at 13:47