Ordung von Produkten in abelschen Gruppen

Mal wieder etwas Gruppentheorie (von hier).

Es sei ${(G,\ \cdot,\ 1)}$ eine abelsche Gruppe. $a$ und $b$ seien zwei Gruppenelemente endlicher Ordnung, d.h. es gebe $k,\ l\in\N\setminus\{0\}$ mit \[ k = \min\{p\in\N\setminus\{0\} \mid a^p = 1\}\quad,\\ l = \min\{p\in\N\setminus\{0\} \mid b^p = 1\}\quad.\\ \] Wir behaupten, dass dann die Ordnung von $a\,b$ nicht größer sein kann als $\mathrm{kgV}(k,\ l)$.

Nun: Sei $t:=\mathrm{kgV}(k,\ l)$. Dann gilt \[\ \begin{array}{rcll} (a\,b)^t &=& a^t\,b^t\\ &=& a^{\alpha\,k}\,b^{\beta\,l} & \text{für passende $\alpha,\ \beta \in \N$}\\ &=& a^{k\,\alpha}\,b^{l\,\beta}\\ &=& \left(a^k\right)^\alpha\,\left(b^l\right)^\beta\\ &=& 1^\alpha\,1^\beta\\ &=& 1\quad. \end{array} \] Also ist $\mathrm{ord}(a\,b)$ ein Teiler von $\mathrm{kgV}(k,\ l)$, woraus die Behauptung sofort folgt.

Teilbarkeit durch $7$

Aus dem Tutorium.

