Finding $(a,b)\in\mathbb{N}^2$ such that $\dfrac{a^2+b^2+1}{a+b} \in \mathbb{N}$.

Question

A pair $(a,b)\in\mathbb{N}^2$ is called good if $a < b$ and $$\frac{a^2+b^2+1}{a+b}\in\mathbb{N}.$$ I think I've shown that there are infinitely many good pairs. However, the family of good pairs that I've found is not all of them, and the argument is not as elementary as I'd like. Observation: we can check small values to show that good pairs do indeed exist, e.g. $(1,2),\, (4,7),\,(5,12),\, (11,16)$.

To construct an infinite family of good pairs, suppose we have $$\frac{a^2+b^2+1}{a+b}=k\in\mathbb{N},$$ then $a^2+b^2+1 - k(a+b)=0$, and completing the square for $a$ and $b$ gives the equation for a circle: $$\left(a-\frac{k}{2}\right)^2+\left(b-\frac{k}{2}\right)^2 = \frac{k^2}{2}-1$$ $$\implies a = \frac{k}{2} + \sqrt{\frac{k^2}{2}-1-\left(b-\frac{k}{2}\right)^2}.$$ Let $k=2j$ for some $j\in\mathbb{N}$ to eliminate the fractions, obtaining $a=j+\sqrt{j^2-1-b^2+2jb}$. In order to have $a\in\mathbb{N}$, we must have $j^2-1-b^2+2bj=n^2$ for some $n\in\mathbb{N}\cup\{0\}$. We can view this as a quadratic in $b$: $$b^2-2jb+(n^2+1-j^2)=0.$$ Since we require $b\in\mathbb{N}$, the discriminant $\Delta$ must be of the form $\Delta = 4m^2$ for some $m\in\mathbb{N}\cup\{0\}$. Thus we have the following expressions for $a$ and $b$: $$b=\dfrac{2j\pm\sqrt{\Delta}}{2} = j+m, \qquad a = j + \sqrt{n^2} = j+n.$$ Considering the discriminant: $$\Delta = (-2j)^2 - 4(n^2+1-j^2) = 4m^2$$ $$\implies 2j^2-1 = m^2+n^2.$$ If $a<b$ we must have $n<m$. In particular, we can assume $n=0$ without restricting $m$. Then we have $m^2-2j^2=-1$, and so we have a correspondence between certain good pairs $(a,b)$ and elements of norm $-1$ in $\mathbb{Q}(\sqrt{2})$. For $x+y\sqrt{2}\in\mathbb{Z}[\sqrt{2}]$, define $N(x+y\sqrt{2})=x^2-2y^2$, and observe that this function is multiplicative. We have $N(1\pm\sqrt{2})=-1$, and thus $N((1\pm\sqrt{2})^{2r-1})=(-1)^{2r-1}=-1$ for any $r\in\mathbb{N}$. Let $m+j\sqrt{2} = (1+\sqrt{2})^{2r-1}$ and so $m-j\sqrt{2} = (1-\sqrt{2})^{2r-1}$. We can combine these expressions to obtain the following general formulas for values of $m$ and $j$: $$m_r = \frac{(1+\sqrt{2})^{2r-1}+(1-\sqrt{2})^{2r-1}}{2},\qquad j_r = \frac{(1+\sqrt{2})^{2r-1}-(1-\sqrt{2})^{2r-1}}{2\sqrt{2}}.$$ Then we have $a=j+n=j$ and $b=m+j$, thus we have an infinite family of good pairs $(a_r,b_r)$ for $r\in\mathbb{N}$ given by: $$a_r = \frac{(1+\sqrt{2})^{2r-1}-(1-\sqrt{2})^{2r-1}}{2\sqrt{2}},\qquad b_r = \frac{(1+\sqrt{2})^{2r}-(1-\sqrt{2})^{2r}}{2\sqrt{2}}.$$ The first few values of $r$ gives the good pairs $(1,2),\,(5,12),\,(29,70),\,(169,408),(985,2378)$ with corresponding values of $k=2,10,58,338, 1970$.

I seek advice both on this proof itself (i.e. does it work?) and also in seeking a more elementary argument (i.e. without requiring knowledge about $\mathbb{Q}(\sqrt{2})$ and the like) - it doesn't necessarily need to be constructive, in fact it would be interesting to know if there exists a more concise argument to that effect.

Regarding finding good pairs themselves, comparing the list constructed in my solution to thta of the observation, it's clear that this solution 'misses' some pairs - and this comes a no surprise since we disregard the cases that $k$ is odd, and $n>0$.

