Determine all pairs $(a, b)$ of integers having the following property: there is an integer $d \ge 2$ such that $a^n + b^n + 1$ is divisible by $d$ for all positive integers $n$.
Problem
Source: Dutch IMO TST 2016 p2
Tags: number theory, divisible, divisor, exponential
BlazingMuddy
30.08.2019 22:25
Any such pair $(a, b)$ with either $a + b$ odd or $a \equiv b \equiv 1\pmod{3}$.
The property implies that $d$ divides $a + b + 1$, $a^2 + b^2 + 1$, and $a^3 + b^3 + 1$. Since $d | a + b + 1$, we obtain:
\begin{align*}
d &| (a + b)^2 - 1 \\
d &| a^2 + b^2 + 2ab - 1 \\
d &| 2ab - 2 \\
d &| a^3 + b^3 + 1 - 3ab \\
d &| 3ab \\
d &| 2(3ab) - 3(2ab - 2) \\
d &| 6
\end{align*}
For the case $d = 2$ and $d = 6$, we have $2 | a + b + 1$, so $a + b$ must be odd. Otherwise, if $d = 3$, then $3 | 2ab - 2$ and $3 | a + b + 1$, so $a + b \equiv 2 \pmod{3}$ and $ab \equiv 1\pmod{3}$, which implies $a\equiv b\equiv 1\pmod{3}$.
Conversely, we can just take $d = 2$ whenever $a + b$ is odd and $d = 3$ whenever $a \equiv b\equiv 1\pmod{3}$.
P2nisic
27.04.2021 17:29
Take $n=$Φ$(d)$ then: $a^n+b^n+1=3or2or1(modd)$ so $d=2or3$. If $d=2$ we have $a+b=odd$. If $d=3$ we have $a=b=1(mod3)$ Edit:My solution is wrong because we don't know that$(d,a)=(d,b)=1$. Let $p$ be a prime division of $d$ then: $a^n+b^n+1=3or2or1(modp)$. So $d=2^x3^y$. For $x>=2$ contradiction $mod4$ for an even $n$. For $y>=2$ contradiction $mod9$ for $6|n$. So $d=1,2,3,6$. For $d=1$ done. For $d=2$ take $a=even$ and $b=odd$. For $d=3$ take $a=b=1(mod6)$. For $d=6$ take $a=1(mod6)$ and $b=4(mod6)$.