Récurrence et solution incorrecte d'arithmétique modulaire

Question

Laisser $a_{10} = 10$, et pour chaque entier $n >10$ laisser $a_n = 100a_{n - 1} + n$. Trouvez le moins$n > 10$ tel que $a_n$ est un multiple de $99$. (Source: AIME I 2017)

Voici ma solution:

Nous souhaitons trouver le moins $n$ tel que $a_n\equiv 0\pmod{99},$ avec la relation de récurrence $a_n \equiv a_{n-1} + n \pmod{99}.$ Aussi, pour chaque $n > 10,$ $a_n = \sum_{k=10}^n k = \frac{10 + n}{2} \cdot (n-9),$ donc nous souhaitons trouver le moins $n$ tel que $$(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.$$ ensuite $n\equiv 9 \pmod{99}$, donc le moins $n>10$ est $108$.

Il paraît que $n=108$ fonctionne réellement dans le sens où $99 \mid a_{108}$, mais la vraie réponse est

45

Comment dois-je modifier ma solution pour lui donner la valeur minimale? Je soupçonne que quelque part le long de la deuxième ligne, ma solution est devenue un peu suspecte, je ne sais pas pourquoi elle donne la mauvaise réponse.

Answer 1

Vous avez bien fait la conclusion $n(n+1)\equiv90\bmod99$, mais votre solution manquait.

Je résoudrais cette congruence en utilisant le théorème chinois du reste;

$99$ est le produit de $11$ et $9$, qui sont relativement premiers.

$n(n+1)\equiv0\bmod9$ et $n(n+1)\equiv2\bmod11$.

$n\equiv0 $ ou $8\bmod9$ et $n\equiv1$ ou $9\bmod11$.

En les mettant ensemble, nous obtenons $n\equiv45, 9, 89$, ou $53\bmod99$.

Est-ce que tu vas l'avoir maintenant?