If $k=2j-1$, then we can use a similar method to show $j^2-j-b^2+2jb-b=n^2-n$ for some $n\in\mathbb{N}$, but I haven't been able to make any progress from this. The case for $k$ even and $n>0$ is essentially asking "when can $2j^2+1$ be written as the sum of two squares", which I'm not sure quite how to answer - using known results about sums of two square seems difficult as $2j^2+1$ has no general factorisation.

Are there totally different methods that can be used to construct more families of good pairs? And what about any other 'structure' to good pairs? It seems interesting that units in $\mathbb{Z}[\sqrt{2}]$ give rise to the solutions, can a more general statement be made?

Answer 1

In the following let us not assume $a<b$ for simplicity (basically this gives the same results except we might get some $(a,b)$ with $a=b$). Note that $$0<\frac{a^2+b^2+1}{a+b}=-(a-b)+\frac{b^2-a^2+a^2+b^2+1}{a+b},$$ so what we need to do is to find all $(a,b)\in\mathbb N^2$ such that $\frac{2b^2+1}{a+b}\in\mathbb N$. So, we immediately find solutions $(2b^2+1-b,b)\in\mathbb N^2$.

In fact, given any $f(x)\in\mathbb Z[x]$ such that $2f(x)^2+1$ has a factor $g(x)$, we can construct a family of solutions $(g(n)-f(n),f(n))$ whenever $g(n)>f(n)$.

Answer 2

your ratio $k$ must satisfy $k \equiv 2 \pmod 4.$ The relation is $ a^2 + b^2 + 1 = ka + kb.$ We write this as $$ (2a-k)^2 + (2b-k)^2 = 2 k^2 - 4$$
If $ k$ were odd, $2 (k^2 - 2)$ would be two times a number $7 \pmod 8$ and not the sum of integer squares. If $k$ were divisible by $4,$ we could write $k=4t,$ then $2k^2 - 4 = 32t^2 - 4 = 4(8t^2-1)$ would be four times a number $7 \pmod 8$ and not the sum of integer squares.

Then, writing $ k = 4 w+2$ with $ w \geq 0,$ there are integer points giving that ratio precisely when $$ 8 w^2 + 8 w + 1 $$ factors as the sum of two squares. This means that, for any prime $q \equiv 3 \pmod 4$ that divides $ 8 w^2 + 8 w + 1, $ the exponent of that $q$ is even.

Next morning: as our number $ 8 w^2 + 8 w + 1 = 2 (2w+1)^2 -1, $ it follows that $2$ is a quadratic residue mod any prime divisor, so that anny prime divisors are $p \equiv 1,7 \pmod 8.$ In order to discard predictable $w$ as far as small primes:

Don't use $w \equiv 2,4 \pmod {7}$ unless we also have $w \equiv 2,46 \pmod {49}$

Don't use $w \equiv 4,18 \pmod {23}$ unless we also have $w \equiv 225, 303 \pmod {529}$

Don't use $w \equiv 13, 17 \pmod {31}$ unless we also have $w \equiv 451, 509 \pmod {961}$

Don't use $w \equiv 13, 33 \pmod {47}$ unless we also have $w \equiv 671, 1537 \pmod {2209}$

$$ \bigcirc \bigcirc \bigcirc \bigcirc \bigcirc \bigcirc \bigcirc \bigcirc \bigcirc \bigcirc \bigcirc \bigcirc \bigcirc \bigcirc \bigcirc \bigcirc \bigcirc \bigcirc \bigcirc \bigcirc \bigcirc \bigcirc \bigcirc \bigcirc $$

$w=0, 8 w^2 + 8w + 1 = 1$

$w=1, 8 w^2 + 8w + 1 = 17 = 4^2 + 1$

$w=2, 8 w^2 + 8w + 1 = 49 = 7^2$

$w=3, 8 w^2 + 8w + 1 = 97= 9^2 + 4^2$

$w=4, 8 w^2 + 8w + 1 = 161= 7 \cdot 23$ NO!

$w=5, 8 w^2 + 8w + 1 = 241= 15^2 + 4^2$

$w=6, 8 w^2 + 8w + 1 = 337= 16^2 + 9^2$

$w=7, 8 w^2 + 8w + 1 = 449= 20^2 + 7^2$

$w=8, 8 w^2 + 8w + 1 = 577= 24^2 + 1^2$

$w=9, 8 w^2 + 8w + 1 = 721= 7 \cdot 103$ NO!

$w=10, 8 w^2 + 8w + 1 = 881= 25^2 + 16^2$

Recall, your ratio $k$ is $k = 4w+2 $ So far, $k=18, 38$ fail to have integer points

