$\sin\left(\frac{\pi}{5}\right) = \sqrt{\frac{5}{8}-\frac{\sqrt{5}}{8}}$

Wie bestimmt man den Wert $\sin\left(\frac{\pi}{5}\right)$ exakt?

Indem man $0=\sin\left(\pi\right)=\sin\left(5\cdot\frac{\pi}{5}\right)$ ausnutzt.

Zunächst gelten die Additionstheoreme \[ \begin{equation} \cos(x+y) = \cos(x)\cos(y)-\sin(x)\sin(y) \end{equation} \] \[ \begin{equation} \sin(x+y) = \sin(x)\cos(y)+\cos(x)\sin(y) \end{equation} \] für alle $x,y\in\R$, wovon man sich zum Beispiel überzeugen kann, indem man die Standardbasisvektoren der Ebene zunächst um den Winkel $x$ und dann um den Winkel $y$ dreht und beachtet, dass die Drehung eine lineare Abbildung ist und die Darstellungsmatrix der Verkettung der Drehungen aufstellt. Es gibt natürlich auch geometrische Beweise dafür, zum Bespiel bei Wikibooks.

Setzen wir $y=x$, so erhalten wir \[ \begin{equation} \cos(2\mspace{2mu}x)=\cos(x)^2-\sin(x)^2 \end{equation} \] sowie \[ \begin{equation} \sin(2\mspace{2mu}x)=2\sin(x)\cos(x)\quad, \end{equation} \] und indem wir auf die rechte Seite der Gleichung $(3)$ den trigonometrischen Pythagoras \[ \begin{equation} \cos(x)^2+\sin(x)^2=1 \end{equation} \] loslassen, folgt \[ \begin{equation} \cos(2\mspace{2mu}x)=1-2\cdot\sin(x)^2\quad. \end{equation} \] Daraus erhalten wir weiter \[ \begin{array}{rcll} \sin(4\mspace{2mu}x) &=& \sin(2\cdot2\mspace{2mu}x)\\ &=& 2\mspace{2mu}\sin(2\mspace{2mu}x)\cos(2\mspace{2mu}x) & (4)\\ &=& 2\cdot2\mspace{2mu}\sin(x)\cos(x)\cdot\left(1-2\mspace{2mu}\sin(x)^2\right) & (4), (3)\\ &=& 4\mspace{2mu}\sin(x)\cos(x)\cdot\left(1-2\mspace{2mu}\sin(x)^2\right)\\ \end{array} \] und damit \[ \begin{equation} \sin(4\mspace{2mu}x) = 4\mspace{2mu}\sin(x)\cos(x)-8\mspace{2mu}\sin(x)^3\cos(x)\quad. \end{equation} \] Mit ebenso wenig Aufwand finden wir \[ \begin{array}{rcll} \cos(4\mspace{2mu}x) &=& \cos(2\cdot2\mspace{2mu}x)\\ &=& 1-2\mspace{2mu}\sin(2\mspace{2mu}x)^2 & (6)\\ &=& 1-2\mspace{2mu}\left(2\sin(x)\cos(x)\right)^2 & (4)\\ &=& 1-2\cdot4\mspace{2mu}\sin(x)^2\cos(x)^2\\ &=& 1-8\mspace{2mu}\sin(x)^2\cos(x)^2\\ &=& 1-8\mspace{2mu}\sin(x)^2\cdot\left(1-\sin(x)^2\right) & (5)\quad,\\ \end{array} \] also \[ \begin{equation} \cos(4\mspace{2mu}x) = 1-8\mspace{2mu}\sin(x)^2+8\mspace{2mu}\sin(x)^4\quad. \end{equation} \] Es folgt \[ \begin{array}{rcll} \sin(5\mspace{2mu}x) &=& \sin(4\mspace{2mu}x+x)\\[2mm] &=& \sin(4\mspace{2mu}x)\cos(x)+\cos(4\mspace{2mu}x)\sin(x) & (2)\\[2mm] &=& \left(4\mspace{2mu}\sin(x)\cos(x)-8\mspace{2mu}\sin(x)^3\cos(x)\right)\cdot\cos(x) \\ && +\left(1-8\mspace{2mu}\sin(x)^2+8\mspace{2mu}\sin(x)^4\right)\cdot\sin(x) & (7), (8)\\[2mm] &=& 4\mspace{2mu}\sin(x)\cos(x)^2-8\mspace{2mu}\sin(x)^3\cos(x)^2\\ && +\sin(x)-8\mspace{2mu}\sin(x)^3+8\mspace{2mu}\sin(x)^5\\[2mm] &=& 4\mspace{2mu}\sin(x)\cdot\left(1-\sin(x)^2\right)-8\mspace{2mu}\sin(x)^3\cdot\left(1-\sin(x)^2\right)\\ && +\sin(x)-8\mspace{2mu}\sin(x)^3+8\mspace{2mu}\sin(x)^5 & (5)\\[2mm] &=& 4\mspace{2mu}\sin(x)-4\mspace{2mu}\sin(x)^3-8\mspace{2mu}\sin(x)^3+8\mspace{2mu}\sin(x)^5\\ && +\sin(x)-8\mspace{2mu}\sin(x)^3+8\mspace{2mu}\sin(x)^5\quad,\\ \end{array} \] was\[ \begin{equation} \sin(5\mspace{2mu}x) = 5\mspace{2mu}\sin(x)-20\mspace{2mu}\sin(x)^3+16\mspace{2mu}\sin(x)^5 \end{equation} \] bedeutet.

