Klar doch! Wir haben zwar Anfang November, aber trotzdem… Amazon bietet genau das! :)
Dienstag, 1. November 2016
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?
Klar doch! Wir haben zwar Anfang November, aber trotzdem… Amazon bietet genau das! :)
Montag, 31. Oktober 2016
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
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
Mittwoch, 24. Februar 2016
$\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} \]
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} \]
Montag, 26. Oktober 2015
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.
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.
Freitag, 3. Juli 2015
Teilbarkeit durch $7$
Aus dem Tutorium.
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.
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.Und das geht so:
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.
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.
Donnerstag, 2. Juli 2015
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 isteine 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 :)
Die Ausgabe dieses Codes lautet
Die Werte
Also versuchen wir die Werte
\[ 49^2 \equiv 2401 \equiv 22\cdot 109+3 \equiv 3 \pmod{109}\quad. \] Die analoge Rechnung mit weiteren Werten für
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
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.
Montag, 13. April 2015
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.
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.
Mittwoch, 10. September 2014
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)
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:
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$.
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. \]
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. \]
Dienstag, 9. September 2014
Viermal abelsche Gruppen
Aus dem Tutorium.
Es sei $(G,\,\ast,\,e)$ eine Gruppe. Wir behaupten: $G$ ist genau dann abelsch, wenn die Abbildung $G\to G$, $a\mapsto a\ast a$, ein Homomorphismus ist.
Gelte zunächst: $G\to G$, $a\mapsto a\ast a$, ist ein Homomorphismus.
Seien $a,b\in G$. Dann gilt $\varphi(a\ast b) = a\ast b\ast a\ast b$ und $\varphi(a)\ast \varphi(b) = a\ast a\ast b\ast b$, wegen der Homomorphieeigenschaft von $\varphi$ also \[ a\ast b\ast a\ast b = a\ast a\ast b\ast b\quad. \] Nun liefert die Multiplikation mit $a^{-1}$ von links \[ b\ast a\ast b = a\ast b\ast b\quad, \] und indem wir von rechts mit $b^{-1}$ multiplizieren, erhalten wir \[ b\ast a = a\ast b\quad. \] Also ist $G$ abelsch.
Gelte nun: $G$ ist abelsch.
Dann gilt für alle $a,\,b\in G$: \[b\ast a=a\ast b\quad,\]also \[b\ast a\ast b = a\ast b\ast b\quad,\] also \[a\ast b\ast a\ast b = a\ast a\ast b\ast b\] und damit \[\varphi(a\ast b) =\varphi(a)\ast \varphi(b)\quad,\]also ist $\varphi$ ein Homomorphismus.
Hier gelten also beide Richtungen.
Nächste Behauptung: Gilt $a\ast a=e$ für alle $a\in G$, so ist $G$ abelsch.
Nun: Gelte $a\ast a=e$ für alle $a\in G$. Dann folgt \[a=a^{-1}\quad\text{für alle $a\in G$}\quad,\] also \[a\ast b=(a\ast b)^{-1}\quad\text{für alle $a\in G$}\quad,\] also \[a\ast b=b^{-1}\ast a^{-1}\quad\text{für alle $a\in G$}\] und damit \[a\ast b=b\ast a\quad\text{für alle $a\in G$}\quad.\] Also ist $G$ abelsch.
Die Umkehrung gilt nicht, denn es gibt abelsche Gruppen, in denen nicht jedes Element Ordnung 2 hat, wo also nicht $a\ast a=e$ für alle $a\in G$ gilt. Einfachstes Beispiel ist die abelsche Gruppe $(\Z,\,+,\,0)$. Hier gilt die Gleichung $a+a=0$ sogar für kein von Null verschiedenes Element.
Nächste Behauptung: Ist $G$ zyklisch, so ist $G$ abelsch.
Gelte also: $G$ ist zyklisch. Dann gibt es ein $g\in G$ mit $G=\{g^k \mid k\in\Z\}$. Seien $a,\,b\in G$. Dann gibt es $i,\,j\in \Z$ mit $a=g^i$ und $b=g^j$. Es folgt \[ a\ast b = g^i\ast g^j = g^{i+j} = g^{j+i} = g^j\ast g^i = b\ast a\quad, \] also ist $G$ abelsch.
Die Umkehrung gilt nicht, denn es gibt abelsche Gruppen, die nicht zyklisch sind. Einfachstes Beispiel ist die abelsche Gruppe $V_4$, die Kleinsche Vierergruppe. Bezeichnet man ihre Elemente mit $1$, $5$, $7$ und $11$, wobei $1$ das neutrale Element ist, so gilt die folgende Verknüpfungstafel, aus der man sofort abliest, dass die Gruppe abelsch ist:
Jedoch erkennt man auch, dass $V_4$ nicht zyklisch ist:
Nächste Behauptung: Ist $G$ endlich und $\abs G$ ungerade und gilt $a\ast b\ast a\ast b=b\ast a\ast b\ast a$ für alle $a,b\in G$, so ist $G$ abelsch.
Quelle dazu.
Es gelte: $G$ ist endlich und von ungerader Ordnung. Dann gibt es $k\in\N$ mit $\abs G=2k-1$. Seien $a,\,b\in G$. Dann gilt \[ \begin{array}{rcll} a\ast b &=& a\ast b\ast e & \text{} \\ &=& a\ast b\ast (a\ast b)^{2k-1} & \text{kleiner Satz von Fermat}\\ &=& (a\ast b)^{2k}\\ &=& (a\ast b\ast a\ast b)^k\\ &=& (b\ast a\ast b\ast a)^k & \text{Voraussetzung}\\ &=& (b\ast a)^{2k}\\ &=& b\ast a\ast(b\ast a)^{2k-1}\\ &=& b\ast a\ast e & \text{kleiner Satz von Fermat}\\ &=& b\ast a\quad, \end{array} \] und damit ist $G$ abelsch.
Der Beweis stammt auch von obiger Quelle.
Auch hier gilt die Umkehrung nicht: Eine abelsche Gruppe braucht nicht endlich zu sein. Einfachstes Beispiel ist die abelsche Gruppe $(\Z,\,+,\,0)$.
Es sei $(G,\,\ast,\,e)$ eine Gruppe. Wir behaupten: $G$ ist genau dann abelsch, wenn die Abbildung $G\to G$, $a\mapsto a\ast a$, ein Homomorphismus ist.
Gelte zunächst: $G\to G$, $a\mapsto a\ast a$, ist ein Homomorphismus.
Seien $a,b\in G$. Dann gilt $\varphi(a\ast b) = a\ast b\ast a\ast b$ und $\varphi(a)\ast \varphi(b) = a\ast a\ast b\ast b$, wegen der Homomorphieeigenschaft von $\varphi$ also \[ a\ast b\ast a\ast b = a\ast a\ast b\ast b\quad. \] Nun liefert die Multiplikation mit $a^{-1}$ von links \[ b\ast a\ast b = a\ast b\ast b\quad, \] und indem wir von rechts mit $b^{-1}$ multiplizieren, erhalten wir \[ b\ast a = a\ast b\quad. \] Also ist $G$ abelsch.
Gelte nun: $G$ ist abelsch.
Dann gilt für alle $a,\,b\in G$: \[b\ast a=a\ast b\quad,\]also \[b\ast a\ast b = a\ast b\ast b\quad,\] also \[a\ast b\ast a\ast b = a\ast a\ast b\ast b\] und damit \[\varphi(a\ast b) =\varphi(a)\ast \varphi(b)\quad,\]also ist $\varphi$ ein Homomorphismus.
Hier gelten also beide Richtungen.
Nächste Behauptung: Gilt $a\ast a=e$ für alle $a\in G$, so ist $G$ abelsch.
Nun: Gelte $a\ast a=e$ für alle $a\in G$. Dann folgt \[a=a^{-1}\quad\text{für alle $a\in G$}\quad,\] also \[a\ast b=(a\ast b)^{-1}\quad\text{für alle $a\in G$}\quad,\] also \[a\ast b=b^{-1}\ast a^{-1}\quad\text{für alle $a\in G$}\] und damit \[a\ast b=b\ast a\quad\text{für alle $a\in G$}\quad.\] Also ist $G$ abelsch.
Die Umkehrung gilt nicht, denn es gibt abelsche Gruppen, in denen nicht jedes Element Ordnung 2 hat, wo also nicht $a\ast a=e$ für alle $a\in G$ gilt. Einfachstes Beispiel ist die abelsche Gruppe $(\Z,\,+,\,0)$. Hier gilt die Gleichung $a+a=0$ sogar für kein von Null verschiedenes Element.
Nächste Behauptung: Ist $G$ zyklisch, so ist $G$ abelsch.
Gelte also: $G$ ist zyklisch. Dann gibt es ein $g\in G$ mit $G=\{g^k \mid k\in\Z\}$. Seien $a,\,b\in G$. Dann gibt es $i,\,j\in \Z$ mit $a=g^i$ und $b=g^j$. Es folgt \[ a\ast b = g^i\ast g^j = g^{i+j} = g^{j+i} = g^j\ast g^i = b\ast a\quad, \] also ist $G$ abelsch.
Die Umkehrung gilt nicht, denn es gibt abelsche Gruppen, die nicht zyklisch sind. Einfachstes Beispiel ist die abelsche Gruppe $V_4$, die Kleinsche Vierergruppe. Bezeichnet man ihre Elemente mit $1$, $5$, $7$ und $11$, wobei $1$ das neutrale Element ist, so gilt die folgende Verknüpfungstafel, aus der man sofort abliest, dass die Gruppe abelsch ist:
| $\ast$ | $\mathbf1$ | $\mathbf5$ | $\mathbf7$ | $\mathbf{11}$ |
|---|---|---|---|---|
| $\mathbf1$ | $1$ | $5$ | $7$ | $11$ |
| $\mathbf5$ | $5$ | $1$ | $11$ | $7$ |
| $\mathbf7$ | $7$ | $11$ | $1$ | $5$ |
| $\mathbf{11}$ | $11$ | $7$ | $5$ | $1$ |
Jedoch erkennt man auch, dass $V_4$ nicht zyklisch ist:
- Die von $1$ erzeugte zyklische Untergruppe ist $\{1\}$, also ungleich $G$.
- Die von $5$ erzeugte zyklische Untergruppe ist $\{1,\ 5\}$, also ungleich $G$.
- Die von $7$ erzeugte zyklische Untergruppe ist $\{1,\ 7\}$, also ungleich $G$.
- Die von $11$ erzeugte zyklische Untergruppe ist $\{1,\ 11\}$, also ungleich $G$.
Nächste Behauptung: Ist $G$ endlich und $\abs G$ ungerade und gilt $a\ast b\ast a\ast b=b\ast a\ast b\ast a$ für alle $a,b\in G$, so ist $G$ abelsch.
Quelle dazu.
Es gelte: $G$ ist endlich und von ungerader Ordnung. Dann gibt es $k\in\N$ mit $\abs G=2k-1$. Seien $a,\,b\in G$. Dann gilt \[ \begin{array}{rcll} a\ast b &=& a\ast b\ast e & \text{} \\ &=& a\ast b\ast (a\ast b)^{2k-1} & \text{kleiner Satz von Fermat}\\ &=& (a\ast b)^{2k}\\ &=& (a\ast b\ast a\ast b)^k\\ &=& (b\ast a\ast b\ast a)^k & \text{Voraussetzung}\\ &=& (b\ast a)^{2k}\\ &=& b\ast a\ast(b\ast a)^{2k-1}\\ &=& b\ast a\ast e & \text{kleiner Satz von Fermat}\\ &=& b\ast a\quad, \end{array} \] und damit ist $G$ abelsch.
Der Beweis stammt auch von obiger Quelle.
Auch hier gilt die Umkehrung nicht: Eine abelsche Gruppe braucht nicht endlich zu sein. Einfachstes Beispiel ist die abelsche Gruppe $(\Z,\,+,\,0)$.
Freitag, 22. August 2014
Für alle $n\in\N_{>0}$ gilt $\left(1+\frac{1}{n}\right)^n \leqslant \sum\limits_{k=0}^{n}\frac{1}{k!}$
Aus dem Tutorium:
Zunächst gilt die Ungleichung für $n=1$, denn beide Seiten sind dann gleich $2$.
Wir halten nun eine Kleinigkeit fest, die den weiteren Beweis verkürzt.
Für alle $k,n\in\N_{\geqslant2}$ gilt $n^k\geqslant n!$.
Beweis. Seien $k,n\in\N_{\geqslant2}$. Dann gilt \[ n^k = n\cdot n\cdot \ldots\cdot n \geqslant n\cdot(n-1)\cdot\ldots\quad, \] und wegen $n-1 < n$ und der Monotonie der Multiplikation ist die rechte Seite echt größer als die linke.
Es gilt für alle $n\in\N_{\geqslant 2}$ \[ \begin{array}{rcll} \left(1+\frac{1}{n}\right)^n &=& \left(\frac{1}{n}+1\right)^n & \text{Kommutativität der Addition in $\R$} \\[2mm] &=& \sum\limits_{k=0}^{n} \dbinom{n}{k}\cdot \left(\frac{1}{n}\right)^k\cdot 1^{n-k} & \text{Binomischer Lehrsatz}\\[2mm] &=& \sum\limits_{k=0}^{n} \dbinom{n}{k}\cdot \left(\frac{1}{n}\right)^k & \text{$1^m= 1$ für alle $m\in\N$}\\[2mm] &=& \sum\limits_{k=0}^{n} \dbinom{n}{k}\cdot \left(\frac{1}{n^k}\right) & \text{Bruchrechnen}\\[2mm] &=& \sum\limits_{k=0}^{n}\frac{n!}{k!\cdot (n-k)!} \cdot\frac{1}{n^k} & \text{Def. Binomialkoeffizient}\\[2mm] &\leqslant& \sum\limits_{k=0}^{n}\frac{n!}{k!\cdot (n-k)!} \cdot\frac{1}{n!} & \text{s.o.}\\[2mm] &=& \sum\limits_{k=0}^{n}\frac{1}{k!\cdot (n-k)!} &\text{$n!$ kürzen}\\[2mm] &\leqslant& \sum\limits_{k=0}^{n}\frac{1}{k!} &\text{$(n-k)!\geqslant 1$} \end{array} \] Da die Reihe $\sum\limits_{k=0}^{\infty}\frac{1}{k!}$ konvergiert, ist sie insbesondere beschränkt. Also ist auch die Folge $\left(\left(1+\frac{1}{n}\right)^n\right)_{n\in\N_{>0}}$ beschränkt. Gelingt der Nachweis, dass sie monoton wachsend ist (z.B. mittels der Bernoullischen Ungleichung, siehe Herbert Amann/Joachim Escher, Analysis 1, Birkhäuser Verlag, Basel u.a., 3. Auflage 2006, S. 178 f.), so ist damit gezeigt, dass die Folge $\left(\left(1+\frac{1}{n}\right)^n\right)_{n\in\N_{>0}}$ konvergiert.
Man zeige, dass für alle $n\in\N_{>0}$ gilt \[ \left(1+\frac{1}{n}\right)^n \leqslant \sum\limits_{k=0}^{n}\frac{1}{k!}\quad. \]Quelle der Aufgabe
Zunächst gilt die Ungleichung für $n=1$, denn beide Seiten sind dann gleich $2$.
Wir halten nun eine Kleinigkeit fest, die den weiteren Beweis verkürzt.
Für alle $k,n\in\N_{\geqslant2}$ gilt $n^k\geqslant n!$.
Beweis. Seien $k,n\in\N_{\geqslant2}$. Dann gilt \[ n^k = n\cdot n\cdot \ldots\cdot n \geqslant n\cdot(n-1)\cdot\ldots\quad, \] und wegen $n-1 < n$ und der Monotonie der Multiplikation ist die rechte Seite echt größer als die linke.
Es gilt für alle $n\in\N_{\geqslant 2}$ \[ \begin{array}{rcll} \left(1+\frac{1}{n}\right)^n &=& \left(\frac{1}{n}+1\right)^n & \text{Kommutativität der Addition in $\R$} \\[2mm] &=& \sum\limits_{k=0}^{n} \dbinom{n}{k}\cdot \left(\frac{1}{n}\right)^k\cdot 1^{n-k} & \text{Binomischer Lehrsatz}\\[2mm] &=& \sum\limits_{k=0}^{n} \dbinom{n}{k}\cdot \left(\frac{1}{n}\right)^k & \text{$1^m= 1$ für alle $m\in\N$}\\[2mm] &=& \sum\limits_{k=0}^{n} \dbinom{n}{k}\cdot \left(\frac{1}{n^k}\right) & \text{Bruchrechnen}\\[2mm] &=& \sum\limits_{k=0}^{n}\frac{n!}{k!\cdot (n-k)!} \cdot\frac{1}{n^k} & \text{Def. Binomialkoeffizient}\\[2mm] &\leqslant& \sum\limits_{k=0}^{n}\frac{n!}{k!\cdot (n-k)!} \cdot\frac{1}{n!} & \text{s.o.}\\[2mm] &=& \sum\limits_{k=0}^{n}\frac{1}{k!\cdot (n-k)!} &\text{$n!$ kürzen}\\[2mm] &\leqslant& \sum\limits_{k=0}^{n}\frac{1}{k!} &\text{$(n-k)!\geqslant 1$} \end{array} \] Da die Reihe $\sum\limits_{k=0}^{\infty}\frac{1}{k!}$ konvergiert, ist sie insbesondere beschränkt. Also ist auch die Folge $\left(\left(1+\frac{1}{n}\right)^n\right)_{n\in\N_{>0}}$ beschränkt. Gelingt der Nachweis, dass sie monoton wachsend ist (z.B. mittels der Bernoullischen Ungleichung, siehe Herbert Amann/Joachim Escher, Analysis 1, Birkhäuser Verlag, Basel u.a., 3. Auflage 2006, S. 178 f.), so ist damit gezeigt, dass die Folge $\left(\left(1+\frac{1}{n}\right)^n\right)_{n\in\N_{>0}}$ konvergiert.
Dienstag, 1. Oktober 2013
Sind $a,\,b,\,c$ reelle Zahlen mit $a+b+c=1$, so folgt $a^2+b^2+c^2\geq\frac{1}{3}$
Woher kommt diese Aussage (und die Ideen zum Beweis)? Von hier.
Um sie zu zeigen, braucht man keine trinomischen Formeln oder sonstiges schweres Geschütz; die binomischen Formeln (besonders die zweite) sind aber schon ganz hilfreich.
Es ist $\left(\frac{1}{3}\right)^2 = \frac{1}{9}$ und $\frac{1}{9} + \frac{1}{9} + \frac{1}{9} = \frac{1}{3}$. Deshalb betrachten wir anstatt der zu zeigenden Ungleichung
\[
a^2+b^2+c^2-\frac{1}{3}\geq 0
\] einfach mal die folgende Ungleichung:
\[
\left(a-\frac{1}{3}\right)^2 + \left(b-\frac{1}{3}\right)^2 + \left(c-\frac{1}{3}\right)^2\geq 0\quad,\qquad(\ast)
\] denn wenn wir in jedem Summanden (unter anderem) ein Drittel quadrieren, so kommen (unter anderem) drei Neuntel, also ein Drittel, heraus. Vielleicht hebt sich da später schön was weg?
Da das Quadrat einer reellen Zahl stets nichtnegativ ist, gilt die Ungleichung $(\ast)$. Wenn wir nun ausmultiplizieren, so erhalten wir
\[
a^2-\frac{2}{3}a + \frac{1}{9} + b^2-\frac{2}{3}b + \frac{1}{9} + c^2-\frac{2}{3}c + \frac{1}{9}\geq 0\quad,
\] was wir zu
\[
a^2 + b^2+c^2 - \frac{2}{3}\left(a+b+c\right) + \frac{1}{9} + \frac{1}{9} + \frac{1}{9}\geq 0
\] umsortieren können. Einerseits ist, wie bereits oben bemerkt, $\frac{1}{9} + \frac{1}{9} + \frac{1}{9} = \frac{1}{3}$, andererseits ist nach Voraussetzung $a+b+c = 1$, so dass sich
\[
a^2 + b^2+c^2 + -\frac{2}{3} + \frac{1}{3} \geq 0
\] ergibt; die Behauptung folgt.
Das war der „analytische” Beweis; es gibt auch einen „linear-algebraischen”.
Wir erkennen, dass auf der linken Seite der Ungleichung die rellen Zahlen $a,\,b,\,c$ summiert werden und auf der rechten ihre Quadrate. Das erinnert doch ein wenig an das Standardskalarprodukt des Vektors $(a,\,b,\,c)$ mit sich selbst?
Betrachten wir im $\mathbb R^3$ die Vektoren $u:=(1,\,1,\,1)$ und $v:=(a,\,b,\,c)$. Dann gilt
\[
\begin{array}{rcl}
\langle u,\,v\rangle &=& 1\cdot a+1\cdot b+1\cdot c = a+b+c\quad,\\
\langle u,\,u\rangle &=& 1^2+1^2+1^2 = 3\quad,\\
\langle v,\,v\rangle &=& a^2+b^2+c^2
\end{array}
\] also \[\langle u,\,u\rangle\cdot\langle v,\,v\rangle = 3\cdot\left(a^2+b^2+c^2\right)\quad.\] Beachten wir nun die Cauchy-Schwarzsche Ungleichung,
\[
\langle u,\,v\rangle\leq \langle u,\,u\rangle\cdot\langle v,\,v\rangle\quad,
\] so folgt
\[
a+b+c \leq 3\cdot\left(a^2+b^2+c^2\right)\quad,
\]
und wegen $a+b+c=1$ impliziert dies $\frac{1}{3}\leq a^2+b^2+c^2$, also die Behauptung.
Um sie zu zeigen, braucht man keine trinomischen Formeln oder sonstiges schweres Geschütz; die binomischen Formeln (besonders die zweite) sind aber schon ganz hilfreich.
Es ist $\left(\frac{1}{3}\right)^2 = \frac{1}{9}$ und $\frac{1}{9} + \frac{1}{9} + \frac{1}{9} = \frac{1}{3}$. Deshalb betrachten wir anstatt der zu zeigenden Ungleichung
\[
a^2+b^2+c^2-\frac{1}{3}\geq 0
\] einfach mal die folgende Ungleichung:
\[
\left(a-\frac{1}{3}\right)^2 + \left(b-\frac{1}{3}\right)^2 + \left(c-\frac{1}{3}\right)^2\geq 0\quad,\qquad(\ast)
\] denn wenn wir in jedem Summanden (unter anderem) ein Drittel quadrieren, so kommen (unter anderem) drei Neuntel, also ein Drittel, heraus. Vielleicht hebt sich da später schön was weg?
Da das Quadrat einer reellen Zahl stets nichtnegativ ist, gilt die Ungleichung $(\ast)$. Wenn wir nun ausmultiplizieren, so erhalten wir
\[
a^2-\frac{2}{3}a + \frac{1}{9} + b^2-\frac{2}{3}b + \frac{1}{9} + c^2-\frac{2}{3}c + \frac{1}{9}\geq 0\quad,
\] was wir zu
\[
a^2 + b^2+c^2 - \frac{2}{3}\left(a+b+c\right) + \frac{1}{9} + \frac{1}{9} + \frac{1}{9}\geq 0
\] umsortieren können. Einerseits ist, wie bereits oben bemerkt, $\frac{1}{9} + \frac{1}{9} + \frac{1}{9} = \frac{1}{3}$, andererseits ist nach Voraussetzung $a+b+c = 1$, so dass sich
\[
a^2 + b^2+c^2 + -\frac{2}{3} + \frac{1}{3} \geq 0
\] ergibt; die Behauptung folgt.
Das war der „analytische” Beweis; es gibt auch einen „linear-algebraischen”.
Wir erkennen, dass auf der linken Seite der Ungleichung die rellen Zahlen $a,\,b,\,c$ summiert werden und auf der rechten ihre Quadrate. Das erinnert doch ein wenig an das Standardskalarprodukt des Vektors $(a,\,b,\,c)$ mit sich selbst?
Betrachten wir im $\mathbb R^3$ die Vektoren $u:=(1,\,1,\,1)$ und $v:=(a,\,b,\,c)$. Dann gilt
\[
\begin{array}{rcl}
\langle u,\,v\rangle &=& 1\cdot a+1\cdot b+1\cdot c = a+b+c\quad,\\
\langle u,\,u\rangle &=& 1^2+1^2+1^2 = 3\quad,\\
\langle v,\,v\rangle &=& a^2+b^2+c^2
\end{array}
\] also \[\langle u,\,u\rangle\cdot\langle v,\,v\rangle = 3\cdot\left(a^2+b^2+c^2\right)\quad.\] Beachten wir nun die Cauchy-Schwarzsche Ungleichung,
\[
\langle u,\,v\rangle\leq \langle u,\,u\rangle\cdot\langle v,\,v\rangle\quad,
\] so folgt
\[
a+b+c \leq 3\cdot\left(a^2+b^2+c^2\right)\quad,
\]
und wegen $a+b+c=1$ impliziert dies $\frac{1}{3}\leq a^2+b^2+c^2$, also die Behauptung.
Samstag, 28. September 2013
Sind $1$ und $\sqrt3$ über $\mathbb Q\left(\sqrt2\right)$ linear unabhängig?
$\newcommand{\Q}{\mathbb{Q}}
\newcommand{\set}[1]{\left\{{#1}\right\}}
\newcommand{\setwhere}[2]{\left\{{#1}\hspace{2pt}\middle|\hspace{2pt}{#2}\right\}}
\newcommand{\qwzwei}{\Q\left(\sqrt2\right)}
\newcommand{\nullqwzwei}{0_\Q+0_\Q\cdot\sqrt2}$Im Buch „Analysis I“ von Herbert Amann und Joachim Escher findet man die Frage, ob $1$ und $\sqrt3$ über dem Körper $\Q\left(\sqrt2\right)$ linear unabhängig sind. Aus dem Bauch heraus habe ich vermutet, dass das so ist, aber es kam dann doch das Gegenteil heraus.
Es ist $\qwzwei:=\setwhere{a+b\cdot\sqrt2}{a,\ b\in\Q}$.
Definitionsgemäß sind $1$ und $\sqrt3$ genau dann linear unabhängig über $\qwzwei$, falls für alle $\alpha,\ \beta\in\qwzwei$ gilt:
\[
\alpha \cdot 1 + \beta \cdot\sqrt3 = \nullqwzwei \implies \alpha=\beta=\nullqwzwei\quad.
\] Seien $\alpha,\ \beta\in\qwzwei$. Dann gibt es $a,\ b,\ c,\ d\in\Q$ mit
\[
\alpha = a+b\cdot\sqrt2\ ,\qquad\beta=c+d\cdot\sqrt2\quad.
\] Es folgt
\[
\begin{array}{rcl}
\alpha \cdot 1 + \beta \cdot\sqrt3 &=& \left(a+b\cdot\sqrt2\right)\cdot 1 + \left(c+d\cdot\sqrt2\right)\cdot\sqrt3\\
&=& a+b\cdot\sqrt2 + c\cdot\sqrt3 + d\cdot\sqrt2\cdot\sqrt3\quad.
\end{array}
\]
Es gelte $\alpha \cdot 1 + \beta \cdot\sqrt3 = \nullqwzwei$. Dann folgt
\[
a+b\cdot\sqrt2 + c\cdot\sqrt3 + d\cdot\sqrt2\cdot\sqrt3 = \nullqwzwei\quad,
\] also erhalten wir nach Multiplikation mit $\sqrt2\cdot\sqrt3$ Folgendes
\[
a\cdot\sqrt2\cdot\sqrt3+2\cdot b\cdot \sqrt3+6\cdot d+3\cdot c \cdot\sqrt2 = \nullqwzwei\quad,
\] und nach etwas Umsortieren und Ausklammern von $\sqrt2$ steht da
\[
\left(2b\sqrt3+6d\right) + (a\sqrt3+3c)\sqrt2= \nullqwzwei\quad.
\] Jetzt können wir ausnutzen, dass $1$ und $\sqrt2$ über $\Q$ linear unabhängig sind, erhalten also
\[
2b\sqrt3+6d = 0_\Q\qquad\text{und}\qquad a\sqrt3+3c=0_\Q\quad.
\] Addieren wir diese beiden Gleichungen, ergibt sich
\[
\left(a+2b\right)\sqrt3 +\left(6d+3c\right) = 0_\Q\quad,
\] und da die rechte Seite der Gleichung eine rationale Zahl ist, ist auch die linke Seite rational. Doch da $1$ und $\sqrt3$ über $\Q$ ebenfalls linear unabhängig sind, folgt $a+2b=0$ und $6d+3c=0$, d.h. es folgt NICHT $a=b=0$ und $c=d=0$.
Also sind $1$ und $\sqrt3$ über dem Körper $\qwzwei$ linear abhängig.
\newcommand{\set}[1]{\left\{{#1}\right\}}
\newcommand{\setwhere}[2]{\left\{{#1}\hspace{2pt}\middle|\hspace{2pt}{#2}\right\}}
\newcommand{\qwzwei}{\Q\left(\sqrt2\right)}
\newcommand{\nullqwzwei}{0_\Q+0_\Q\cdot\sqrt2}$Im Buch „Analysis I“ von Herbert Amann und Joachim Escher findet man die Frage, ob $1$ und $\sqrt3$ über dem Körper $\Q\left(\sqrt2\right)$ linear unabhängig sind. Aus dem Bauch heraus habe ich vermutet, dass das so ist, aber es kam dann doch das Gegenteil heraus.
Es ist $\qwzwei:=\setwhere{a+b\cdot\sqrt2}{a,\ b\in\Q}$.
Definitionsgemäß sind $1$ und $\sqrt3$ genau dann linear unabhängig über $\qwzwei$, falls für alle $\alpha,\ \beta\in\qwzwei$ gilt:
\[
\alpha \cdot 1 + \beta \cdot\sqrt3 = \nullqwzwei \implies \alpha=\beta=\nullqwzwei\quad.
\] Seien $\alpha,\ \beta\in\qwzwei$. Dann gibt es $a,\ b,\ c,\ d\in\Q$ mit
\[
\alpha = a+b\cdot\sqrt2\ ,\qquad\beta=c+d\cdot\sqrt2\quad.
\] Es folgt
\[
\begin{array}{rcl}
\alpha \cdot 1 + \beta \cdot\sqrt3 &=& \left(a+b\cdot\sqrt2\right)\cdot 1 + \left(c+d\cdot\sqrt2\right)\cdot\sqrt3\\
&=& a+b\cdot\sqrt2 + c\cdot\sqrt3 + d\cdot\sqrt2\cdot\sqrt3\quad.
\end{array}
\]
Es gelte $\alpha \cdot 1 + \beta \cdot\sqrt3 = \nullqwzwei$. Dann folgt
\[
a+b\cdot\sqrt2 + c\cdot\sqrt3 + d\cdot\sqrt2\cdot\sqrt3 = \nullqwzwei\quad,
\] also erhalten wir nach Multiplikation mit $\sqrt2\cdot\sqrt3$ Folgendes
\[
a\cdot\sqrt2\cdot\sqrt3+2\cdot b\cdot \sqrt3+6\cdot d+3\cdot c \cdot\sqrt2 = \nullqwzwei\quad,
\] und nach etwas Umsortieren und Ausklammern von $\sqrt2$ steht da
\[
\left(2b\sqrt3+6d\right) + (a\sqrt3+3c)\sqrt2= \nullqwzwei\quad.
\] Jetzt können wir ausnutzen, dass $1$ und $\sqrt2$ über $\Q$ linear unabhängig sind, erhalten also
\[
2b\sqrt3+6d = 0_\Q\qquad\text{und}\qquad a\sqrt3+3c=0_\Q\quad.
\] Addieren wir diese beiden Gleichungen, ergibt sich
\[
\left(a+2b\right)\sqrt3 +\left(6d+3c\right) = 0_\Q\quad,
\] und da die rechte Seite der Gleichung eine rationale Zahl ist, ist auch die linke Seite rational. Doch da $1$ und $\sqrt3$ über $\Q$ ebenfalls linear unabhängig sind, folgt $a+2b=0$ und $6d+3c=0$, d.h. es folgt NICHT $a=b=0$ und $c=d=0$.
Also sind $1$ und $\sqrt3$ über dem Körper $\qwzwei$ linear abhängig.
Freitag, 13. September 2013
Teilbarkeit und Äquivalenzrelationen
Wir definieren die Relation $R\subseteq \mathbb Z \times \mathbb Z$ durch
\[
\ \ \forall\mspace{2mu} x,\,y\in\mathbb Z\quad\left( xRy \iff 7\mspace{2mu}\mid\mspace{2mu} 2x+5y\right)
\] und vermuten, dass es sich um eine Äquivalenzrelation handelt.
Reflexivität: Sei $x\in\mathbb Z$. Dann gilt $7\mspace{2mu}\mid\mspace{2mu} 7x = 5x+2x$, also $xRx$. Damit ist $R$ reflexiv.
Symmetrie: Seien $x,\,y\in\mathbb Z$, und es gelte $xRy$, d.h. $7\mspace{2mu}\mid\mspace{2mu} 2x+5y$. Klarerweise gilt $7\mspace{2mu}\mid\mspace{2mu} 7x+7y$, und da mit zwei durch $7$ teilbaren Zahlen auch ihre Differenz durch $7$ teilbar ist, folgt
\[
7 \mspace{2mu}\mid\mspace{2mu} 7x+7y-(2x+5y) = 5x+2y\quad,
\] also $yRx$. Damit ist $R$ symmetrisch.
Transitivität: Seien $x,\,y,\,z\in\mathbb Z$, und es gelte $xRy$ und $yRz$, d.h. $7\mspace{2mu}\mid\mspace{2mu} 2x+5y$ und $7\mspace{2mu}\mid\mspace{2mu} 2y+5z$. Dann folgt wegen $7\mspace{2mu}\mid\mspace{2mu} 7y$:
\[
7\mspace{2mu}\mid\mspace{2mu} 2x+5y+2y+5z-7y=2x+5z\quad,
\] und damit ist $R$ transitiv.
Also ist $R$ tatsächlich eine Äquivalenzrelation.
\[
\ \ \forall\mspace{2mu} x,\,y\in\mathbb Z\quad\left( xRy \iff 7\mspace{2mu}\mid\mspace{2mu} 2x+5y\right)
\] und vermuten, dass es sich um eine Äquivalenzrelation handelt.
Reflexivität: Sei $x\in\mathbb Z$. Dann gilt $7\mspace{2mu}\mid\mspace{2mu} 7x = 5x+2x$, also $xRx$. Damit ist $R$ reflexiv.
Symmetrie: Seien $x,\,y\in\mathbb Z$, und es gelte $xRy$, d.h. $7\mspace{2mu}\mid\mspace{2mu} 2x+5y$. Klarerweise gilt $7\mspace{2mu}\mid\mspace{2mu} 7x+7y$, und da mit zwei durch $7$ teilbaren Zahlen auch ihre Differenz durch $7$ teilbar ist, folgt
\[
7 \mspace{2mu}\mid\mspace{2mu} 7x+7y-(2x+5y) = 5x+2y\quad,
\] also $yRx$. Damit ist $R$ symmetrisch.
Transitivität: Seien $x,\,y,\,z\in\mathbb Z$, und es gelte $xRy$ und $yRz$, d.h. $7\mspace{2mu}\mid\mspace{2mu} 2x+5y$ und $7\mspace{2mu}\mid\mspace{2mu} 2y+5z$. Dann folgt wegen $7\mspace{2mu}\mid\mspace{2mu} 7y$:
\[
7\mspace{2mu}\mid\mspace{2mu} 2x+5y+2y+5z-7y=2x+5z\quad,
\] und damit ist $R$ transitiv.
Also ist $R$ tatsächlich eine Äquivalenzrelation.
Freitag, 9. August 2013
Die Zahlen $5^{98}+3$ und $5^{99}+1$ sind beide durch $14$ teilbar
Für den Taschenrechner sind sie zu groß, aber für den kleinen Fermatschen Satz nicht.
Es sind beide Zahlen gerade; damit brauchen wir nur noch die Teilbarkeit beider Zahlen durch $7$ zu zeigen.
Zunächst zur kleineren Zahl. Nach dem kleinen Fermatschen Satz gilt $5^6\equiv 1 \pmod 7$, also folgt
\[
5^{98} \equiv 5^{16\cdot 6+2} \equiv 5^2 \equiv 25 \equiv 4\pmod 7\quad{,}
\]
damit $5^{98}+3\equiv 0\pmod 7$, d.h. $7\mid 5^{98}+3$.
Die größere Zahl könnte man auf dieselbe Weise erschlagen, aber es geht auch schneller:
Aus der Beziehung $7\mid 5^{98}+3$ folgt $7\mid 5\cdot \left(5^{98}+3\right) = 5^{99}+15$, und das führt unmittelbar zu $7\mid 5^{99}+1$, denn $14=5^{99}+15-\left(5^{99}+1\right)$ ist klarerweise durch $7$ teilbar.
Sowas geht natürlich auch mit größeren Zahlen, z.B. „Die Zahl $5^{4^7}-5^{4^6}$ ist durch 7 teilbar“. Solche Potenztürme kann man aber auch auf ganz andere Art knacken. Dazu mehr in einem späteren Post.
Es sind beide Zahlen gerade; damit brauchen wir nur noch die Teilbarkeit beider Zahlen durch $7$ zu zeigen.
Zunächst zur kleineren Zahl. Nach dem kleinen Fermatschen Satz gilt $5^6\equiv 1 \pmod 7$, also folgt
\[
5^{98} \equiv 5^{16\cdot 6+2} \equiv 5^2 \equiv 25 \equiv 4\pmod 7\quad{,}
\]
damit $5^{98}+3\equiv 0\pmod 7$, d.h. $7\mid 5^{98}+3$.
Die größere Zahl könnte man auf dieselbe Weise erschlagen, aber es geht auch schneller:
Aus der Beziehung $7\mid 5^{98}+3$ folgt $7\mid 5\cdot \left(5^{98}+3\right) = 5^{99}+15$, und das führt unmittelbar zu $7\mid 5^{99}+1$, denn $14=5^{99}+15-\left(5^{99}+1\right)$ ist klarerweise durch $7$ teilbar.
Sowas geht natürlich auch mit größeren Zahlen, z.B. „Die Zahl $5^{4^7}-5^{4^6}$ ist durch 7 teilbar“. Solche Potenztürme kann man aber auch auf ganz andere Art knacken. Dazu mehr in einem späteren Post.
Donnerstag, 8. August 2013
Es gibt unendlich viele Primzahlen der Form $4k+3$
$\newcommand{\set}[1]{\left\{{#1}\right\}}$Unter einer Primzahl verstehen wir eine natürliche Zahl, die genau zwei natürliche Zahlen als Teiler hat.
Dass es unendlich viele Primzahlen gibt, ist spätestens seit Euklid bekannt. Sein Beweis, dessen Idee wir verwenden werden, um die Aussage im Titel zu zeigen, lautet (in moderner Sprache):
\[
N:=(-1)+4\cdot\displaystyle\prod_{i=1}^{n} p_i\quad{,}
\] die offenbar ebenfalls bei Division durch 4 den Rest 3 lässt, also insbesondere ungerade ist. Damit ist jeder Teiler von $N$ entweder von der Form $4k+1$ oder von der Form $4k+3$. Also ist insbesondere jeder Primteiler von $N$ von einer der beiden Formen.
Nehmen wir an, jeder Primteiler von $N$ hätte die Form $4k+1$. Dann nehmen wir uns doch mal zwei davon her (es muss mindestens zwei (mit Vielfachheit gezählt) geben, denn gäbe es nur einen, dann wäre er gleich $N$, und $N$ wäre dann entgegen Konstruktion nicht von der Form $4k+3$), nennen wir sie $4a+1$ und $4b+1$, und berechnen ihr Produkt:
\[
\begin{array}{rcl}
(4a+1)\cdot(4b+1) &=& 4a\cdot4b+4a+4b+1\\[2mm]
&=& 16ab+4(a+b)+1\\[2mm]
&=& 4\cdot4ab+4(a+b)+1\\[2mm]
&=& 4\cdot(4ab+a+b) + 1
\end{array}
\] Wir sehen also, dass ihr Produkt wieder von der Form $4k+1$ ist. Per Induktion folgt sofort, dass dann auch $N$ von der Form $4k+1$ wäre, was erneut einen Widerspruch zur Konstruktion von $N$ darstellen würde. Also hat $N$ mindestens einen Primteiler $t$ der Form $4k+3$.
Wäre $t$ eine der Zahlen $p_i$, so folgte
\[
t \mid (-1) + 4\cdot\prod_{i=1}^{n} p_i - 4\cdot\prod_{i=1}^{n} p_i = -1\quad{,}
\] also $t\mid -1$ und damit auch $t\mid 1$, was nicht möglich ist. Also ist $t$ von allen Primzahlen ${p_1,\ p_2,\,\ldots,\ p_n}$ verschieden und damit eine weitere Primzahl der Form $4k+3$. Also gibt es unendlich viele Primzahlen dieser Form.
Dass es unendlich viele Primzahlen gibt, ist spätestens seit Euklid bekannt. Sein Beweis, dessen Idee wir verwenden werden, um die Aussage im Titel zu zeigen, lautet (in moderner Sprache):
Die Menge der Primzahlen ist nicht leer, denn $2$ ist offenbar eine Primzahl. Wenn wir annehmen, dass es nur endlich viele, sagen wir $n\in\mathbb N_{\geq 1}$, Primzahlen gibt, die mit ${p_1,\ p_2,\,\ldots,\ p_n}$ bezeichnet seien, dann können wir alle diese Zahlen miteinander multiplizieren und $1$ addieren, d.h. die Zahl $N:=1+\displaystyle\prod_{i=1}^{n} p_i$ betrachten. Diese ist durch keine der Primzahlen $p_i$ teilbar, denn aus $p_i \mid 1+\displaystyle\prod_{i=1}^{n} p_i$ folgt sofort $p_i\mid 1$, ein offensichtlicher Widerspruch.Nun zum Beweis der eigentlichen Aussage. Zunächst ist die Primzahl $3$ von der verlangten Form. Nun sei $n\in\mathbb N$, und es seien ${p_1,\ p_2,\,\ldots,\ p_n}$ Primzahlen, die bei Division durch 4 alle den Rest 3 lassen. Jetzt betrachten wir die Zahl
Da $N$ eine natürliche Zahl größer als 1 ist, besitzt $N$ einen Primteiler (der kleinste Teiler $t$ von $N$, der größer als 1 ist, ist etwa ein solcher). Jedoch kann $t$ nicht in der Menge ${\set{p_1,\ p_2,\,\ldots,\ p_n}}$ enthalten sein, wie wir eben gesehen haben. Damit ist $t$ eine weitere Primzahl.
(Der Leser überlege sich, ob der Beweis gültig bleibt, wenn anfangs die Existenz wenigstens einer Primzahl nicht sichergestellt wird!)
\[
N:=(-1)+4\cdot\displaystyle\prod_{i=1}^{n} p_i\quad{,}
\] die offenbar ebenfalls bei Division durch 4 den Rest 3 lässt, also insbesondere ungerade ist. Damit ist jeder Teiler von $N$ entweder von der Form $4k+1$ oder von der Form $4k+3$. Also ist insbesondere jeder Primteiler von $N$ von einer der beiden Formen.
Nehmen wir an, jeder Primteiler von $N$ hätte die Form $4k+1$. Dann nehmen wir uns doch mal zwei davon her (es muss mindestens zwei (mit Vielfachheit gezählt) geben, denn gäbe es nur einen, dann wäre er gleich $N$, und $N$ wäre dann entgegen Konstruktion nicht von der Form $4k+3$), nennen wir sie $4a+1$ und $4b+1$, und berechnen ihr Produkt:
\[
\begin{array}{rcl}
(4a+1)\cdot(4b+1) &=& 4a\cdot4b+4a+4b+1\\[2mm]
&=& 16ab+4(a+b)+1\\[2mm]
&=& 4\cdot4ab+4(a+b)+1\\[2mm]
&=& 4\cdot(4ab+a+b) + 1
\end{array}
\] Wir sehen also, dass ihr Produkt wieder von der Form $4k+1$ ist. Per Induktion folgt sofort, dass dann auch $N$ von der Form $4k+1$ wäre, was erneut einen Widerspruch zur Konstruktion von $N$ darstellen würde. Also hat $N$ mindestens einen Primteiler $t$ der Form $4k+3$.
Wäre $t$ eine der Zahlen $p_i$, so folgte
\[
t \mid (-1) + 4\cdot\prod_{i=1}^{n} p_i - 4\cdot\prod_{i=1}^{n} p_i = -1\quad{,}
\] also $t\mid -1$ und damit auch $t\mid 1$, was nicht möglich ist. Also ist $t$ von allen Primzahlen ${p_1,\ p_2,\,\ldots,\ p_n}$ verschieden und damit eine weitere Primzahl der Form $4k+3$. Also gibt es unendlich viele Primzahlen dieser Form.
Sonntag, 4. August 2013
$\displaystyle\frac{1+\sqrt{5}}{2}$, zum Ersten
Heute mal etwas Analysis (von hier).
$\text{Man zeige, dass die Folge $(a_n)_{n\in\mathbb N}$, definiert durch}$
\[
a_{n}:= \begin{cases}
1 & , \quad n = 1\\
\sqrt{\vphantom{1+a_n^2}1+a_{n-1}}& , \quad n > 1
\end{cases} \quad {,}
\] $\text{konvergiert und gebe ihren Grenzwert an.}$
Zuerst zeigen wir die Konvergenz. Dazu benutzen wir den Satz
„Jede monoton wachsende, nach oben beschränkte Folge reller Zahlen konvergiert.“
Die Folge $(a_n)$ ist (sogar streng) monoton wachsend, denn erstens gilt
\[
a_2 = \sqrt{\vphantom{1+a_n^2}1+a_1} = \sqrt{\vphantom{1+a_n^2}2} > 1 = a_1\quad\text{.}
\] und zweitens gilt für alle ${n\in{\mathbb N}_{\geq2}}$ mit ${a_n > a_{n-1}}$:
\[
a_{n+1} = \sqrt{\vphantom{1+a_n^2}1+a_n} > \sqrt{\vphantom{1+a_n^2}1+a_{n-1}} = a_n\quad{;}
\] hierbei haben wir die Induktionsvoraussetzung und die strenge Isotonie der Wurzelfunktion verwendet.
Außerdem ist die Folge $(a_n)$ durch 2 nach oben beschränkt: Es ist ${a_1=1<2}$, und ist ${n\in\mathbb N}$ mit ${a_n <2}$, so folgt
\[
a_{n+1} = \sqrt{\vphantom{1+a_n^2}1+a_n} < \sqrt{\vphantom{1+a_n^2}1+2} = \sqrt{\vphantom{1+a_n^2}3} < 2\quad.
\] Hier wurde wieder die Induktionsvoraussetzung und die strenge Isotonie der Wurzelfunktion verwendet.
Damit ist die Folge $(a_n)$ monoton wachsend und nach oben beschränkt, also existiert ${\displaystyle\lim_{n\to\infty}a_n}$.
Wie bestimmt man nun den Grenzwert der Folge, nennen wir ihn $x$?
Dazu halten wir zunächst fest, dass gilt
\[
\lim_{n\to\infty}a_n = \lim_{n\to\infty}a_{n+1}\quad{.}
\] (Wie sähe ein Beweis dafür aus?)
Jedenfalls erhalten wir damit
\[
\lim_{n\to\infty}a_n = \lim_{n\to\infty}\sqrt{\vphantom{1+a_n^2}1+a_n}\quad{.}
\] Wenn wir jetzt nacheinander die Stetigkeit der Wurzelfunktion auf ${\mathbb R_{>0}}$ und die Stetigkeit der Addition auf ${\mathbb R \times \mathbb R}$ ausnutzen, so sehen wir, dass gilt
\[
x = \lim_{n\to\infty}a_n = \lim_{n\to\infty}\sqrt{\vphantom{\big(}1+a_n} = \sqrt{\vphantom{\big(}\lim_{n\to\infty}1+a_n} = \sqrt{\vphantom{\big(}1+\lim_{n\to\infty}a_n} = \sqrt{\vphantom{\big(}1+x}\quad{,}
\] d.h. wir haben nur noch die quadratische Gleichung $x^2=1+x$ zu lösen. Sie hat in $\mathbb R$ genau zwei Lösungen, von denen eine positiv und eine negativ ist. Die negative Lösung ist aber uninteressant: es gilt ${a_1>0}$, und die Folge ist streng monoton wachsend – also sind auch alle weiteren Folgenglieder größer als 0, und es folgt, dass ${\displaystyle\lim_{n\to\infty}a_n} \geqslant 0$ sein muss.
Damit ist der Grenzwert gefunden; sein Wert ist… ja, genau: $\displaystyle\frac{1+\sqrt{5}}{2}$.
Interessant ist noch, dass der Grenzwert ein Fixpunkt der der Folge zugrundeliegenden Abbildung
\[
f\colon \mathbb R_{>0}\to\mathbb R_{>0}\ , \quad x\mapsto\sqrt{\vphantom{1+a_n^2}1+x}\quad{,}
\] ist:
\[
\begin{array}{rclcl}
f\left(\frac{1+\sqrt{5}}{2}\right)
&=&
\sqrt{1+\frac{1+\sqrt{5}}{2}}
&=&
\sqrt{\frac{3+\sqrt{5}}{2}}
\\[5mm]
&=&
\sqrt{\frac32+\frac{\sqrt5}{2}}
&=&
\sqrt{\frac64+\frac{\sqrt5}{2}}
\\[5mm]
&=&
\sqrt{\frac14+\frac{\sqrt5}{2}+\frac54}
&=&
\sqrt{\left(\frac12\right)^2 + 2\cdot\frac12\cdot\frac{\sqrt5}{2} + \left(\frac{\sqrt5}{2}\right)^2}
\\[5mm]
&=&
\sqrt{\left(\frac12+\frac{\sqrt5}{2}\right)^2}
&=& \displaystyle\frac12+\frac{\sqrt5}{2}
\\[5mm]
&=&
\displaystyle\frac{1+\sqrt5}{2}
\end{array}
\] Wann ein Fixpunkt einer der Folge zungrundeliegenden Funktion ein Grenzwert der Folge ist, klärt der Banachsche Fixpunktsatz.
$\text{Man zeige, dass die Folge $(a_n)_{n\in\mathbb N}$, definiert durch}$
\[
a_{n}:= \begin{cases}
1 & , \quad n = 1\\
\sqrt{\vphantom{1+a_n^2}1+a_{n-1}}& , \quad n > 1
\end{cases} \quad {,}
\] $\text{konvergiert und gebe ihren Grenzwert an.}$
Zuerst zeigen wir die Konvergenz. Dazu benutzen wir den Satz
„Jede monoton wachsende, nach oben beschränkte Folge reller Zahlen konvergiert.“
Die Folge $(a_n)$ ist (sogar streng) monoton wachsend, denn erstens gilt
\[
a_2 = \sqrt{\vphantom{1+a_n^2}1+a_1} = \sqrt{\vphantom{1+a_n^2}2} > 1 = a_1\quad\text{.}
\] und zweitens gilt für alle ${n\in{\mathbb N}_{\geq2}}$ mit ${a_n > a_{n-1}}$:
\[
a_{n+1} = \sqrt{\vphantom{1+a_n^2}1+a_n} > \sqrt{\vphantom{1+a_n^2}1+a_{n-1}} = a_n\quad{;}
\] hierbei haben wir die Induktionsvoraussetzung und die strenge Isotonie der Wurzelfunktion verwendet.
Außerdem ist die Folge $(a_n)$ durch 2 nach oben beschränkt: Es ist ${a_1=1<2}$, und ist ${n\in\mathbb N}$ mit ${a_n <2}$, so folgt
\[
a_{n+1} = \sqrt{\vphantom{1+a_n^2}1+a_n} < \sqrt{\vphantom{1+a_n^2}1+2} = \sqrt{\vphantom{1+a_n^2}3} < 2\quad.
\] Hier wurde wieder die Induktionsvoraussetzung und die strenge Isotonie der Wurzelfunktion verwendet.
Damit ist die Folge $(a_n)$ monoton wachsend und nach oben beschränkt, also existiert ${\displaystyle\lim_{n\to\infty}a_n}$.
Wie bestimmt man nun den Grenzwert der Folge, nennen wir ihn $x$?
Dazu halten wir zunächst fest, dass gilt
\[
\lim_{n\to\infty}a_n = \lim_{n\to\infty}a_{n+1}\quad{.}
\] (Wie sähe ein Beweis dafür aus?)
Jedenfalls erhalten wir damit
\[
\lim_{n\to\infty}a_n = \lim_{n\to\infty}\sqrt{\vphantom{1+a_n^2}1+a_n}\quad{.}
\] Wenn wir jetzt nacheinander die Stetigkeit der Wurzelfunktion auf ${\mathbb R_{>0}}$ und die Stetigkeit der Addition auf ${\mathbb R \times \mathbb R}$ ausnutzen, so sehen wir, dass gilt
\[
x = \lim_{n\to\infty}a_n = \lim_{n\to\infty}\sqrt{\vphantom{\big(}1+a_n} = \sqrt{\vphantom{\big(}\lim_{n\to\infty}1+a_n} = \sqrt{\vphantom{\big(}1+\lim_{n\to\infty}a_n} = \sqrt{\vphantom{\big(}1+x}\quad{,}
\] d.h. wir haben nur noch die quadratische Gleichung $x^2=1+x$ zu lösen. Sie hat in $\mathbb R$ genau zwei Lösungen, von denen eine positiv und eine negativ ist. Die negative Lösung ist aber uninteressant: es gilt ${a_1>0}$, und die Folge ist streng monoton wachsend – also sind auch alle weiteren Folgenglieder größer als 0, und es folgt, dass ${\displaystyle\lim_{n\to\infty}a_n} \geqslant 0$ sein muss.
Damit ist der Grenzwert gefunden; sein Wert ist… ja, genau: $\displaystyle\frac{1+\sqrt{5}}{2}$.
Interessant ist noch, dass der Grenzwert ein Fixpunkt der der Folge zugrundeliegenden Abbildung
\[
f\colon \mathbb R_{>0}\to\mathbb R_{>0}\ , \quad x\mapsto\sqrt{\vphantom{1+a_n^2}1+x}\quad{,}
\] ist:
\[
\begin{array}{rclcl}
f\left(\frac{1+\sqrt{5}}{2}\right)
&=&
\sqrt{1+\frac{1+\sqrt{5}}{2}}
&=&
\sqrt{\frac{3+\sqrt{5}}{2}}
\\[5mm]
&=&
\sqrt{\frac32+\frac{\sqrt5}{2}}
&=&
\sqrt{\frac64+\frac{\sqrt5}{2}}
\\[5mm]
&=&
\sqrt{\frac14+\frac{\sqrt5}{2}+\frac54}
&=&
\sqrt{\left(\frac12\right)^2 + 2\cdot\frac12\cdot\frac{\sqrt5}{2} + \left(\frac{\sqrt5}{2}\right)^2}
\\[5mm]
&=&
\sqrt{\left(\frac12+\frac{\sqrt5}{2}\right)^2}
&=& \displaystyle\frac12+\frac{\sqrt5}{2}
\\[5mm]
&=&
\displaystyle\frac{1+\sqrt5}{2}
\end{array}
\] Wann ein Fixpunkt einer der Folge zungrundeliegenden Funktion ein Grenzwert der Folge ist, klärt der Banachsche Fixpunktsatz.
Samstag, 3. August 2013
Isomorphie endlicher Gruppen, Teil 1
Und nun geht es doch schneller als gedacht.
In dem einen Matheforum – genauer hier – bin ich auf die folgende Aussage gestoßen:
Zuerst der einfache Teil der Behauptung: Was ist mit der trivialen Gruppe los? Sie hat Ordnung $1$, und $1$ ist quadratfrei (denn eine natürliche Zahl $n$ ist genau dann quadratfrei, wenn in der PFZ von $n$ kein Primfaktor mit Vielfachheit größer als $1$ erscheint). Die Menge der Primteiler von $1$ ist leer, denn die kleinste Primzahl ist $2$. Also ist hier nicht viel zu tun.
Und nun… Trommelwirbel………………………… Je zwei Gruppen der Ordnung $1$ sind isomorph! (Beweis? vielleicht später irgendwann mal… es sei denn, jemand hinterlässt ihn als Kommentar ;))
Jetzt sei also $n$ eine natürliche Zahl größer als $1$.
Wenn $n$ eine Primzahl ist, dann ist die Sache einfach.
Denn sei $n$ eine Primzahl und $G$ eine Gruppe der Ordnung $n$. Dann gilt zunächst, dass $n$ mit Ausnahme von $1$ und $n$ keine positiven Teiler hat. Aus dem Satz von Lagrange können wir also folgern, dass $G$ keine nichttrivialen Untergruppen, d.h. solche, die von $G$ und $\{1\}$ verschieden sind, haben kann. Also hat jedes Element von $G$ entweder die Ordnung $1$ oder die Ordnung $n$.
Welche Elemente von $G$ haben Ordnung $1$?
Sicherlich das neutrale Element, denn $1$, egal wie oft mit sich selbst verknüpft, ist wieder gleich $1$.
Kann es noch weitere Elemente von $G$ geben, die Ordnung $1$ haben?
Nein, denn sei $a\in G\setminus\{1\}$, und es gelte $\mathrm{ord}(a)=1$. Dann folgt, dass die von $a$ erzeugte zyklische Untergruppe gleich $\{1\}$ ist, und damit wäre $a$ ein neutrales Element in $G$. Jedoch hatten wir $a$ als vom neutralen Element verschieden vorausgesetzt.
Damit haben wir gezeigt: Jedes Element $a\in G\setminus\{1\}$ hat Ordnung $n$.
Insgesamt haben wir damit die Ordnung aller Gruppenelemente bestimmt, und dadurch ist die Gruppe natürlich (bis auf Isomorphie ;)) festgelegt.
Wir sind jetzt also bei folgender Aussage angekommen: „Je zwei Gruppen von Primzahlordnung sind isomorph.“ Wenn wir nun zeigen „Für jede Primzahl $p$ gilt: $p$ ist quadratfrei und für alle Primteiler $q$, $r$ von $p$ gilt $q\nmid r-1$“, dann haben wir die behauptete Äquivalenz zumindest für Primzahlordnungen nachgewiesen. Und das sind immerhin schon unendlich viele.
Sei also $p$ eine Primzahl. Dann ist $p$ klarerweise quadratfrei, denn der einzige Primteiler mit Vielfachheit $1$ ist $p$, und alle anderen Primteiler haben Vielfachheit $0$. Also hat kein Primteiler Vielfachheit größer als $1$.
Nun zum zweiten Teil der Und-Aussage. Seien $q$, $r\in\mathbb P$, und es gelte $q\mid p$ und $r \mid p$. Dann folgt sofort $q=p=r$. Also gilt $q\nmid q-1=r-1$, denn zwei aufeinander folgende natürliche Zahlen sind stets teilerfremd.
So. Das war der einfache Teil. Der schwierige Teil, also die zusammengesetzten Gruppenordnungen, kommt später.
In dem einen Matheforum – genauer hier – bin ich auf die folgende Aussage gestoßen:
Sei $n\in{\mathbb N}$. Genau dann sind alle Gruppen der Ordnung $n$ isomorph, wenn $n$ quadratfrei ist und für je zwei Primteiler $p$ und $q$ von $n$ gilt: $p\nmid q-1$.
Zuerst der einfache Teil der Behauptung: Was ist mit der trivialen Gruppe los? Sie hat Ordnung $1$, und $1$ ist quadratfrei (denn eine natürliche Zahl $n$ ist genau dann quadratfrei, wenn in der PFZ von $n$ kein Primfaktor mit Vielfachheit größer als $1$ erscheint). Die Menge der Primteiler von $1$ ist leer, denn die kleinste Primzahl ist $2$. Also ist hier nicht viel zu tun.
Und nun… Trommelwirbel………………………… Je zwei Gruppen der Ordnung $1$ sind isomorph! (Beweis? vielleicht später irgendwann mal… es sei denn, jemand hinterlässt ihn als Kommentar ;))
Jetzt sei also $n$ eine natürliche Zahl größer als $1$.
Wenn $n$ eine Primzahl ist, dann ist die Sache einfach.
Denn sei $n$ eine Primzahl und $G$ eine Gruppe der Ordnung $n$. Dann gilt zunächst, dass $n$ mit Ausnahme von $1$ und $n$ keine positiven Teiler hat. Aus dem Satz von Lagrange können wir also folgern, dass $G$ keine nichttrivialen Untergruppen, d.h. solche, die von $G$ und $\{1\}$ verschieden sind, haben kann. Also hat jedes Element von $G$ entweder die Ordnung $1$ oder die Ordnung $n$.
Welche Elemente von $G$ haben Ordnung $1$?
Sicherlich das neutrale Element, denn $1$, egal wie oft mit sich selbst verknüpft, ist wieder gleich $1$.
Kann es noch weitere Elemente von $G$ geben, die Ordnung $1$ haben?
Nein, denn sei $a\in G\setminus\{1\}$, und es gelte $\mathrm{ord}(a)=1$. Dann folgt, dass die von $a$ erzeugte zyklische Untergruppe gleich $\{1\}$ ist, und damit wäre $a$ ein neutrales Element in $G$. Jedoch hatten wir $a$ als vom neutralen Element verschieden vorausgesetzt.
Damit haben wir gezeigt: Jedes Element $a\in G\setminus\{1\}$ hat Ordnung $n$.
Insgesamt haben wir damit die Ordnung aller Gruppenelemente bestimmt, und dadurch ist die Gruppe natürlich (bis auf Isomorphie ;)) festgelegt.
Wir sind jetzt also bei folgender Aussage angekommen: „Je zwei Gruppen von Primzahlordnung sind isomorph.“ Wenn wir nun zeigen „Für jede Primzahl $p$ gilt: $p$ ist quadratfrei und für alle Primteiler $q$, $r$ von $p$ gilt $q\nmid r-1$“, dann haben wir die behauptete Äquivalenz zumindest für Primzahlordnungen nachgewiesen. Und das sind immerhin schon unendlich viele.
Sei also $p$ eine Primzahl. Dann ist $p$ klarerweise quadratfrei, denn der einzige Primteiler mit Vielfachheit $1$ ist $p$, und alle anderen Primteiler haben Vielfachheit $0$. Also hat kein Primteiler Vielfachheit größer als $1$.
Nun zum zweiten Teil der Und-Aussage. Seien $q$, $r\in\mathbb P$, und es gelte $q\mid p$ und $r \mid p$. Dann folgt sofort $q=p=r$. Also gilt $q\nmid q-1=r-1$, denn zwei aufeinander folgende natürliche Zahlen sind stets teilerfremd.
So. Das war der einfache Teil. Der schwierige Teil, also die zusammengesetzten Gruppenordnungen, kommt später.
Donnerstag, 1. August 2013
Impressum
Angaben gemäß § 5 TMG:
Thure Dührsen
Elisabethstraße 116
24143 Kiel
Kontakt:
| Telefon: | +49 (0) 160 9641 8332 |
| E-Mail: | sammeltlemmas@gmx.net |
Verantwortlich für den Inhalt nach § 55 Abs. 2 RStV:
Thure Dührsen
Elisabethstraße 116
24143 Kiel
Quelle: Erstellt durch den Impressum-Generator von e-recht24.de für Privatpersonen.
Abonnieren
Posts (Atom)