Beweisen von Teilbarkeitsregeln bei Kongruenzen

Question

Für n ∈ ℕ schreiben wir die Dezimaldarstellung von n in der Form

$$ n\quad =\quad { n }_{ r }{ n }_{ r-r }....{ n }_{ 1 }{ n }_{ 0 }\quad =\quad { n }_{ 0 }+{ n }_{ 1 }{ { 10 }^{ 1 }+ }{ n }_{ 2 }{ 10 }^{ 2 }+....+{ n }_{ r }{ 10 }^{ r } $$

mit Ziffern n_j ∈ {0,1,...,8,9}. Beweise folgende Teilbarkeitsregeln:

a) n ≡ n₀ + n₁ + ... + n_r (mod 3)

b) n ≡ n₀ + n₁ + ... + n_r (mod 9)

c) n ≡ n₀ - n₁ + n₂ -+ ... +(-1)^r n_r (mod 11)

Answer 1

a) und b )

betrachte  n = no + n₁*10 + n₂*10^2 + ...  n_r * 10^r

=  no + n₁*(10 - 1  +1 ) + n₂*(10^2 -1 +1  + ...  n_r * (10^r-1 + 1 )

= no + n₁*(10 - 1 ) + n₁*1  + n₂*(10^2 -1)  + n₂*1  + ...  n_r * (10^r-1)  + n_r* 1

Die Klammern von der Form 10^k - 1 sind alle durch 9 und also

auch durch 3 teilbar , also ≡ 0  mod (3) und auch mod (9) .

Also bleibt mod (3) oder mod(9) nur noch das rote übrig

Das ist genau die Quersumme.

Für mod(11) bedenke  10^k -1 ist durch 11 teilbar, wenn

k gerade und   10^k +1 ist durch 11 teilbar, wenn k ungerade.

Also machst du den Ansatz

  no + n₁*(10 +1  -1 ) + n₂*(10^2 -1 +1  + ...  n_r * (10^r  + (-1)^r  - (-1)^r   )

und dann wie oben.

Comments

Das find ich noch gut zu verstehen. Aber wie wäre es bei der Teilbarkeit durch 2? Also eine Zahl ist ja durch 2 teilbar, wenn die letzten beiden Ziffern durch 2 teilbar sind.Bei mod 3 und mod 9 zb betrachtet man ja die ganze Zahl.Aber bei mod 2 müsste man die Zahl aufteilen, damit man man die letzten beiden Ziffern alleine stehen hat.Wie soll das dann da funktionieren?

---

Bei 2 genügt sogar die letzte Ziffer. Wenn du etwa

256 hast, dann ist  250+6

Der erst Summand endet auf 0, ist also durch 10 und damit durch 2 teilbar,

also kommt es nur auf die letzte Ziffer an.
Bei Teilbarkeit durch 4 die letzten beiden.

---

Ja, ich meinte auch mod4. keine Ahnung, wieso ich zwei geschrieben habe. aber bei 4 macht die Formel, die bei 3 und 9 angewandt wird, ja keinen Sinn mehr. wie würde man das dann bei 4 ausdrücken? Ist das dann n-1?

---

bei 4, etwa   54648  kannst du zerlegen

54600  +  48

Die erste Zahl geht durch 100, also auch durch 4 und somit

Hängt das Ergebnis von 54648  nur von den letzten beiden Ziffern ab.

Answer 2

n₀ ≡ n₀ mod 9

10n₁ ≡ n₁ mod 9

100n₂ ≡ n₂ mod 9

1000n₃ ≡ n₃ mod 9

....       ....        ....

10^rn_r ≡ n_r mod 9

Wenn man diese Zeilen addiert, steht links die Zahl, deren Teilbarkeit durch 9 geprüft wird und rechts (n₀ + n₁+n₂+n₃+....+n_r) mod 9, also der Rest der Quersumme bei Teilen durch 9.