Teilbarkeit Quersumme b-adische Darstellung

23.07.2022, 17:57

_Bastii

Teilbarkeit Quersumme b-adische Darstellung

Hallo,

ich soll zeigen das gilt:
$\begin{eqnarray*} t \mid Q(x) \Rightarrow t \mid x \end{eqnarray*}$ für jedes $\begin{eqnarray*} t \end{eqnarray*}$ mit $\begin{eqnarray*} t \mid (b-1) \end{eqnarray*}$ .
$\begin{eqnarray*} x = a_{k-1} \cdot b^{k-1} + ... + a_1 \cdot b^1 + a_0 \cdot b^0 \end{eqnarray*}$ in b-adischer Darstellung, $\begin{eqnarray*} Q(x) \end{eqnarray*}$ ist die Quersumme von $\begin{eqnarray*} x \end{eqnarray*}$ und $\begin{eqnarray*} x \in \mathbb{N}^{>0} \end{eqnarray*}$ .

Ich habe nur keine Ahnung, wie ich anfangen soll.

Vorher habe ich in einer anderen Aufgabe $\begin{eqnarray*} t \mid a_0 \Rightarrow t \mid x \end{eqnarray*}$ , für jeden Teiler $\begin{eqnarray*} t \end{eqnarray*}$ von $\begin{eqnarray*} b \end{eqnarray*}$ folgendermaßen gezeigt:

Wegen $\begin{eqnarray*} t \mid b \end{eqnarray*}$ folgt $\begin{eqnarray*} t \mid a_{k-1} \cdot b^{k-1} + ... + a_1 \cdot b^1 \Leftrightarrow t \mid (x-a_0) \Leftrightarrow x = k_1 \cdot t + a_0 \end{eqnarray*}$
Da zusätzlich $\begin{eqnarray*} t \mid a_0 \Leftrightarrow a_0 = k_2 \cdot t \end{eqnarray*}$ gilt
$\begin{eqnarray*} \Rightarrow x = k_1 \cdot t + k_2 \cdot t = (k_1 + k_2) \cdot t = k \cdot t \Rightarrow t \mid x \end{eqnarray*}$ , $\begin{eqnarray*} k, k_1, k_2 \in \mathbb{Z} \end{eqnarray*}$

Erstmal hoffe ich, dass meine Argumentation für die zweite Aufgabe nicht fehlerhaft ist.
Mit dieser Vorgehensweise und anderen Versuchen bin ich bei der ersten Aufgabe jedoch nicht weiter gekommen.

Hat jemand eine Tipp, wie ich an die erste Aufgabe heran gehen kann?

23.07.2022, 18:39

Mathema

Auf diesen Beitrag antworten »

Moin Basti!

Nutze $\begin{eqnarray*} b^i\equiv 1 \bmod t \end{eqnarray*}$ um aus $\begin{eqnarray*} x=\sum\limits_{i=0}^n a_i b^i \end{eqnarray*}$ und $\begin{eqnarray*} Q(x)=\sum\limits_{i=0}^n a_i \end{eqnarray*}$ dann $\begin{eqnarray*} x\equiv Q(x) \bmod t \end{eqnarray*}$ zu folgern.

Anstatt \Rightarrow schreibt man bei Aussagen in $\begin{eqnarray*} \LaTeX \end{eqnarray*}$ übrigens besser \implies, also $\begin{eqnarray*} t \mid Q(x) \implies t \mid x \end{eqnarray*}$ . Anstatt $\begin{eqnarray*} \Leftrightarrow \end{eqnarray*}$ schreibt dann \iff, also $\begin{eqnarray*} A \iff B \end{eqnarray*}$ .

Deinen Beweis habe ich mir nicht angesehen.

Wink

23.07.2022, 18:48

Elvis

Auf diesen Beitrag antworten »

Der Beweis ist in Ordnung, man könnte ihn noch etwas besser strukturieren, damit er schneller einleuchtet.

Für die 2. Aufgabe habe ich mir überlegt, dass man $\begin{eqnarray*} x=\sum_{l=0}^ka_lb^l=a_0+\sum_{l=1}^k(a_l(b^l-1)+a_l)=\sum_{l=1}^ka_l(b^l-1)+Q(x) \end{eqnarray*}$ schreiben könnte und dann mit $\begin{eqnarray*} t|Q(x)\wedge t|b-1 \end{eqnarray*}$ weiter kommt.

Eigentlich must du nur noch aus der Voraussetzung $\begin{eqnarray*} t|b-1 \end{eqnarray*}$ Mathemas Behauptung $\begin{eqnarray*} t|b^l-1 \end{eqnarray*}$ folgern (dividiere $\begin{eqnarray*} b^l-1 \end{eqnarray*}$ durch $\begin{eqnarray*} b-1 \end{eqnarray*}$ , dann steht alles da).

23.07.2022, 20:17

Mathema

Auf diesen Beitrag antworten »

Zitat:

Original von Elvis
[...] Mathemas Behauptung $\begin{eqnarray*} t|b^l-1 \end{eqnarray*}$ folgern (dividiere $\begin{eqnarray*} b^l-1 \end{eqnarray*}$ durch $\begin{eqnarray*} b-1 \end{eqnarray*}$ , dann steht alles da).

Das sollte Basti eigentlich kennen: Teilbarkeit von Potenzen (#3)

24.07.2022, 18:14

_Bastii

Auf diesen Beitrag antworten »

Danke erstmal für eure Tipps aber irgendwie verstehe ich es noch nicht wirklich.

Das $\begin{eqnarray*} t \mid (b-1) \iff b \equiv_t 1 \implies b^i \equiv_t 1, i \in \mathbb{N}^0 \end{eqnarray*}$ gilt, verstehe ich.

Bei euren Ansätzen zeige ich doch aber $\begin{eqnarray*} t \mid x \implies t \mid Q(x) \end{eqnarray*}$ und nicht $\begin{eqnarray*} t \mid Q(x) \implies t \mid x \end{eqnarray*}$ , was ich eigentlich zeigen soll, oder?
Ich muss doch erstmal bei $\begin{eqnarray*} t \mid Q(x) \end{eqnarray*}$ oder/und $\begin{eqnarray*} t \mid (b-1) \end{eqnarray*}$ starten, oder nicht?

24.07.2022, 21:26

Elvis

Auf diesen Beitrag antworten »

Voraussetzung ist, dass t ein Teiler von b-1 und ein Teiler von Q(x) ist. So wie ich x als Summe dargestellt habe, folgt sofort, dass t dann ein Teiler von x ist.

27.07.2022, 14:44

_Bastii

Auf diesen Beitrag antworten »

Stimmt, mich hatte nur die Richtung verwirrt.

Danke!

Neue Frage »

Antworten »

Teilbarkeit Quersumme b-adische Darstellung

Verwandte Themen