Find all pairs of natural numbers $(a,b)$ satisfying the following conditions: $b-1$ is divisible by $a+1$ and $a^2+a+2$ is divisible by $b$.
Problem
Source: Russian TST 2015, Day 9 P1 (Groups A & B)
Tags: number theory, Divisibility
21.04.2023 12:54
22.04.2023 00:01
Set $t=a+1$ to get $t\mid b-1$ and $b\mid t^2-t+2$. We let $b=tk+1$ for $k\in\mathbb{N}$ to get $tk+1\mid t^2-t+2$. Further, $tk+1\mid 2tk+2$, so we get $tk+1\mid t^2-t-2tk = t(t-2k-1)$. As $(t,tk+1)=1$, we get $tk+1\mid t-2k-1$. Now I claim $t=2k+1$. Indeed, let $t>2k+1$. Then, $t-2k-1\ge tk+1$. Now, let $k=0$. Then $b=1$ and any $a$ works, yielding $(a,1)$ is the first family. Let $k\ge 1$. Then $t\ge tk+2k+2>t$, a contradiction. Likewise, if $2k+1>t$ then we get $2k+1\ge tk+t+1$, yielding $t\le 1$. This is not possible as $t=a+1\ge 2$. So, $t=2k+1$. From here, we get immediately that $(a,b)=(2k,2k^2+2k+1)$, $k\in\mathbb{N}$, is the second family.
22.04.2023 00:58
grupyorum wrote: Then, $t-2k-1\ge tk+1$, which is a clear contradiction. How so? What if e.g. $k=0$?
22.04.2023 01:42
grupyorum wrote: Set $t=a+1$ to get $t\mid b-1$ and $b\mid t^2-t+2$. We let $b=tk+1$ for $k\in\mathbb{N}$ to get $tk+1\mid t^2-t+2$. Further, $tk+1\mid 2tk+2$, so we get $tk+1\mid t^2-t-2tk = t(t-2k-1)$. As $(t,tk+1)=1$, we get $tk+1\mid t-2k-1$. Now I claim $t=2k+1$. Indeed, let $t>2k+1$. Then, $t-2k-1\ge tk+1$, which is a clear contradiction. Likewise, if $2k+1>t$ then we get $2k+1\ge tk+t+1$, yielding $t\le 1$. This is not possible as $t=a+1\ge 2$. So, $t=2k+1$. From here, we get immediately that $(a,b)=(2k,2k^2+2k+1)$, $k\in\mathbb{N}$, as the only family. I think you missed $k=0$
22.04.2023 02:35
@above: You guys are right indeed, I missed $k=0$.