Iranian Mathematical Olympiad

Define $$A_n:=\overline{a_n\dots a_1{a}_0},B_n:=\overline{b_n\dots b_1{b}_0},K_n:=\frac{B_n^2+999}{A_n^2+999}.$$ Claim 1. $\{K_n\}$ is eventually constant or $10^n\mid A_{n-1}^2+999$ for each positive integer $n$.

---

Proof. For each $n\ge 1$ $$B_n^2+999=K_n(A_n^2+999),B_{n-1}^2+999=K_{n-1}(A_{n-1}^2+999)(1)$$ From the Definition of $A_n,B_n$ we know that $$A_n\equiv A_{n-1}(\mathrm{mod}10^n),B_n\equiv B_{n-1}(\mathrm{mod}10^n)(2)$$ Then (1),(2) imply that $$K_n(A_n^2+999)\equiv K_{n-1}(A_{n-1}^2+999)(\mathrm{mod}10^n).(3)$$ If there exist $N\ge 1$ such that $10^N\nmid A_{N-1}^2+999$, then there is a prime number $p\in \{2,5\}$ such that $p^N\nmid A_{N-1}^2+999$. (2) infers that $A_n\equiv A_{N-1}(\mathrm{mod}{p}^N)$ for each $n\ge N-1$. So $p^N\nmid A_n^2+999$, meaning $$v_p(A_n^2+999)\le N,$$ where $v_p(x)$ is the power of $p$ in prime factorization of $x$. Define $d_n:=\gcd (10^n,A_{n-1}^2+999)$. If $n\ge N+1$ then $d_n\nmid \frac{10^n}{p^{n-N}}$ because $v_p(A_n^2+999)\le N$. According to (3) there is $K_n\equiv K_{n-1}(\mathrm{mod}\frac{10^n}{d_n})$ so $$K_n\equiv K_{n-1}(\mathrm{mod}{p}^{n-N}),(4)$$ if $n\ge M$ is large enough such that $p^{n-N}>100$ then for each $i\ge n-1$ $$\begin{gathered} A_i\ge 10^i⟹A_i^2+999\ge 10^{2i}+999 \\ {B}_i<10^{i+1}⟹B_i^2+999<10^{2i+2}+999. \end{gathered}$$ Then $$K_i=\frac{B_i^2+999}{A_i^2+999}<100<p^{n-N}$$ Hence (4) implies that $K_{n-1}=K_n$ for large enough values of $n$ so the claim is done. $\square$

As discussed above there are two cases: 1. $10^n\mid A_{n-1}^2+999$ for each $n\ge 1$. 2. $\{K_n\}$ is eventually constant.

Claim 2. By assumption of the first case, $a_n=b_n$ for all non-negative integers $n$.

---

Proof. Let $n\ge 1$ be any positive integer. $$A_n^2+999\mid B_n^2+999⟹10^n\mid B_{n-1}^2+999$$ With above assertions and some calculation it's deduced that $a_0=b_0,a_1=b_1$. Note that $A_n=10^n{a}_n+A_{n-1}$ so $$A_n^2+999\equiv 2\times 10^n{a}_n{A}_{n-1}+A_{n-1}^2+999(\mathrm{mod}10^{n+1}).$$ Clearly, $2\times 10^n\mid 10^{n+1}\mid A_n^2+999$ thus $$2\times 10^n\mid A_{n-1}^2+999\mid B_{n-1}^2+999(5)$$ Which is stronger than assumed relation at beginning of the claim. The remaining part of proof is by using induction. Assume that $a_m=b_m$ for all $0\le m\le n-1$. Which means $A_{n-1}=B_{n-1}$. Using (5) implies for all $n\ge 1$ $$\begin{array}{rl}{A}_n^2+999& \equiv 0(\mathrm{mod}2\times 10^{n+1})\\ ⟹(10^n{a}_n+A_{n-1}{)}^2+999& \equiv 0(\mathrm{mod}2\times 10^{n+1}).\end{array}$$ Which implies $$a_n{A}_{n-1}+\frac{A_{n-1}^2+999}{2\times 10^n}\equiv 0(\mathrm{mod}10).(6)$$ Repeating above discussion with $B_n^2+999$ infers that $$b_n{B}_{n-1}+\frac{B_{n-1}^2+999}{2\times 10^n}\equiv 0(\mathrm{mod}10).(7)$$ According to (6), (7) and the assertion of $A_{n-1}=B_{n-1}$ (induction) it's known that $a_n{A}_{n-1}\equiv b_n{A}_{n-1}(\mathrm{mod}10)$. Moreover $\gcd (A_n,10)=1$ since $10^{n+1}\mid A_n^2+999$. This implies $a_n\equiv b_n(\mathrm{mod}10)$. Hence $a_n=b_n$ since $0\le a_n,b_n\le 9$. Claim is proved. $\square$

