, 2015

*Answer: $(a, b) \in \{(43n, 43m-1),\ (43n-42, 43m),\ (43n-6, 43m-7),\ (43n+7-43, 43m+6-43) \mid n, m \in \mathbb{Z}_{\ge 1}\}.$*

If $p = 43$ then it follows from Fermat's little theorem that $a \equiv b+1 \pmod{43}$. Hence if $a$ is divisible by $43$ then $b \equiv -1 \pmod{43}$ and if $b$ is divisible by $43$ then $a \equiv 1 \pmod{43}$. For such a pair $(a, b)$, it is clear that $a^p - b^p - 1$ is divisible by $43$ for every prime $p$. Thus, we can assume that $ab$ is not divisible by $43$.

Since $a^{41} - b^{41} - 1$ is divisible by $43$ we obtain
$$b \equiv b a^{42} \equiv a b^{42} + a b \equiv a + a b \pmod{43}.$$
Thus $b^2 + b + 1 \equiv 0 \pmod{43}$, implying that $b \equiv 6 \pmod{43}$ and $a \equiv 7 \pmod{43}$ respectively. To see that $a^{41} - b^{41} - 1$ is divisible by $43$ for any $p \ge 5$, it is enough to see that $(b+1)^p - b^p - 1 \equiv 0 \pmod{b^2 + b + 1}$ which follows from $(-b^2)^p - b^p - 1 \equiv 0 \pmod{b^2 + b + 1}$.