United States — Team Selection Test

Solution 1. For all pairs of positive integers $a$ and $b$, we claim that there exist infinitely many $n$ such that $a$ divides $b^n - n$.
We establish our claim by strong induction on $a$. The base case of $a = 1$ holds trivially. Now, suppose that the claim holds for all $a < a_0$. Since $\varphi(a) < a$, by the induction hypothesis and by Lemma 1, there are infinitely many $n$ such that
$$\varphi(a) \mid (b^n - n) \quad \text{and} \quad b^{n+\varphi(a)} \equiv b^n \pmod{a}.$$
For each such $n$, set
$$t = \frac{b^n - n}{\varphi(a)} \quad \text{and} \quad n_1 = b^n = n + t\varphi(a).$$

It follows that
$$b^{n_1} - n_1 \equiv b^{n+t\varphi(a)} - (n+t\varphi(a)) \equiv b^n - n - t\varphi(a) \equiv 0 \pmod{a}.$$
Then, we see that $n_1$ satisfies the desired property. By the induction hypothesis, there are infinitely many $n_1 = b^n$ satisfying the conditions of the claim for $a$, completing the induction.

Solution 2. We prove that no such $a, b$ exist by proving the following: for any $a, b$, there is an arithmetic progression $n \equiv h \pmod m$, with $m$ divisible only by primes less than or equal to the greatest prime factor of $a$, such that $b^n \equiv n \pmod a$ for all sufficiently large $n$ satisfying $n \equiv h \pmod m$.
Let us induct on highest prime divisor of $a$. The result is trivial for $a = 1$. Let $p$ be a prime, and suppose that the result is true whenever all the prime divisors of $a$ are less than $p$. Now, suppose that $p$ is the greatest prime divisor of some $a$, and write $a = p^e a_1$, where $a_1$ has all prime factors less than $p$. By the induction hypothesis, there is an arithmetic progression $n \equiv h_1 \pmod{m_1}$, with $m_1$ divisible only by primes strictly less than $p$, such that for $n \equiv h_1 \pmod{m_1}$ sufficiently large, $b^n \equiv n \pmod{a_1}$. There is no harm in assuming that $p-1$ divides $m_1$. In this case, in this arithmetic progression, $b^n$ is eventually constant modulo $p$ due to the lemma. We can thus choose a congruence modulo $p$ so that for $n$ an appropriate residue class modulo $m_1p$, $b^n \equiv n \pmod{p}$. In this progression, $b^n$ is constant modulo $p^2$, so we can refine our choice of $n$ modulo $m_1p$ to a choice of $n$ modulo $m_1p^2$ to force $b^n \equiv n \pmod{p^2}$. We can then repeat the above process until we obtain $b^n \equiv n \pmod{p^e}$. Since we originally had $b^n \equiv n \pmod{a_1}$, combining the two congruences using the Chinese Remainder Theorem gives us $b^n \equiv n \pmod a$ for all sufficiently large $n$ in the congruence class generated at the last step. This completes the induction.