$\{a_{n}\}_{n\geq 0}$ and $\{b_{n}\}_{n\geq 0}$ are two sequences of positive integers that $a_{i},b_{i}\in \{0,1,2,\cdots,9\}$. There is an integer number $M$ such that $a_{n},b_{n}\neq 0$ for all $n\geq M$ and for each $n\geq 0$ $$(\overline{a_{n}\cdots a_{1}a_{0}})^{2}+999 \mid(\overline{b_{n}\cdots b_{1}b_{0}})^{2}+999 $$prove that $a_{n}=b_{n}$ for $n\geq 0$. (Note that $(\overline{x_nx_{n-1}\dots x_0}) = 10^n\times x_n + \dots + 10\times x_1 + x_0$.) Proposed by Yahya Motevassel
Problem
Source: Iranian TST 2019, first exam day 2, problem 6
Tags: number theory
pslove
30.06.2019 15:05
We notice the following:
If there exists some $N$ such that $2\cdot 10^{N+1}\!\!\!\not|(\overline{a_{N}\cdots a_{1}a_{0}})^{2}+999$, then $\forall n\geq N$ $v_{10}((\overline{a_{n}\cdots a_{1}a_{0}})^{2}+999)\leq N+1$. The same holds for $(\overline{b_{n}\cdots b_{1}b_{0}})^{2}+999$.
Now we have the following two cases...
Case 1. There exists some $N$ such that $2\cdot 10^{N+1}\!\!\!\not|(\overline{a_{N}\cdots a_{1}a_{0}})^{2}+999$
Let $f(n)=\frac{(\overline{b_{n}\cdots b_{1}b_{0}})^{2}+999}{(\overline{a_{n}\cdots a_{1}a_{0}})^{2}+999}$.
If $v_{10}((\overline{b_{n}\cdots b_{1}b_{0}})^{2}+999)$ can be arbitrarily big, then $v_{10}(f(n))$ can be arbitrarily big.
But for $n\geq M$, $f(n)<100$, so contradiction. Therefore there exists some $K$ such that $2\cdot 10^{K+1}\!\!\!\not|(\overline{b_{K}\cdots b_{1}b_{0}})^{2}+999$.
Let $\max\lbrace{N,K\rbrace}=T$.
We notice that for $n\geq T+1$, $v_{10}((\overline{a_{n+1}\cdots a_{1}a_{0}})^{2}+999)=v_{10}((\overline{a_{n}\cdots a_{1}a_{0}})^{2}+999)$, and the same for $(\overline{b_{n}\cdots b_{1}b_{0}})^{2}+999$.
Let $\lim_{n\rightarrow \infty}v_{10}((\overline{a_{n}\cdots a_{1}a_{0}})^{2}+999)=X$, $\lim_{n\rightarrow \infty}v_{10}((\overline{b_{n}\cdots b_{1}b_{0}})^{2}+999)=Y$. Of course $X\leq Y$ must hold.
For $n>\max\lbrace{T,X+2,Y+2,M\rbrace}$ $$f(n+1)=\frac{(\overline{b_{n+1}\cdots b_{1}b_{0}})^{2}+999}{(\overline{a_{n+1}\cdots a_{1}a_{0}})^{2}+999}=10^{Y-X}\cdot \frac{10^{2n+2-Y}b_{n+1}^{2}+2\cdot 10^{n+1-Y}b_{n+1}\cdot \overline{b_{n}\cdots b_{1}b_{0}}+\frac{(\overline{b_{n}\cdots b_{1}b_{0}})^{2}+999}{10^{Y}}}{10^{2n+2-X}b_{n+1}^{2}+2\cdot 10^{n+1-X}b_{n+1}\cdot \overline{a_{n}\cdots a_{1}a_{0}}+\frac{(\overline{a_{n}\cdots a_{1}a_{0}})^{2}+999}{10^{X}}}$$Comparing with $f(n)=10^{Y-X}\cdot\frac{\frac{(\overline{b_{n}\cdots b_{1}b_{0}})^{2}+999}{10^{Y}}}{\frac{(\overline{a_{n}\cdots a_{1}a_{0}})^{2}+999}{10^{X}}}$, we see that $\frac{f(n+1)}{10^{Y-X}}\equiv \frac{f(n)}{10^{Y-X}} \pmod {1000}$.
But for $n\geq M$, $f(n)< 100$, so we get $f(n+1)=f(n)$. This means $f(n)$ becomes constant eventually. Let this constant $c$.
Some tedious calculationsUsing some properties related to proportionality, we see that $c=\frac{\overline{b_{n+1}\cdots b_{1}b_{0}}+\overline{b_{n}\cdots b_{1}b_{0}}}{\overline{a_{n+1}\cdots a_{1}a_{0}}+\overline{a_{n}\cdots a_{1}a_{0}}}$ for big $n$.
Using the same property again, we see that $c=\frac{10b_{n+1}+b_{n}}{10a_{n+1}+a_{n}}$ for big $n$.
If $ca_{n}\neq b_{n}$, $b_{n+1}>ca_{n+1}$, so $b_{n+1}\not\equiv ca_{n+1} \pmod{10}$, which contradicts $c=\frac{10b_{n+2}+b_{n+1}}{10a_{n+2}+a_{n+1}}$.
Therefore $c=\frac{b_{n}}{a_{n}}$ for all big $n$, so $c=\lim_{n\rightarrow \infty}f(n)=c^{2}$. This means $c=1$.
Therefore $c=1$, and $a_{n}=b_{n}$ must hold for all $n\geq 0$.
Case 2. For all $N\geq 0$, $2\cdot 10^{N+1}|(\overline{a_{N}\cdots a_{1}a_{0}})^{2}+999$
We can easily see that for $N\geq 0$, $2\cdot 10^{N+1}|(\overline{b_{N}\cdots b_{1}b_{0}})^{2}+999$ must also hold.
Since $a_{0}^{2}+999|b_{0}^{2}+999$ and $(\overline{a_{1}a_{0}})^{2}+999|(\overline{b_{1}b_{0}})^{2}+999$, we get $a_{0}=b_{0}$, $a_{1}=b_{1}$.
Now we prove the following claim.
Claim.
After $a_{0},a_{1},\cdots,a_{n}$ satisfying the assumption of Case 2 for $N=0,1,\cdots,n$ has been decided,
there exists a unique $a_{n+1}$ satisfying the assumption of Case 2 for $N=n+1$.
Proof of ClaimLet $(\overline{a_{n}\cdots a_{1}a_{0}})^{2}+999=2\cdot 10^{n+1}\cdot l$.
Then $(\overline{a_{n+1}\cdots a_{1}a_{0}})^{2}+999=10^{2n+2}a_{n+1}^{2}+2\cdot 10^{n+1}a_{n+1}\cdot\overline{a_{n}\cdots a_{1}a_{0}}+2\cdot 10^{n+1}\cdot l$.
Since $2\cdot 10^{n+2}|10^{2n+2}$, $2\cdot 10^{n+2}|(\overline{a_{n+1}\cdots a_{1}a_{0}})^{2}+999 \Leftrightarrow 10|a_{n+1}\cdot\overline{a_{n}\cdots a_{1}a_{0}}+l$
Since $\overline{a_{n}\cdots a_{1}a_{0}}$ is coprime with $10$, there exists a unique $a_{n+1}$ among $\{0,1,2,\cdots ,9\}$ such that $10|a_{n+1}\cdot\overline{a_{n}\cdots a_{1}a_{0}}+l$.
By the claim, we see that the value of $a_{0}$ totally determines the sequence $\{a_{n}\}_{n\geq 0}$ for Case 2.
The same holds for $\{a_{n}\}_{n\geq 0}$, so since $a_{0}=b_{0}$, we get that $a_{n}=b_{n}$ for all $n\geq 0$.
Therefore in both cases, $a_{n}=b_{n}$ for $n\geq 0$. $\blacksquare$
soryn
30.06.2019 15:33
Intetesting...Thanks
Pathological
04.07.2019 19:34
Here's a different solution using Pell Equations.
WLOG let's assume that $M > 10^{10^{10^{10}}}$. For each $n$, let $c_n = \frac{(\overline{b_{n}\cdots b_{1}b_{0}})^{2}+999}{(\overline{a_n \cdots a_1a_0})^2+999}.$ From the condition of the problem that $a_n, b_n \neq 0$ for $n \ge M$, we know for $n \ge M$ that $c_n \in \{1, 2, \cdots, 100\}.$ If there were infinitely many $n \in \mathbb{N}$ with $c_n = 1$, then we'd have $\overline{b_{n}\cdots b_{1}b_{0}} = \overline{a_n \cdots a_1a_0}$ for infinitely many $n \in \mathbb{N}$, and hence we'd be done.
Otherwise, assume for contradiction that only finitely many $n \in \mathbb{N}$ satisfied $c_n = 1$, suppose that $M$ is such that all $n$ with $c_n = 1$ are less than $M$. Note that since $M$ is big ($>10^{10^{10^{10}}}$), we know that $c_n$ is not a perfect square for $n \ge M.$ Call $n \ge M$ $k$-type if $c_n = k$. From our previous work, we know that all $n \ge M$ are of at most $90$ different types. Hence, among any $91$ consecutive integers $m, m+1, m+2, \cdots, m+90$ with $m \ge 10^{2M}$, we know that two are of the same type, say $m+a$ and $m+b$ are both $k-$type for $k \in \{1, 2, \cdots, 100\}$ not a perfect square, where $a < b$. For convenience, we will let $B_1 = \overline{b_{m+a}\cdots b_{1}b_{0}}, B_2 = \overline{b_{m_b}\cdots b_{1}b_{0}}, A_1 = \overline{a_{m+a} \cdots a_1a_0}, A_2 = \overline{a_{m+b} \cdots a_1a_0}$.
Now, let $\{(x_1, y_1), (x_2, y_2), \cdots, (x_t, y_t)\}$ be the pairs of positive integers which satisfy $x_i < 10^{10^{10}}$ and $\frac{x_i^2-1}{y_i^2} = k.$
It's then well-known that there exists $1 \le v \le t$ with:
$$A_2 = A_1x_v + B_1ky_v, B_2 = A_1y_v + B_1x_v.$$Hence, we have that:
$$A_1(x_v - 1) + B_1ky_v \equiv A_1y_v + B_1(x_v-1) \equiv 0$$modulo $10^{m+a+1}.$
Therefore, we have that:
$$10^{m+a+1} \mid y_v(A_1(x_v - 1) + B_1ky_v) - (x_v-1)(A_1y_v + B_1(x_v-1)) = B_1(ky_v^2 - x_v^2 + 2x_v - 1) = 2x_vB_1.$$Since $v_{5} (x_v) < 2 \cdot 10^{10^{10}} < M-1, v_2 (x_v) < 5 \cdot 10^{10^{10}} < M-1$, we must have that $10^{M+1} | B_1.$ However, this implies that $b_M = 0$, contradicting the conditions of the problem.
$\square$
Aryan-23
23.11.2020 00:24
Define $A_n =\left( \overline{a_na_{n-1}\dots a_1a_0 }\right) $ and $B_n =\left( \overline{b_nb_{n-1}\dots b_1b_0 }\right) $. Set $K_n= \frac {B_n^2+999}{A_n^2+999}$.
First note that we have :
$$A_n\equiv A_{n-1} \pmod {10^n} \quad B_n\equiv B_{n-1} \pmod {10^n} $$$$B_n^2+999=K_n(A_n^2+999) \quad B_{n-1}^2+999=K_{n-1}(A_{n-1}^2+999)$$
This gives $K_n (A_n^2+999) \equiv K_{n-1}^2(A_n^2+999) \pmod {10^n}$
Claim : We have that one of the following cases holds :
$10^n \mid A_{n-1}^2+999$ for all $n\ge 1$.
$K_n$ is eventually constant
Proof : Assume that there is a $N$ such that there is some prime $p\in \{2,5\}$ such that $p^N \nmid A_{N-1}^2+999$. Note that because of the congruence $A_n\equiv A_{N-1} \pmod {p^N}$ we have that for all $n\ge N-1$, $\nu_p(A_n^2+999)<N$. Conisder $d_n = \operatorname {gcd}(10^n,A_{n-1}^2+999)$. We have $d_n \mid \frac {10^n}{p^n}\cdot p^N$, so we have the congruence:
$$K_n =K_{n-1} \pmod {\tfrac {10^n}{d_n}} \implies
K_n =K_{n-1} \pmod {p^{n-N}}$$
Note that we have a dumb size bound on $K_n$ :
$$K_n =\frac { B_n^2+999}{A_n^2+999} < \frac {10^{2n+2}+999}{10^{2n}+999} <100$$
So take $p^{n-N} >100$ and the claim is proven. $\square$
Case 1 : Assume $10^{n+1} \mid A_n^2+999 \mid B_n^2+999$ for all $n \ge 0$
We actually prove that this divisibility can be improved. We claim $2\cdot 10^n \mid A_{n-1}^2+999$ for all $n\ge 1$.
We have :
$$A_n^2+999 = (10^na_n+A_{n-1})^2+999 \equiv A_n^2+999 = 2\cdot 10^na_n + A_{n-1}^2+999 \pmod {2\cdot 10^{n}}$$
So we have $2\cdot 10^n \mid 10^{n+1} \mid A_n^2+999$, so $2\cdot 10^n \mid A_{n-1}^2+999$.
We prove $a_n=b_n$ for all $n \ge 0$ with induction on $n$. Check $n=0,1$ by direct calculation. Now assume $a_k=b_k$ for all $k<n$. We only care about $A_{n-1}=B_{n-1}$.
We have :
$$ A_n^2+999 = 2\cdot 10^na_nA_{n-1}+A_{n-1}^2+999 \equiv 0 \pmod {2\cdot 10^{n+1}} \iff a_nA_{n-1} + \frac {A_{n-1}^2+999}{2\cdot 10^n} \equiv 0 \pmod {10}$$
Similarly we have:
$$b_nB_{n-1} + \frac {B_{n-1}^2+999}{2\cdot 10^n} \equiv 0 \pmod {10}$$
This gives $a_n \equiv b_n \pmod {10}$. Since $a_n,b_n<10$, we get $a_n=b_n$ and we are done by induction. $\blacksquare$
Remark on strengthening divisibility conditionThe obvious way to try induction doesnt work because we are missing out on a extra 2 ! With the weak condition, we can only conclude $a_n \equiv b_n \pmod 5$, which isnt sufficient. So this gives the idea of strengthening the divisibility which fortunately isnt too hard to prove.
Case 2 : $K_n$ is eventually constant.
NT flavoured arguements dont really work here, so we try glorified size, i.e analysis type arguements
So we have that for all $n>N$ $B_n^2+999=K(A_n^2+999)$.
First note that for all large $n$, we have that $\frac {B_n^2}{A_n^2} \approx \frac {B_n^2+999}{A_n^2+999} =K$. In other words $\lim_{n\rightarrow \infty} \frac {B_n}{A_n} = \sqrt K$. Define $C_n = \frac {B_n}{A_n}-\sqrt K$, so that
$\lim_{n\rightarrow \infty} C_n=0$.
Next using the equalities :
$$B_n^2+999 = K(A_n^2+999) \quad B_{n-1}^2+999 = K(A_{n-1}^2+999)$$$$B_n=10^nb_n+B_{n-1} \quad A_n=10^na_n+A_{n-1}$$
We have the following equality (after some manipulation) :
$$ \frac {10^n}{A_{n-1}}(b_n^2-Ka_n^2) =2(Ka_n- b_n \frac {B_{n-1}}{A_{n-1}})$$$$\iff \frac {10^n}{A_{n-1}}(b_n^2-Ka_n^2) =2(Ka_n- b_n (C_{n-1}+ \sqrt K))$$$$\iff \frac {10^n}{A_{n-1}}(b_n^2-Ka_n^2) = -2\sqrt K(b_n-\sqrt K a_n)-2b_nC_{n-1}$$$$\iff (b_n-\sqrt Ka_n) \left( \frac {10^n}{A_{n-1}}(b_n+ \sqrt Ka_n)+2\sqrt K \right) = -2b_nC_{n-1}$$
Call the above equation as $\spadesuit$.
Take $n\rightarrow \infty$ in $\spadesuit$. Since $b_n$ takes finitely many values, RHS goes to $0$. Since the second factor of LHS is always positive, (in particular it's always $\geq 2\sqrt K$), we have $\lim_{n\rightarrow \infty} b_n-\sqrt Ka_n =0$.
Note that $b_n-\sqrt Ka_n$ takes only finitely many values, so there exists a $L$ such that for all $n>L$, we have $b_n=\sqrt K a_n$. Plugging in $n>L$ in the equation $\spadesuit$. This gives $C_{n-1}=0$, so we have $\frac {B_n}{A_n} = \sqrt K$ for all large $n$. Plugging into the equation $B_n^2+999=K(A_n^2+999)$, we get $K=1$. In other words, $A_n=B_n$ holds for all large $n$. By definition of $A_n,B_n$, we conclude that $a_n=b_n$ for all $n\ge 0$ and we are done. $\blacksquare$
thevictor
10.05.2022 15:58
Define $A_n =\left( \overline{a_na_{n-1}\dots a_1a_0 }\right) $ and $B_n =\left( \overline{b_nb_{n-1}\dots b_1b_0 }\right) $.
Let $u_n=A_n/10^n,v_n=B_n/10^n$.
Let $k_n=\sqrt{\frac{B_n^2+999}{A_n^2+999}}$.$K_n$ has only finitely many possible values.
Assume for contradiction that $K_n \neq 1$ for some $n$,then it holds for any positive integer $n$.It is also easy to draw a contradiction if $K_n \in Z$.
We prove that there exists a finite set $S$,such that for all $\epsilon>0$,there exists an integer $N$ such that for all $n>N$,there exists $t \in S,|u_n-t|<\epsilon$ (and a similar argument for $v_n$)
In fact,we have
$$\frac{b_{n+1}+v_n}{a_{n+1}+u_n}\to K_{n+1},\frac{v_n}{u_n}\to K_n$$Clearly $\frac{b_{n+1}}{a_{n+1}}\neq K_n$(which is not a rational number),the system of equations has a unique solution.
The above claim indicates that there exists an $L$ such that we can uniquely determine $a_{n-L}$ from $a_n,a_{n-1},\cdots,a_{n-L+1}$.This easily yields that $a_n$ is eventually periodic,and so is $b_n$.However,this indicates that $\frac{B_n}{A_n}$ converges to a rational number,a contradiction.