The only remaining part of solution is the case that $\{K_n\}$ is eventually constant. Suppose that there exist positive integers $K,T$ such that $K_n=K$ for all $n\ge T$. Suppose that $n\ge T$ then $$\begin{gathered} \begin{array}{l}{B}_n^2+999=K(A_n^2+999)\\ A_n=10^n{a}_n+A_{n-1}\\ B_n=10^n{b}_n+B_{n-1}\end{array}\} \\ ⟹10^n{b}_n^2+2\times b_n{B}_{n-1}=K(10^n{a}_n^2+2\times a_n{A}_{n-1}) \\ ⟹10^n(b_n^2-K{a}_n^2)=2(K{a}_n{A}_{n-1}-b_n{B}_{n-1}). \end{gathered}$$ So $$\frac{10^n}{A_{n-1}}(b_n^2-K{a}_n^2)=2\left(K{a}_n-b_n\frac{B_{n-1}}{A_{n-1}}\right).(8)$$ It's known that $A_n,B_n\ge 10^n$ for large enough integers $n$ $$⟹A_n^2\simeq A_n^2+999,B_n^2\simeq B_n^2+999.$$ Which implies $$B_n^2\simeq K{A}_n^2⟹\underset{n\to \infty }{\lim }\frac{B_n}{A_n}=\sqrt{K}.$$ Define $$C_n:=\frac{B_n}{A_n}-\sqrt{K}⟹\underset{n\to \infty }{\lim }{C}_n=0,$$ according to (8) $$\begin{array}{rl}\frac{10^n}{A_{n-1}}(b_n^2-K{a}_n^2)& =2(K{a}_n-b_n\sqrt{K})-2b_n{C}_n\\ ⟹\frac{10^n}{A_{n-1}}(b_n-\sqrt{K}{a}_n)(b_n+\sqrt{K}{a}_n)& =2\sqrt{K}(\sqrt{K}{a}_n-b_n)-2b_n{C}_n\\ ⟹(b_n-\sqrt{K}{a}_n)\left(\frac{10^n}{A_{n-1}}(b_n+\sqrt{K}{a}_n)+2\sqrt{K}\right)& =-2b_n{C}_n\end{array}(9)$$ Right Hand Side of (9) converges to 0 since ${\lim }_{n\to \infty }{C}_n=0$ and $0\le b_n\le 9$. Also the second parenthesis in (9) is always greater than $2\sqrt{K}$. So $$\underset{n\to \infty }{\lim }{b}_n-\sqrt{K}{a}_n=0$$ But $b_n-\sqrt{K}{a}_n$ has finite values which infers that there exist positive integer $L\ge M$ such that $b_n=\sqrt{K}{a}_n$ for all $n\ge L$. Therefore according to (9) there must be $-2b_n{C}_n=0$ for all $n\ge L$. Which implies $C_n=0$ since $b_n\ne 0$ for $n\ge M$. Therefore $$C_n=0⟹B_n=\sqrt{K}{A}_n$$ In addition with $B_n^2+999=K(A_n^2+999)$ it's easy to see that $999K=999$ which means $K=1$. So for large enough positive numbers $n$, $$B_n=A_n⟹\overline{b_n\cdots b_1{b}_0}=\overline{a_n\cdots a_1{a}_0}$$ Therefore $a_k=b_k$ for all $k\ge 0$ and we're done! ■