$$ \bigcirc \bigcirc \bigcirc \bigcirc \bigcirc \bigcirc \bigcirc \bigcirc \bigcirc \bigcirc \bigcirc \bigcirc \bigcirc \bigcirc \bigcirc \bigcirc \bigcirc \bigcirc \bigcirc \bigcirc \bigcirc \bigcirc \bigcirc \bigcirc $$

$w=11, 8 w^2 + 8w + 1 = 1057= 7 \cdot 151$ NO!

$w=12, 8 w^2 + 8w + 1 = 1249= 32^2 + 15^2$

$w=13, 8 w^2 + 8w + 1 = 1457= 31 \cdot 47$ NO!

$w=14, 8 w^2 + 8w + 1 = 1681= 41^2 = 40^2 + 9^2$

$w=15, 8 w^2 + 8w + 1 = 1921= 17 \cdot 113= 39^2 + 20^2 = 36^2 + 25^2$

$w=16, 8 w^2 + 8w + 1 = 2177= 7 \cdot 311$ NO!

$w=17, 8 w^2 + 8w + 1 = 2449= 31 \cdot 79$ NO!

$w=18, 8 w^2 + 8w + 1 = 2737= 7 \cdot 17 \cdot 23$ NO!

$w=19, 8 w^2 + 8w + 1 = 3041= 55^2 + 4^2$

$w=20, 8 w^2 + 8w + 1 = 3361= 56^2 + 15^2$

In case you are worried about an infinite number of distinct ratios, we may take $w$ in the infinite sequence $$ 0, 2, 14, 84, 492, 2870, ... $$ obeying $$ w_{j+2} = 6 w_{j+1} - w_j + 2 .$$ For these values, $8 w^2 + 8w + 1$ is itself a perfect square.

Answer 3

As supersuper pointed out, $\frac{a^2+b^2+1}{a+b}\in\mathbb{N}$ is equivalent to $a+b|2a^2+1$. Then for all $a\in N$, for all $a<d|2a^2+1$, either the pair $(a,d-a)$ or the pair $(d-a,a)$ is good. This generates all good pairs, because in every good pair, $a+b$ is a divisor $d|2a^2+1$, and it's greater than $a$. In fact, it generates each good pair twice, because if $d=a+b$ divides $2a^2+1$, then it also divides $2b^2+1$. This means we can replace the restriction $a<d$ with $2a<d$, and only consider the pairs $(a,d-a)$ which are precisely the good pairs. If there is a faster way to generate all good pairs than factoring $2a^2+1$, it might lead to a faster way to factor numbers of the form $2a^2+1$, which would probably be useful. These are the $7$ examples you mentioned, expressed in the form described above:

$(1,2) = (1,3-1) = (1,\frac{2\cdot1^2+1}{1}-1),\ \ \ \ (4,7) = (4,11-4) = (4,\frac{2\cdot4^2+1}{3}-4),\ \ \ \ (5,12) = (5,17-5) = (5,\frac{2\cdot5^2+1}{3}-5),\ \ \ \ (11,16) = (11,27-11) = (11,\frac{2\cdot11^2+1}{9}-11),\ \ \ \ (29,70) = (29,99-29) = (29,\frac{2\cdot29^2+1}{17}-29),\ \ \ \ (169,408) = (169,577-169) = (169,\frac{2\cdot169^2+1}{99}-169),\ \ \ \ (985,2378) = (985,3363-985) = (985,\frac{2\cdot985^2+1}{577}-985)$

And here are the good pairs with $a\le 20$ which aren't covered by the previous solutions and haven't been explicitly mentioned:

$(7,33-7), (8,43-8), (10,67-10), (11,81-11), (13,113-13), (14,131-14), (15,41-15), (16,171-16), (17,193-17), (18,59-18), (19,241-19), (20,89-20), (20,267-20)$

Answer 4

$a^2-b^2$ = $(a-b)(a+b)$ is divisible by a+b, so $a^2+b^2+1$ is divisible by a+b if and only if $2a^2+1$ is.

To find all solutions with a, b >= 1:

Iterate through a = 0, 1, 2, …
Let z = 2a^2+1
Determine all divisors d of z. 
For each d >= a, (a, d-a) is a solution. 

Since z is divisible by z, we have the obvious b = z - a for each a. For example, a = 5, z = 51, b = 46, and $5^2 + 46^2 + 1 = 2142 = 51 \cdot 42$. Other divisors of z are 1, 3 and 17, leading to be = 17-5 = 12, and $5^2 + 12^2 + 1 = 170 is divisible by a+b = 17.

The values z have on average fewer divisors than random integer of the same size, since they are never divisible by 2, 5, 7, 11, or 13.