Minimal representation of numbers which are the difference between two squares

Question

Most natural numbers can be written as the difference between two squares. For such a number $n=a^2-b^2$, are there methods to get the least $a$ such that there is a $b\in\mathbb N$ with $n=a^2-b^2$?

Answer 1

I'm sorry, my previous answer was critically flawed - it found the maximum $a$ for which $n = a^2 - b^2$, rather than the minimum. For example, when $n = 15$, it suggested the maximal $a = 8$ and $b = 7$, rather than the minimal $a = 4$ and $b = 1$. I've made the necessary fix (and added more detail) in this answer below.

As claimed earlier, if $n = a^2 - b^2$, then $n \equiv 0, 1$ or $3 \pmod{4}$. To see this, observe that $a^2, b^2 \in \{0, 1\} \pmod{4}$, so there is no way their difference can be $2 \pmod{4}$.

We are given $n = a^2 - b^2 = (a + b)(a - b)$, so we have to look for a suitable pair of divisors $p = a+b$ and $q = a-b$ with $n = pq$. Note that $a = \frac12 (p+q)$ and $b = \frac12(p-q)$. Hence we want to minimise $p + q$ subject to $pq = n$.

When fixing the product of two numbers, their sum is minimised when they are as close to one another as possible. Observe that $q = \frac{n}{p}$, and so $p + q = p + \frac{n}{p}$. A little straightforward calculus shows that this takes a minimum at $p = \sqrt{n}$.

However, since $p = a + b$, and $a, b \in \mathbb{N}$, we must have $p \in \mathbb{N}$ as well. We know that $p \ge \sqrt{n} \ge q$, and so we must look for the factorisation of $n$ into two factors that are as close to $\sqrt{n}$ as possible. Since there are fewer numbers below $\sqrt{n}$ than above it, one way of doing this would be to start at $\sqrt{n}$ and then count down until you find a divisor of $n$ (which would be our $q$). Note that if $\sqrt{n} \in \mathbb{N}$ and you do not consider $0 \in \mathbb{N}$, then you should not allow $p = q = \sqrt{n}$, since that corresponds to $a = \sqrt{n}$ and $b = 0$.

There is one thing left to check: we need $a = \frac12(p+q)$ to be an integer. If $n$ is odd, then both $p$ and $q$ must be odd, so $p+q$ must be even, so we need not worry.

If $n$ is even, then by our first remark we must have $n = 4n'$ for some $n' \in \mathbb{N}$. Since $pq = n$, at least one of $p, q$ must be even. However, if one is even and the other is odd, then $\frac12(p+q)$ will not be an integer, so we only want to consider factorisations of $n$ into a pair of even numbers. We can simplify this by letting $p = 2p'$, $q = 2q'$. Note that we then have $p'q' = n'$, and $a = \frac12(p+q) = p' + q'$ is guaranteed to be an integer. We also have $\sqrt{n} = 2 \sqrt{n'}$, so if $p'$ and $q'$ are close to $\sqrt{n'}$, then $p$ and $q$ are close to $\sqrt{n}$. Hence we should search for a factorisation of $n'$ with the factors as close to $\sqrt{n'}$ as possible (without worrying about any parity concerns), and then take $a = p' + q'$ for $n$.

Finally, for some worked (and relatively randomly chosen) examples:

If $n = 379$, then $\sqrt{n} = 19.4679...$. The largest number no bigger than $19$ that divides $379$ is $1$, since $379$ is prime (bad random choice!). Hence we take $q = 1$ and $p = 379$, giving $a = \frac12(379 + 1) = 190$ and $b = \frac12(379-1) = 189$.

If $n = 1485$ (no way this is prime!), then $\sqrt{n} = 38.5356...$. The largest number not bigger than $38$ that divides $1485$ is $33$, with $1485 = 33 \times 45$. Hence we take $p = 45$ and $q = 33$, giving $a = \frac12(45 + 33) = 39$ and $b = \frac12(45-33) = 6$.

If $n = 1264$, then $4 | n$, so we take $n' = 316$. Then $\sqrt{n'} = 17.7763...$. The largest number not bigger than $17$ that divides $316$ is $4$, with $316 = 4 \times 79$. Hence we take $p' = 79$ and $q' = 4$, giving $a = 79 + 4 = 83$, and $b = 79 - 4 = 75$.

Sorry again for misleading you initially, and I hope this clears things up.

Answer 2

For odd $n = 2k+1$ you can go for $a = k+1, b = k$. We have $2k+1 = (k+1-k)(k+1+k)$. For even and divisible by 4, i.e., $n = 4k$ take $a = k+1, b = k-1$. We have $4k = (k+1-(k-1))(k+1+k-1))$.

In the last case, i.e., $n = 4q+2$ if we suppose that $4q+2= (a-b)(a+b)$ then it follows that either both $a,b$ are even or both $a,b$ are odd (because at least one of $a-b,a+b$ must divide $4q+2$). If $a-b > 1$, then the right-hand side must be divisible by 4, a contradiction. Thus $a-b = 1$ and $4q+2 = (1)(2b+1)$, again a contradiction. Thus, in this case such $a$ and $b$ don't exist.