Damit ist $\sin\left(\frac{\pi}{5}\right)$ eine Nullstelle des Polynoms $16\mspace{2mu}x^5-20\mspace{2mu}x^3+5\mspace{2mu}x$. Da $\sin\left(\frac{\pi}{5}\right)$ von Null verschieden ist, können wir problemlos das Polynom $16\mspace{2mu}x^4-20\mspace{2mu}x^2+5$ betrachten. Es gilt \[ \begin{array}{lrcll} & 16\mspace{2mu}x^4-20\mspace{2mu}x^2+5 &=& 0\\ \iff & 16\mspace{2mu}x^4-20\mspace{2mu}x^2 &=& -5\\ \end{array} \] was wir auch in der Form \[ \begin{equation} \left(4\mspace{2mu}x^2\right)^2-5\cdot\left(4\mspace{2mu}x^2\right) = -5 \end{equation} \] schreiben können, und mit der Abkürzung $y:=4\mspace{2mu}x^2$ wird daraus $y^2-5\mspace{2mu}y=-5$, also \[ \begin{equation} y^2-5\mspace{2mu}y+5=0\quad. \end{equation} \] Wie man leicht nachrechnet, hat diese quadratische Gleichung die Lösungen $y_1=\frac{1}{2}\cdot\left(5+\sqrt{5}\right)$ und $y_2=\frac{1}{2}\cdot\left(5-\sqrt{5}\right)$. Wir müssen prüfen, ob diese auch die Gleichung $(10)$ erfüllen. Für $y_1$ ergibt sich \[ \begin{array}{rcll} {y_1}^2-5\mspace{2mu}y_1+5 &=& \left(\frac{1}{2}\cdot\left(5+\sqrt{5}\right)\right)^2-5\mspace{2mu}\cdot\frac{1}{2}\cdot\left(5+\sqrt{5}\right)\\ &=& \frac{1}{4}\cdot\left(5+\sqrt{5}\right)^2-\frac{5}{2}\cdot\left(5+\sqrt{5}\right)\\ &=& \frac{1}{4}\cdot\left(25+10\mspace{2mu}\sqrt{5}+5\right)-\frac{5}{2}\cdot\left(5+\sqrt{5}\right)\\ &=& \frac{1}{4}\cdot\left(30+10\mspace{2mu}\sqrt{5}\right)-\frac{1}{2}\cdot\left(25+5\mspace{2mu}\sqrt{5}\right)\\ &=& \frac{1}{4}\cdot\left(30+10\mspace{2mu}\sqrt{5}\right)-\frac{1}{4}\cdot\left(50+10\mspace{2mu}\sqrt{5}\right)\\ &=& \frac{1}{4}\cdot\left(30-50\right)\\ &=& \frac{1}{4}\cdot\left(-20\right)\\ &=& -5\quad. \end{array} \] Also ist $y_1$ eine Lösung von $(10)$.