Sei $z$ eine im Dezimalsystem mehrstellige ganze Zahl. Man bilde aus $z$ die Zahl ${z'\in\Z}$, indem man die Einerstelle von $z$ streiche und von der verbleibenden Zahl das Doppelte der gestrichenen Ziffer subtrahiere.
Man zeige: Genau dann ist $z'$ durch $7$ teilbar, wenn $z$ durch $7$ teilbar ist. Man entwickle daraus einen Algorithmus, mit dem man die Teilbarkeit einer ganzen Zahl ${n\neq0}$ durch $7$ in ${\mathcal O(\log(\abs n))}$ Schritten prüfen kann.

Und das geht so:

Sei ${n\in\N_{\geqslant1}}$. Seien ${a_0,\ldots,a_n\in\{0,\ldots,9\}}$, und es gelte ${a_1\neq0}$.
Setze ${z:=\displaystyle\sum_{k=0}^{n}a_k\,10^k}$ und ${z':=-2\,a_0+\displaystyle\sum_{k=0}^{n-1}a_{k+1}\,10^k}$.

Wir müssen zeigen, dass aus ${7\divides z'}$ die Aussage ${7\divides z}$ folgt und umgekehrt.

Gelte also ${7\divides z'}$. Dann gibt es ${l\in\Z}$ mit ${7\,l=z'}$, d.h. ${7\,l=-2\,a_0+\displaystyle\sum_{k=0}^{n-1}a_{k+1}\,10^k}$. Es sind die folgenden Aussagen äquivalent: \[ \begin{array}{rcl} 7\,l&=&-2\,a_0+\displaystyle\sum_{k=0}^{n-1}a_{k+1}\,10^k\\ 70\,l&=&10\cdot\left(-2\,a_0+\displaystyle\sum_{k=0}^{n-1}a_{k+1}\,10^k\right)\\ 70\,l&=&-20\,a_0+\displaystyle\sum_{k=0}^{n-1}a_{k+1}\,10^{k+1}\\ 70\,l&=&-20\,a_0+\displaystyle\sum_{k=1}^{n}a_{k}\,10^{k}\\ 70\,l+20\,a_0&=&\displaystyle\sum_{k=1}^{n}a_{k}\,10^{k}\\ 70\,l+21\,a_0&=&a_0+\displaystyle\sum_{k=1}^{n}a_{k}\,10^{k}\\ 70\,l+21\,a_0&=&\displaystyle\sum_{k=0}^{n}a_{k}\,10^{k}\\ 70\,l+21\,a_0&=&z\\ \end{array} \]
Es gilt also ${70\,l+21\,a_0=z}$, und wegen ${7\divides70\,l}$ und ${7\divides21\,a_0}$ folgt ${7\divides70\,l+21\,a_0}$, d.h. ${7\divides z}$. Dies war eine der zu zeigenden Behauptungen.

Die andere Richtung der Äquivalenzaussage erhält man, indem man annimmt, $z$ sei durch ${7}$ teilbar, beachtet, dass mit $z$ auch $z-21\,a_0$ durch $7$ teilbar ist und die oben stehende Äquivalenzenkette von unten nach oben liest. Genauer: \[ \begin{array}{rcl} 7\divides z &\implies& 7\divides z-21\,a_0\\ &\implies& 7\divides -20\,a_0+\displaystyle\sum_{k=1}^{n}a_{k}\,10^{k}\\ &\implies& 7\divides 10\cdot\left(-2\,a_0+\displaystyle\sum_{k=1}^{n}a_{k}\,10^{k-1}\right)\\ &\implies& 7\divides 10\cdot\left(-2\,a_0+\displaystyle\sum_{k=0}^{n-1}a_{k+1}\,10^k\right)\\ &\implies& 7\divides -2\,a_0+\displaystyle\sum_{k=0}^{n-1}a_{k+1}\,10^k\\ &\implies& 7\divides z'\\ \end{array} \]
Wie der Algorithmus aussieht, ist damit klar: Ist die gegebene Zahl ${n\in\Z}$ negativ, so gehe man zu ihrem Betrag über. Ist sie ein- oder zweistellig, so lese man die Teilbarkeit bzw. Nichtteilbarkeit durch $7$ direkt ab. Anderenfalls verkleinere man sie mittels des gegebenen Verfahrens so lange, bis sie kleiner als $100$ ist oder auf einen Blick als nicht durch $7$ teilbar zu erkennen ist (z.B. $5678$). Da die Anzahl der Stellen in jedem Schritt um mindestens $1$ abnimmt, ist die Laufzeitschranke ebenfalls sofort einzusehen.

Eine quadratische diophantische Gleichung

Die Gleichung \[ a^2 \equiv 3 \pmod{109} \] sieht harmloser aus, als sie ist.

Man finde ein $a\in\{0,\ldots,108\}$, das sie erfüllt.

Wir lassen den Zusatz $\pmod{109}$ im Folgenden weg.
Dem auf der Matheplanet-Seite zu findenden Hinweis $121=109+12$ entnehmen wir die Gleichung \[ 11^2 \equiv 2^2\cdot 3\quad. \] Das sieht einigermaßen vielversprechend aus: auf der rechten Seite stört noch der Faktor $2^2$. Es ist $109$ eine Primzahl; also ist $(\Z / 109\Z,\ \cdot)$ eine Gruppe und damit jedes $x\in\{1,\ldots,108\}$ multiplikativ invertierbar. Wir bekommen ihn weg, indem wir beide Seiten der Gleichung mit dem multiplikativen Inversen von $2$ (ja, genau, von $2$, nicht von $4=2^2$) multiplizieren, denn es gilt $(2^2)^{-1} = (2^{-1})^2$. Also können wir wie folgt fortfahren: \[ \begin{array}{rrcl} & 11^2 &\equiv& 2^2\cdot 3\\ \iff& 11^2\cdot\left(2^2\right)^{-1} &\equiv& 3\\ \iff& 11^2\cdot\left(2^{-1}\right)^2 &\equiv& 3\\ \iff& \left(11\cdot2^{-1}\right)^2 &\equiv& 3\\ \iff& \left(11\cdot55\right)^2 &\equiv& 3\\ \iff& 605^2 &\equiv& 3\\ \iff& \left(5\cdot109+60\right)^2 &\equiv& 3\\ \iff& 60^2 &\equiv& 3\\ \end{array} \] Also ist $a=60$ eine Lösung.

Stimmt's denn auch? Ja:
\[ 60^2 \equiv 3600 \equiv 33\cdot 109+3 \equiv 3 \pmod{109}\quad. \] Damit ist eine Lösung gefunden; aber es gibt natürlich noch eine weitere. (Denn $\left(\Z / 109\Z,\ +,\ \cdot\right)$ ist ein Körper, und jede quadratische Gleichung hat über einem Körper genau zwei Lösungen.) Wolfram Alpha behauptet, dass $a=49$ eine weitere Lösung ist. Aber wie kommt man ohne Ausprobieren darauf?
Es wäre wohl machbar, wenn man einen Hinweis ähnlich wie oben gegeben hätte... Oder man lässt die Theorie der Pellschen Gleichungen (Skript S. 89) darauf los.

Wie bekommt man einen Hinweis ähnlich dem oben gegebenen? Durch Ausprobieren :)

#!/bin/bash

for ((q=0; q < 500; q++)); do

    for ((r=0; r < 500; r++)); do

        t=$((q*q-3*r*r))

        ((t == 109)) && printf "q = %d, r = %d\n" "$q" "$r"

    done

done

Die Ausgabe dieses Codes lautet

q = 11, r = 2
q = 16, r = 7
q = 28, r = 15
q = 53, r = 30
q = 101, r = 58
q = 196, r = 113
q = 376, r = 217

Die Werte q = 11, r = 2 entsprechen dem gegebenen Hinweis.
Also versuchen wir die Werte q = 16, r = 7. Indem wir mit ihnen die gleiche Rechnung durchführen wie oben, erhalten wir \[ \begin{array}{rrcl} & 16^2 &\equiv& 7^2\cdot 3\\ \iff& 16^2\cdot\left(7^2\right)^{-1} &\equiv& 3\\ \iff& 16^2\cdot\left(7^{-1}\right)^2 &\equiv& 3\\ \iff& \left(16\cdot7^{-1}\right)^2 &\equiv& 3\\ \iff& \left(16\cdot78\right)^2 &\equiv& 3\\ \iff& 1248^2 &\equiv& 3\\ \iff& \left(11\cdot109+49\right)^2 &\equiv& 3\\ \iff& 49^2 &\equiv& 3\\ \end{array} \] Also ist $a=49$ tatsächlich eine Lösung. Stimmt's denn auch? Ja:
\[ 49^2 \equiv 2401 \equiv 22\cdot 109+3 \equiv 3 \pmod{109}\quad. \] Die analoge Rechnung mit weiteren Werten für q und r durchzuführen, sei dem Leser als Übung überlassen.

Teilbarkeit per geometrischer Reihe, Teil 1

Aus dem Tutorium.

Man zeige mithilfe einer endlichen geometrischen Reihe, dass für alle $k,\ n\in\N_{\geqslant1}$ gilt: \[ k \mid n \implies 2^k-1 \mid 2^n-1\quad. \] Nun: Seien $k,\ n\in\N_{\geqslant1}$. Es gelte $k\mid n$, d.h es gebe ein $q\in\N$ mit $n=q\cdot k$. Der Fall $q=0$ tritt nicht ein. Der Fall $q=1$ ist trivial. (Ja, wirklich! Aus $k=n$ folgt $2^k-1=2^n-1$, also auch $2^k-1 \mid 2^n-1$.)

Im Fall $q>1$ folgt \[ \begin{array}{rcl} 2^n-1 &=& \displaystyle\sum_{i=0}^{n-1} 2^i\\ &=& \displaystyle\sum_{i=0}^{k-1} 2^i+\displaystyle\sum_{i=k}^{n-1} 2^i\\ &=& 2^k-1+\displaystyle\sum_{i=k}^{n-1} 2^i\\ &=& 2^k-1+2^k\cdot\displaystyle\sum_{i=0}^{n-1-k} 2^i\quad.\\ \end{array} \] Auf die letzte Summe können wir diese Umformungen natürlich erneut anwenden (sofern $q>2$) und erhalten \[ \begin{array}{rcl} 2^n-1 &=& \displaystyle\sum_{i=0}^{n-1} 2^i\\ &=& 2^k-1+\displaystyle\sum_{i=k}^{n-1} 2^i\\ &=& 2^k-1+2^k\cdot\displaystyle\sum_{i=0}^{n-1-k} 2^i\\ &=& 2^k-1+2^k\cdot\left(2^k-1+2^k\cdot\displaystyle\sum_{i=0}^{n-1-2\cdot k} 2^i\right)\quad. \end{array} \] Wir sehen, dass wir auf diese Weise genau $k$ Mal den Faktor $2^k$ ausklammern können und am Ende einen Ausdruck der Form \[ 2^n-1 = 2^k-1+2^k\cdot\left(2^k-1+2^k\cdot\left(\ldots\cdot\left(\sum_{i=0}^{n-1-q\cdot k} 2^i\right)\ldots\right)\right) \] erhalten.

Dabei ist die Summe $\sum_{i=0}^{n-1-q\cdot k} 2^i$ gleich Null, denn die obere Summationsgrenze ist $-1$ und damit kleiner als die untere. Also ist diese Summe durch $2^k-1$ teilbar. Multiplikation mit $2^k$ ändert daran nichts, ebensowenig wie die anschließende Addition von $2^k-1$. Indem wir uns auf diese Weise durch die Klammerebenen arbeiten, sehen wir, dass die gesamte rechte Seite durch $2^k-1$ teilbar ist, also auch die linke, und dies war zu zeigen.

Kann man in diesem Beweis auf die Pünktchenschreibweise verzichten?

Ja, man kann! Und zwar mit Abschnittsinduktion. Dazu mehr in einem späteren Post.