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
hung9A
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)$.
wassupevery1
27.12.2024 17:36
Part a is okay, part b can be either done by bashing (not recommended) or finding a key observation.
It is easy to prove that $u_0=2, u_1 = 4, u_{n+2} = 4u_{n+1} + u_n$ for all $n \geq 0$ hence $u_n$ is a positive integer for all $n \geq 0$.
Manually checking the sequence mod $3$ and $8$, we get the following:
- Mod $3$: $2, 1, 0, 1, 1, 2, 0, 2$, then this repeats.
- Mod $8$: $2, 4$ and this repeats.
This implies the sequence is periodic modulo $24$ with period $8$, and hence manually checking the first $8$ terms gives the answer to be $\boxed{20}$ at, for example, $u_5 = 1364$.
Plugging in $n=1, 3$ gives $a-b \equiv 4 \pmod {1111}, a^3 - b^3 \equiv 76 \mod {1111}$. We first claim all such $(a, b)$ work, before proceeding to find all $a, b$ satisfying $0 < a, b < 500$.
Plugging $a \equiv b+4 \pmod {1111}$ in, we get that $b^2 -1 \equiv -4b \pmod {1111}$ (noting that $12, 1111$ are relatively prime), while $a^2 -1 \equiv 4a \pmod {1111}$.
Squaring, we get that $a, b$ are solutions to $x^4 - 18x^2 + 1 \equiv 0 \pmod {1111}$, and with a note that $u_{n+4} - 18u_{n+2} + u_n = 0$ (this is by directly calculating $u_{2k+1}, u_{2k}$), a simple induction shows that $u_n \equiv a^n - b^n \pmod {1111}$ for all odd $n$.
Now, let's find all $a, b$ satisfying $0 < a, b < 500$. Note that $-498 \leq a-b \leq 498$, the first modulo equation implies $a=b+4$. Plugging in $a^3 - b^3 \equiv 76 \pmod {1111}$, we get $b^2 + 4b -1 \equiv 0 \pmod {1111}$.
- Considering modulo $11$, we get $(b+2)^2 \equiv 5 \equiv 16 \pmod {11}$, hence $b \equiv 2 \pmod {11}$ or $b \equiv 5 \pmod {11}$.
- Considering modulo $101$, we get $(b+2)^2 \equiv 5 \equiv 2025 \pmod {101}$, hence $b \equiv 43 \pmod {101}$ or $b \equiv 54 \pmod {101}$.
Chinese Remainder Theorem shows that there is only one solution for $b$ modulo $1111$, given $b$ modulo $11$ and $b$ modulo $101$. We then get
- $b \equiv 2 \pmod {11}, b \equiv 43 \pmod {101} \Rightarrow b \equiv 750 \pmod {1111}$,
- $b \equiv 2 \pmod {11}, b \equiv 54 \pmod {101} \Rightarrow b \equiv 761 \pmod {1111}$,
- $b \equiv 5 \pmod {11}, b \equiv 43 \pmod {101} \Rightarrow b \equiv 346 \pmod {1111}$,
- $b \equiv 5 \pmod {11}, b \equiv 54 \pmod {101} \Rightarrow b \equiv 357 \pmod {1111}$.
Since $b < 500$, we only take $b=346, 357$ and it follows that $(a, b) = (350, 346), (361, 357)$.