Für $y_2$ ergibt sich \[ \begin{array}{rcll} {y_2}^2-5\mspace{2mu}y_2+5 &=& \left(\frac{1}{2}\cdot\left(5-\sqrt{5}\right)\right)^2-5\mspace{2mu}\cdot\frac{1}{2}\cdot\left(5-\sqrt{5}\right)\\ &=& \frac{1}{4}\cdot\left(5-\sqrt{5}\right)^2-\frac{5}{2}\cdot\left(5-\sqrt{5}\right)\\ &=& \frac{1}{4}\cdot\left(25-10\mspace{2mu}\sqrt{5}+5\right)-\frac{5}{2}\cdot\left(5-\sqrt{5}\right)\\ &=& \frac{1}{4}\cdot\left(25-10\mspace{2mu}\sqrt{5}+5\right)-\frac{1}{2}\cdot\left(25-5\mspace{2mu}\sqrt{5}\right)\\ &=& \frac{1}{4}\cdot\left(25-10\mspace{2mu}\sqrt{5}+5\right)-\frac{1}{4}\cdot\left(50-10\mspace{2mu}\sqrt{5}\right)\\ &=& \frac{1}{4}\cdot\left(25-10\mspace{2mu}\sqrt{5}+5-50+10\mspace{2mu}\sqrt{5}\right)\\ &=& \frac{1}{4}\cdot\left(25+5-50\right)\\ &=& \frac{1}{4}\cdot\left(-20\right)\\ &=& -5\quad. \end{array} \] Also ist auch $y_2$ eine Lösung von $(10)$.

