Online bestellen beim Versandriesen

„Ich brauche einen Zirkel. Den könnt' ich online bestellen… Aber er muss UNBEDINGT bis Mitte Januar da sein!“

Klar doch! Wir haben zwar Anfang November, aber trotzdem… Amazon bietet genau das! :)

Und wenn ich mir noch 1800 Stunden Zeit lassen kann mit der Bestellung – was kann da noch groß schiefgehen?

Präsident der Uni Hamburg hält Bologna-Reform für Fehlschlag

Endlich sagt es mal jemand...

Präsident der Uni Hamburg hält Bologna-Reform für Fehlschlag (Meldung im Deutschlandfunk, 30. Oktober 2016)

Das komplette Interview (Welt am Sonntag, 30. Oktober 2016)

Ich hätte nicht übel Lust, die Diskussion weiterzuführen!

tdu

$\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.