Modulare Arithmetik und Teilbarkeitsregeln, Beweisen

Question

Aufgabe:

Zeigen Sie anhand der Regeln der modularen Arithmetik, dass die Zahl

a = a0 + a1 · 10 + a2 · 10^2 + ··· + ak · 10^k
(mit 0 ≤ ai < 10 für 0 ≤ i ≤ k, k ∈ N)

genau dann durch 9 teilbar ist, wenn ihre Quersumme

q(a) = a0 + a1 + a2 + ··· + ak

durch 9 teilbar ist.

Problem/Ansatz:

Ich finde im Internet keine Lösungsansätze für dieses Problem. Kann mir jemand helfen und die Aufgabe inkl. Lösungsweg aufzeigen?

Answer 1

Die 10er Potenzen sind alle kongruent 1 Modulo 9.

Also gilt :  a0 + a1 · 10 + a2 · 10^2 + ··· + ak · 10^k

              ≡ a0 + a1 + a2 + ··· + ak       mod 9.

Teilbarkeit durch 9 heißt ja  ...     ≡ 0  mod 9