For each non-negative integer $n$, let $u_n = \left( 2+\sqrt{5} \right)^n + \left( 2-\sqrt{5} \right)^n$. a) Prove that $u_n$ is a positive integer for all $n \geq 0$. When $n$ changes, what is the largest possible remainder when $u_n$ is divided by $24$? b) Find all pairs of positive integers $(a, b)$ such that $a, b < 500$ and for all odd positive integers $n$, $u_n \equiv a^n - b^n \pmod {1111}$.
Problem
Source: 2025 Vietnam National Olympiad - Problem 2
Tags: modular arithmetic, number theory
25.12.2024 13:08
Solution: a) Notice that $u_{n+2} = 4u_{n+1} + u_n$, for all non-negative integer $n$. Since $u_0 = 2, u_1 = 4$, using induction, we get that $u_n$ is a positive integer for all $n \geq 0$. Then, by direct computation, we obtain that $u_8 \equiv u_0 \pmod {1111}$ and $u_9 \equiv u_1 \pmod {1111}$. Therefore, the sequence $(r_n)$, where $r_n$ is the remainder obtained when we divide $u_n$ by $24$, is a periodic sequence of period $8$. To find the largest possible remainder, it suffices to check the first $8$ terms of $(r_n)$, giving us the largest possible remainder of $20$. b) Let $(a, b)$ be a satisfying pair of positive integers. Then, $$a - b \equiv 4 \pmod {1111}, a^3 - b^3 \equiv 76 \pmod{1111}$$Since $a, b < 500$, we must have $a = b+4$. Then, $$1111 | (b+4)^3 - b^3 - 76 = 12(b^2 + 4b - 1)$$giving us $1111 | b^2 + 4b - 1$ since $(12, 1111) = 1$. Therefore $b^2 + 4b + 4 \equiv 5 \pmod {1111}$, so $$(b+2)^2 \equiv 5 \equiv 16 \pmod {11}, (b+2)^2 \equiv 5 \equiv 2025 \pmod{101}$$We obtain that $b \equiv 2 \pmod {11}$ or $b \equiv 5 \pmod {11}$, and $b \equiv 43 \pmod {101}$ or $b \equiv 54 \pmod {101}$. By Chinese Remainder Theorem, each possible pair of congruences give us one unique solution modulo $1111$, so there are only $4$ possible remainders when $b$ is divided by $1111$, which are $346, 357, 750, 761$. Since $b < 500$ and $a = b + 4$, we obtain $$(a, b) \in \{(361, 357), (350, 346)\}.$$Finally, we claim that these two pairs satisfy the conditions. By direct computation, we get that $a^n - b^n \equiv u_n \pmod {1111}$ for $n = 1, 3$. Now notice that for all non-negative integers $n$, we have $u_{n+4} = 18u_{n+2} - u_n$. Additionally, in both cases, we always have $$a^4 - 18a^2 + 1 \equiv b^4 - 18b^2 + 1 \equiv 0 \pmod {1111},$$so by induction, we get that $a^n - b^n \equiv u_n \pmod {1111}$ for all non-negative odd integers $n$. In conclusion, there are two satisfying pairs of $(a, b)$, which are $(361, 357)$ and $(350, 346)$.
27.12.2024 17:36
Part a is okay, part b can be either done by bashing (not recommended) or finding a key observation.