漸化式とモジュラー算術の誤った解

Question

しましょう $a_{10} = 10$、および各整数に対して $n >10$ しましょう $a_n = 100a_{n - 1} + n$。最小限を見つける$n > 10$ そのような $a_n$ の倍数です $99$。（出典：2017 AIME I）

これが私の解決策です：

最小限を見つけたい $n$ そのような $a_n\equiv 0\pmod{99},$ 漸化式と $a_n \equiv a_{n-1} + n \pmod{99}.$ また、すべての $n > 10,$ $a_n = \sum_{k=10}^n k = \frac{10 + n}{2} \cdot (n-9),$ だから私たちは最小限を見つけたい $n$ そのような $$(10 + n)(n - 9)2^{-1} \equiv 50(10+n)(n - 9) \equiv 0 \pmod{99}.$$ $$50(n^2+n-90) \equiv 50(n^2+n+9) \equiv 50n(n+1)+450 \equiv 0 \\ \Longleftrightarrow 50n(n+1) \equiv 45 \Longleftrightarrow n(n+1) \equiv 45\cdot 50^{-1} \equiv 90 \Longleftrightarrow n(n+1) \equiv 90.$$ 次に $n\equiv 9 \pmod{99}$、だから最小限 $n>10$ です $108$。

のようだ $n=108$ 実際には次の意味で機能します $99 \mid a_{108}$、しかし実際の答えは

45

最小値を与えるためにソリューションをどのように編集する必要がありますか？2行目のどこかで私の解決策が少し疑わしいものになったのではないかと思いますが、なぜそれが間違った答えを与えるのかわかりません。

Answer 1

あなたは結論を通してうまくやった $n(n+1)\equiv90\bmod99$、しかしそれに対するあなたの解決策は欠けていました。

私は中国の剰余定理を使用してその合同を解決します。

$99$ の製品です $11$ そして $9$、互いに素です。

$n(n+1)\equiv0\bmod9$ そして $n(n+1)\equiv2\bmod11$。

$n\equiv0 $ または $8\bmod9$ そして $n\equiv1$ または $9\bmod11$。

これらをまとめると、 $n\equiv45, 9, 89$、または $53\bmod99$。

あなたは今それを手に入れましたか？