Indem wir $y=4\mspace{2mu}x^2$ nach $x$ umstellen, erhalten wir $x_{1,\,2} = \pm\frac{1}{2}\mspace{2mu}\sqrt{\vphantom{y^2}y}$. Mit $y=y_1$ folgt \[ \begin{array}{rcll} x_1 &=& \frac{1}{2}\mspace{2mu}\sqrt{\vphantom{y^2}y_1}\\ &=& \frac{1}{2}\mspace{2mu}\sqrt{\frac{1}{2}\cdot\left(5+\sqrt{5}\right)}\\ &=& \sqrt{\frac{1}{4}}\cdot\mspace{2mu}\sqrt{\frac{1}{2}\cdot\left(5+\sqrt{5}\right)}\\ &=& \sqrt{\frac{1}{4}\cdot\frac{1}{2}\cdot\left(5+\sqrt{5}\right)}\\ &=& \sqrt{\frac{1}{8}\cdot\left(5+\sqrt{5}\right)} \end{array} \] und damit \[ \begin{equation} x_1 = \sqrt{\frac{5}{8}+\frac{\sqrt{\vphantom{5^2}5}}{8}}\quad,\quad x_2 = -\mspace{2mu}\sqrt{\frac{5}{8}+\frac{\sqrt{\vphantom{5^2}5}}{8}}\quad. \end{equation} \] Wegen $\sin(0)=0$ und da die Sinusfunktion auf dem Intervall $\left]0,\frac{\pi}{2}\right[$ streng monoton wachsend ist, ist $\sin\left(\frac{\pi}{5}\right)>0$, also ist $x_2$ uninteressant.

Mit $y=y_2$ folgt $x_{3,\,4} = \pm\frac{1}{2}\mspace{2mu}\sqrt{\vphantom{y^2}y_2}$, also \[ \begin{array}{rcll} x_3 &=& \frac{1}{2}\mspace{2mu}\sqrt{\vphantom{y^2}y_2}\\ &=& \frac{1}{2}\mspace{2mu}\sqrt{\frac{1}{2}\cdot\left(5-\sqrt{5}\right)}\\ &=& \sqrt{\frac{1}{8}\cdot\left(5-\sqrt{5}\right)} \end{array} \] und damit \[ \begin{equation} x_3 = \sqrt{\frac{5}{8}-\frac{\sqrt{\vphantom{5^2}5}}{8}}\quad,\quad x_4 = -\mspace{2mu}\sqrt{\frac{5}{8}-\frac{\sqrt{\vphantom{5^2}5}}{8}}\quad. \end{equation} \] Erneut ist $x_4<0$, also uninteressant.

Wir haben jetzt also zwei Werte für $\sin\left(\frac{\pi}{5}\right)$ zur Auswahl, nämlich $a:=\sqrt{\frac{5}{8}+\frac{\sqrt{\vphantom{5^2}5}}{8}}$ und $b:=\sqrt{\frac{5}{8}-\frac{\sqrt{\vphantom{5^2}5}}{8}}$, und müssen uns für einen der beiden Werte entscheiden.

Wir wissen, dass der Sinus auf dem Intervall $\left]0,\frac{\pi}{2}\right[$ streng monoton wächst, d.h. aus der Ungleichung \[ \begin{equation} \frac{\pi}{5} < \frac{\pi}{4} \end{equation} \] folgt \[ \begin{equation} \sin\left(\frac{\pi}{5}\right) < \sin\left(\frac{\pi}{4}\right) = \frac{1}{2}\mspace{2mu}\sqrt{\vphantom{5^2}2}\quad. \end{equation} \] (Dass tatsächlich $\sin\left(\frac{\pi}{4}\right) = \frac{1}{2}\mspace{2mu}\sqrt{\vphantom{5^2}2}$ ist, kann man sich am rechtwinkligen Dreieck veranschaulichen, indem man beachtet, dass zum Bogenmaß $\frac{\pi}{4}$ das Gradmaß $45^{\circ}$ gehört und den trigonometrischen Pythagoras (Gleichung $(5)$) anwendet.) Also brauchen wir nur abzuschätzen: Für $a$ erhalten wir \[ \begin{array}{lrcll} & \sqrt{\frac{5}{8}+\frac{\sqrt{\vphantom{5^2}5}}{8}} &<& \frac{1}{2}\mspace{2mu}\sqrt{\vphantom{5^2}2}\\ \iff & \frac{5}{8}+\frac{\sqrt{\vphantom{5^2}5}}{8} &<& \frac{1}{4}\mspace{2mu}\cdot2\\ \iff & \frac{5}{8}+\frac{\sqrt{\vphantom{5^2}5}}{8} &<& \frac{1}{2}\\ \iff & 5+\sqrt{5} &<& 4\\ \iff & \sqrt{5} &<& -1\quad, \end{array} \] also eine falsche Aussage. Also können wir den Wert $\sqrt{\frac{5}{8}+\frac{\sqrt{\vphantom{5^2}5}}{8}}$ verwerfen.

Für $b$ erhalten wir \[ \begin{array}{lrcll} & \sqrt{\frac{5}{8}-\frac{\sqrt{\vphantom{5^2}5}}{8}} &<& \frac{1}{2}\mspace{2mu}\sqrt{\vphantom{5^2}2}\\ \iff & \frac{5}{8}-\frac{\sqrt{\vphantom{5^2}5}}{8} &<& \frac{1}{4}\mspace{2mu}\cdot2\\ \iff & \frac{5}{8}-\frac{\sqrt{\vphantom{5^2}5}}{8} &<& \frac{1}{2}\\ \iff & 5-\sqrt{5} &<& 4\\ \iff & -\sqrt{5} &<& -1\\ \iff & \sqrt{5} &>& 1\\ \iff & 5 &>& 1\quad, \end{array} \] also eine wahre Aussage.

Also können wir festhalten: \[ \begin{equation} \sin\left(\frac{\pi}{5}\right) = \sqrt{\frac{5}{8}-\frac{\sqrt{\vphantom{5^2}5}}{8}}\quad. \end{equation} \]

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.

Es gibt genau eine Primzahl $p$ derart, dass $3\mspace{3mu}p+1$ eine Quadratzahl ist

Aus dem Tutorium.

Man benutze die folgende Charakterisierung von Primzahlen (vgl. Lemma von Euklid)

Eine natürliche Zahl $p$ größer als $1$ ist genau dann eine Primzahl, wenn für alle $a,\,b\in\Z$ gilt: Aus $p\mid a\mspace{3mu}b$ folgt $\ p\mid a\ $ oder $\ p\mid b$.

um zu zeigen: Es gibt genau eine Primzahl $p$ derart, dass $3\mspace{3mu}p+1$ eine Quadratzahl ist.
Quelle dazu.

Nun: Sei $p$ eine Primzahl, sei $n$ eine natürliche Zahl, und es gelte $3\mspace{3mu}p+1=n^2$. Daraus erhalten wir sofort \[ 3\mspace{3mu}p=n^2 -1\quad, \] und die dritte binomische Formel erlaubt es uns, das als \[ 3\mspace{3mu}p = (n-1)\cdot(n+1) \] zu schreiben. Die linke Seite ist das Produkt der Primzahlen $3$ und $p$, ist also (Lemma von Euklid!) nur durch $1$, $3$, $p$ und $3\mspace{3mu}p$ teilbar. Also gilt das auch für die rechte Seite. Daraus ergeben sich vier Fälle:

Fall	$n+1$	$n-1$
a)	$1$	$3\mspace{3mu}p$
b)	$3$	$p$
c)	$p$	$3$
d)	$3\mspace{3mu}p$	$1$

