Prove that for each positive integer $n$ there are at most two pairs $(a, b)$ of positive integers with following two properties: (i) $a^2 + b = n$, (ii) $a+b$ is a power of two, i.e. there is an integer $k \ge 0$ such that $a+b = 2^k$.
Problem
Source: Dutch BxMO TST 2019 p1
Tags: number theory
kaede
14.01.2020 01:16
Note that if $ ( a,b)$ satisfy the condition, then $ n-a^{2} +a=2^{k}$ for some $ k\geq 1$ with $ a^{2} < n$ and $ b=n-a^{2}$.
Assume that there exist a triple of positive integers $ ( x,y,z)$ which satisfies the following conditions:
(1) $ n-x^{2} +x=2^{p}$
(2) $ n-y^{2} +y=2^{q}$
(3) $ n-z^{2} +z=2^{r}$
(4) $ x^{2} ,y^{2} ,z^{2} < n$
(5) $ x >y >z$
Since $ r >q >p$, we have $ \left( 2^{q} -2^{p}\right) /2^{p} \in \mathbb{N}$.
So we have $ ( x-y)( x+y-1) /2^{p} \in \mathbb{N}$.
Since $ x-y\not\equiv x+y-1\pmod 2$, $ 2^{p} |x-y$ or $ 2^{p} |x+y-1$.
If $ 2^{p} |x-y$, $ x-y\geq 2^{p} =n-x^{2} +x\ \Rightarrow x^{2} -y\geq n\ $, but this is impossible.
So we have $ 2^{p} |x+y-1$.
If $ x+y-1\geq 2^{p+1}$, then $ x+y-1\geq 2\left( n-x^{2} +x\right) \Rightarrow y-1\geq 2\left( n-x^{2}\right) +x$.
It follows that $ x >2\left( n-x^{2}\right) +x$, and so $ n-x^{2} < 0$, but this is impossible.
So we must have $ x+y-1=2^{p} =n-x^{2} +x\ \Rightarrow x^{2} +y=n+1$.
Similarly, we have $ x^{2} +z=n+1$.
Therefore, $ x^{2} +y=x^{2} +z\ \Rightarrow \ y=z$.
This is a contradiction.
$ \blacksquare $
jeshts
12.04.2024 09:18
Assume for the sake of contradiction there exist $n$ such that there are at least 3 pairs $(x,x_1)$, $(y,y_1)$, $(z,z_1)$ that satisfy the two properties. Therefore, by PHP at least two of $x,y,z$ have the same parity. WLOG $x\equiv y \pmod 2$ and $x>y$ Let $x+x_1 = 2^a \implies x^2-x = n-2^a$. Analogously, $y+y_1 = 2^b \implies y^2-y = n-2^b$. And because $x>y$, we get $x^2-x>y^2-y \implies n-2^a > n-2^b \implies 2^a<2^b$. Notice also that $(x-y)(x+y-1) = 2^b-2^a = 2^a(2^{b-a}-1)$. And because $x\equiv y \pmod 2$, therefore $x+y-1 \equiv 1\pmod 2 \implies 2^a\mid x-y \implies x>x-y\geq 2^a$. However, since $x+x_1 = 2^a$, therefore $2^a>x>2^a$, contradiction. Hence, for each positive integer $n$ there are at most two pairs that satisfies the two properties.