If $a_n=100a_{n-1}+134$, find least value of n for which $a_n$ is divisible by $99$

Question

Let $a_{1}=24$ and form the sequence $a_{n}, n \geq 2$ by $a_{n}=100 a_{n-1}+134 .$ The first few terms are $$ 24,2534,253534,25353534, \ldots $$ What is the least value of $n$ for which $a_{n}$ is divisible by $99 ?$

We have to find. $a_n \equiv 0\pmod{99}$ $$ a_n=100a_{n-1}+134 \\ \implies a_n-a_{n-1}\equiv 35 \pmod{99}$$

Now how do I proceed from here? I Concluded some results, verified for smaller values, which proved to be wrong. How does doing this get me the $n$? Or am I even correct to proceed like this?

The (unofficial) solution isn't very good either:

$a_{3}=253534 \\ a_{4}=25353534 \\ \therefore a_{n}=2 \underbrace{535353 \ldots 53}_{(n-1) \text { Times } 53}4$

Now, $a_n \rightarrow$ divisible by $99 \Rightarrow$ by $\ 9 \ \& \ 11$ both.

Sum of digits $=6+8(n-1)$

To be divisible by 9 $\mathrm{n}=7,16,25,34,43,52,61,70,79,88, \ldots$

$a_{7}=2\underbrace{535353535353 }_{6 \text { Times } 53} 4$

But $a_{7} \rightarrow$ Not divisible by 11 .

$a_{16}=2\underbrace{5353535353 \ldots \ldots 53 }_{15 \text { Times } 53}4$

Similarly, $a_{16} \rightarrow$ Not divisible by 11 .

Now, $n=88$

$a_{88}=2 \underbrace{5353 \ldots \ldots 53}_{87 \text { Times } 53}4$

Divisibility by $11 \rightarrow|(2+3+3 \ldots \ldots)-(5+5+\ldots+ 4)|$ $$ \begin{array}{l} =|263-439| \\ =176 \end{array} $$ $\therefore$ Least $n=88$

Hints are more appreciated than the solution.

Answer 1

Your method can work quite well. For all $1 \lt i \le n$, note $a_i - a_{i-1}\equiv 35 \pmod{99}$ means each $a_i$ is congruent to $35$ more than the previous one of $a_{i-1}$. Thus, starting from $a_1$ and repeating this $n - 1$ times, you get

$$a_n \equiv a_1 + (n - 1)35 \equiv 35n - 11 \equiv 0 \pmod{99} \tag{1}\label{eq1A}$$

Since $99 = 9(11)$, you can split \eqref{eq1A} into

$$35n - 11 \equiv 0 \pmod{9} \implies 8n - 2 \equiv 0 \pmod{9} \implies 4n \equiv 1 \pmod{9} \tag{2}\label{eq2A}$$ $$35n - 11 \equiv 0 \pmod{11} \implies 2n \equiv 0 \pmod{11} \implies n \equiv 0 \pmod{11} \tag{3}\label{eq3A}$$

Note \eqref{eq3A} means $n = 11k, \; k \in \mathbb{Z}$. You can thus use this to determine $k$ from \eqref{eq2A}.

Answer 2

Claim 1: a number is divisible by $9$ if and only if the sum of its digits (written in base $10$) is $0\pmod 9$.

Proof: if $n=\sum_{k=0}^md_k10^k$, then since $10^k\equiv 1\pmod 9$, we have $n\equiv \sum_{k=0}^m d_k\pmod 9$. Thus $9$ divides $n$ if and only if $9$ divides $\sum_{k=0}^md_k$.

Claim 2: a number is divisible by $11$ if and only if the alternating sum of its digits is $0\pmod {11}$.

Proof: the same thing, but now $10^k\equiv (-1)^k\pmod{11}$.

Now $a_n$ is divisible by $99$ if and only if it is divisible by $9$ and $11$, and the sequence is designed so we can easily tell what the digits are. Writing $b_n$ for the sum of the digits of $a_n$, we have

$$b_2=7+7, b_3=7+8+7,b_4=7+8+8+7,$$

etc. Mod $9$, each successive term subtracts one. Inductively, one sees that $a_n$ is divisible by nine if and only if $n=9k+7$ for some $k$.

Now let $c_n$ be the alternating sum of the digits. We have

$$c_2=2-5+3-4,c_3=2-5+3-5+3-4,$$ etc. In other words,

$$c_2=-4,c_3=-6,c_4=-8,$$ etc. Inductively, $c_n=-2n$, and $a_n$ is divisible by $11$ if and only if $n=11k$.

All together, $a_n$ is divisible by $99$ if and only if $n\equiv 7\pmod 9$ and $n\equiv 0\pmod {11}$. It is then straightforward to use the Euclidean algorithm to find the set of solutions $\{88+99k:k\in\Bbb Z\}$.