Im Fall a) gilt $n+1=1$, also $n-1=-1$, womit $n-1$ keine natürliche Zahl, also insbesondere kein Primfaktor von $3\mspace{3mu}p$, wäre. Also tritt dieser Fall nicht ein.

Im Fall b) gilt $n+1=3$, also $n=2$, also $n^2=4=3\mspace{3mu}p+1$ und damit $p=1$, womit $p$ keine Primzahl wäre. Also tritt dieser Fall nicht ein.

Im Fall c) gilt $n-1=3$, also $n=4$, also $p=5$ und $3\mspace{3mu}p+1=16=4^2=n^2$. Also ist $p=5$ eine Lösung!

Im Fall d) schleißlich gilt $n-1=1$, also $n+1=3\mspace{3mu}p$, also $p=1$, womit $p$ erneut keine Primzahl wäre. Also tritt auch dieser Fall nicht ein.

Damit gibt es genau eine Primzahl $p$ derart, dass $3\mspace{3mu}p+1$ eine Quadratzahl ist, nämlich $p=5$.

Binomischer Lehrsatz? Viel zu kompliziert.

Aus dem Tutorium.

Gibt es Ringe $R$, in denen die Gleichung $(a+b)^5 = a^5+b^5$ für alle $a,\,b\in R$ gilt?

Wir behaupten: Ja, solche Ringe gibt es. (Aber mit Sicherheit ist $\R$ kein Beispiel dafür!)

Sei $R$ ein beliebiger kommutativer Ring mit Eins, und seien $a,\,b\in R$. Multiplizieren wir einmal $(a+b)^5$ aus. Das ergibt \[ a^5 + 5\mspace{3mu}a\mspace{3mu}b^4 + 10\mspace{3mu}a^3\mspace{3mu}b^2 + 10\mspace{3mu}a^2\mspace{3mu}b^3 + 5\mspace{3mu}a\mspace{3mu}b^4 + b^5\quad, \] und wir sehen, dass alle Summanden bis auf den ersten und den letzten durch 5 teilbar sind. Es gilt also \[ (a+b)^5 \equiv a^5+b^5\pmod5\quad, \] weil alle anderen Summanden wegfallen.

Wenn wir also $R:=\Z_5$ setzen, dann haben wir erreicht, was wir wollten: Die lange Binomialentwicklung schnurrt auf zwei Summanden zusammen. Für alle $[a],\,[b]\in\Z_5$ gilt \[ ([a]+[b])^5 = [a]^5+[b]^5 = [a^5] + [b^5] = [a^5 + b^5]\quad. \]