Find all pairs of natural numbers $a,b$ , with $a\ne b$ , such that $a+b$ and $ab+1$ are powers of $2$.
Problem
Source: 2015 Argentina OMA Finals L3 p2
Tags: number theory, power of 2
23.07.2023 22:20
parmenides51 wrote: Find all pairs of natural numbers $a,b$ , with $a\ne b$ , such that $a+b$ and $ab+1$ are powers of $2$. $\color{blue}\boxed{\textbf{Answer:}(1,2^k-1)(2^k-1,2^k+1)}$ $\color{blue}\boxed{\textbf{Proof:}}$ $\color{blue}\rule{24cm}{0.3pt}$ $\text{WLOG } a<b$ $$a+b=2^p, ab+1=2^q$$$\color{red}\boxed{\textbf{If a=1}}$ $\color{red}\rule{24cm}{0.3pt}$ $$\Rightarrow b=2^p-1$$$$\Rightarrow (2^p-1)+1 \text{ is a power of }2 \checkmark$$$$\Rightarrow (1, 2^p-1) \text{ is a solution}$$$\color{red}\rule{24cm}{0.3pt}$ $\color{red}\boxed{\textbf{If }a>1}$ $\color{red}\rule{24cm}{0.3pt}$ $$\Rightarrow (a-1)(b-1)\ge 1$$$$\Rightarrow ab+1\ge a+b$$$$\Rightarrow a+b|ab+1$$$$\Rightarrow a+b|ab+1-(a+b)a$$$$\Rightarrow a+b|-a^2+1$$$$\Rightarrow a+b|a^2-1$$$$\Rightarrow 2^p|(a-1)(a+1)$$$$\Rightarrow a \text{ is odd}$$$$\Rightarrow 2^{p-1}|a-1 \text{ or }a+1$$$$\Rightarrow a=2^{p-1}t\pm 1<2^{p} \Rightarrow t=1$$$$\Rightarrow a=2^{p-1}\pm 1$$$$\text{If }a=2^{p-1}+1\Rightarrow b=2^{p-1}-1 \Rightarrow a>b(\Rightarrow \Leftarrow)$$$$\Rightarrow a=2^{p-1}-1 \Rightarrow b=2^{p-1}+1$$$$\Rightarrow (2^{p-1}-1)(2^{p-1}+1)+1 \text{ is a perfect square}\checkmark$$$\color{red}\rule{24cm}{0.3pt}$ $$\Rightarrow \boxed{(1, 2^k-1), (2^k-1, 2^k+1)\textbf{ are the only solutions}}_\blacksquare$$$\color{blue}\rule{24cm}{0.3pt}$