Teilbarkeit im Binärsystem

Question

kann mir jemand bei dieser Aufgabe weiterhelfen?

Wir betrachten Teilbarkeitsregeln in Binärdarstellungen. Sei hierzu \( n=\sum \limits_{k=0}^{2 m} a_{k} 2^{k} \) mit \( m \in \mathbb{N} \) und \( a_{0}, \ldots, a_{2 m} \in\{0,1\} \) die Binärdarstellung von \( n \in \mathbb{N} . \) Zeigen Sie folgende Teilbarkeitsregeln:

a) \( n \) ist genau dann durch 3 teilbar, wenn \( \sum \limits_{k=0}^{2 m} a_{k}(-1)^{k} \) durch 3 teilbar ist.
b) \( n \) ist genau dann durch 3 teilbar, wenn \( \sum \limits_{k=0}^{m} a_{2 k}+2 a_{2 k+1} \) durch 3 teilbar ist.
c) \( n \) ist genau dann durch 5 teilbar, wenn \( \sum \limits_{k=0}^{m}\left(a_{2 k}+2 a_{2 k+1}\right) \cdot(-1)^{k} \) durch 5 teilbar ist.
d) Finden Sie eine entsprechende Vorschrift für Teilbarkeit durch \( 7 . \)

Comments

könnte mir bitte noch jemand helfen? ich würde diesen aufgabe sehr gerne lösen..

Answer 1

Vorschlag zu Aufgabe d):  n ist genau dann durch 7 teilbar, wenn Σ_k=0 ^m(a_3k+2a_3k+1+4a_3k+2) durch 7 teilbar ist.

a) heißt auf Deutsch: n ist genau dann durch 3 teilbar, wenn die alternierende Quersumme durch 3 teilbar ist.

b) heißt auf Deutsch: n ist genau dann durch 3 teilbar, wenn die Quersumme der Zweierblöcke durch 3 teilbar ist. Beispiel 110100111 hat die Quersumme der Zweierblöcke 1+10+10+01+11.

c) heißt auf Deutsch: n ist genau dann durch 5 teilbar, wenn die alternierende Quersumme der Zweierblöcke durch 5 teilbar ist.

d) heißt auf Deutsch: n ist genau dann durch 7 teilbar, wenn die Quersumme der Dreierblöcke durch 7 teilbar ist.

Comments

Danke Schonmal :) was es auf deutsch heisst wusste ich, aber ich hab leider keine Ahnung wie ich einen Beweis dazu anfangen bzw. Machen soll.

---

Das steht in Büchern über elementare Zahlentheorie (z.B. von Padberg).

---

Achso ok. Dies habe ich nur leider gerade nicht zur Hand und die Bibliothek der Universität hat an Sonntagen geschlossen. Gäbe es noch eine andere Empfehlung, wie ich an die Lösungen der Aufgaben gelangen könnte?