Jeweils vier Lösungen von x^2=8n+1 mod 2^r

02.10.2012, 16:49

mathinitus

Jeweils vier Lösungen von x^2=8n+1 mod 2^r

Hallo!

Durch Ausprobieren habe ich festgestellt, dass für $\begin{eqnarray*} 3\le r\le 6 \end{eqnarray*}$ die Gleichung $\begin{eqnarray*} x^2=8n+1\mod 2^r \end{eqnarray*}$ für jedes ganze n genau vier Lösungen (mod 2^r) hat. Die Vermutung liegt nahe, dass dies auch für r>6 gilt.
Jedoch habe ich keinen Beweis finden können. Habt ihr eine Idee? Ein kleiner Hinweis ist eventuell schon genug (will ja auch noch selbst etwas tun).

Vielen Dank!

02.10.2012, 17:06

HAL 9000

Auf diesen Beitrag antworten »

(Bitte löschen, ich beuge mich den Algebraikern - die mögen anscheinend keine einfach verständlichen Lösungen, wie man auch schon hier sehen konnte.)

02.10.2012, 18:26

tmo

Auf diesen Beitrag antworten »

Eine kleine Alternative, die vielleicht mehr den mathematischen Hintergrund hinter dieser Aussage erkennen lässt:

Der Isomorphismus (für $\begin{eqnarray*} r \geq 3 \end{eqnarray*}$ )

$\begin{eqnarray*} \varphi: \mathbb Z/2 \mathbb Z \oplus \mathbb Z/2^{r-2} \mathbb Z \to (\mathbb Z/2^r \mathbb Z)^* \end{eqnarray*}$ , $\begin{eqnarray*} (i,j) \mapsto (-1)^i 5^j \end{eqnarray*}$

führt zum Ziel.

Da HAL eine elementare Lösung vorgeschlagen hat, will ich meine Lösung auch elementarer halten und den Isomorphismus kurz erläutern:
Wenn man für $\begin{eqnarray*} r\geq 3 \end{eqnarray*}$ mal $\begin{eqnarray*} 5^{2^{r-3}} \equiv 2^{r-1} +1 \pmod {2^r} \end{eqnarray*}$ induktiv nachweist, so folgert man schnell, dass $\begin{eqnarray*} 5 \end{eqnarray*}$ die Ordnung $\begin{eqnarray*} 2^{r-2} \end{eqnarray*}$ in $\begin{eqnarray*} (\mathbb Z/2^r \mathbb Z)^* \end{eqnarray*}$ hat. Also erfüllen die beiden Untergruppen $\begin{eqnarray*} \langle -1 \rangle \end{eqnarray*}$ und $\begin{eqnarray*} \langle 5 \rangle \end{eqnarray*}$ alles was man braucht, um zu folgern, dass $\begin{eqnarray*} (\mathbb Z/2^r \mathbb Z)^* \end{eqnarray*}$ ihre direktes Produkt ist:

Sie schneiden sich trivial und ihre Ordnungen multiplizieren sich zur Gruppenordnung.

edit: @HAL: Wer sagt, dass ich deine Lösung (bzw. die Lösung, die ich hinter deinem Tipp vermute) nicht mag. Ich fand sie sogar sehr gut und gehe fest davon aus, dass mathinitus diese Lösung auch mit dem Tipp selbst führen würde.
Nichtdestotrotz dachte ich mir, dass neben dieser Lösung eine Betrachtung meiner Lösung auch sehr lehrreich sein könnte (ich weiß, dass mathinitus sich sicher gerne mit mehreren Lösungsmöglichkeiten beschäftigt).
Und was das angeht ist es nunmal so, dass die Ursache der 4 Lösungen in der Struktur der Einheitengruppe zu finden ist, nämlich dass sie das Produkt 2er zyklischer Gruppen ist.

Damit wollte ich keinerseits beurteilen, welche der beiden Lösungen jetzt in irgendeiner Form besser ist. Warum sollte man das auch wollen?
Daher finde ich es ein bisschen schade, dass du deswegen gleich deinen Vorschlag hier gelöscht hast.

02.10.2012, 19:16

HAL 9000

Auf diesen Beitrag antworten »

Nein, nein, ich erkenne das an: Wenn du in einem Thread so früh mit einem Alternativvorschlag kommst, dann muss der einfach besser oder zumindest doch lehrreicher für den Fragesteller sein - und darauf kommt es ja an.

03.10.2012, 00:42

mathinitus

Auf diesen Beitrag antworten »

Hallo ihr zwei. Ich muss hier tmo recht geben, er schrieb:

Zitat:

Original von tmo
Nichtdestotrotz dachte ich mir, dass neben dieser Lösung eine Betrachtung meiner Lösung auch sehr lehrreich sein könnte (ich weiß, dass mathinitus sich sicher gerne mit mehreren Lösungsmöglichkeiten beschäftigt).

Tatsächlich beschäftige ich mich gerne mit mehreren Lösungswegen. Daher bin ich auch beide durchgegangen. Dadurch bekommt man einen tieferen Einblick und man schult sein mathematisches Verständnis. Folglich habe ich mich sowohl über deine als auch über die Lösung von tmo gefreut.

Zitat:

Original von HAL 9000
Tipp: Für $\begin{eqnarray*} r\geq 4 \end{eqnarray*}$ sowie alle ungeraden $\begin{eqnarray*} x \end{eqnarray*}$ gilt

$\begin{eqnarray*} \left( x + 2^{r-2} \right)^2 = x^2 + x2^{r-1} + 2^{2r-4} \equiv x^2 + 2^{r-1} \bmod 2^r \end{eqnarray*}$

Danke für deine Hilfe, damit habe ich es hinbekommen. Mal salopp beschrieben: Über vollständige Induktion bekommt man, dass es für jedes n acht potentielle Lösungen gibt. Man weiß jedoch nicht, ob es wirklich passt, oder das Quadrat "gegenüber" liegt. Durch deinen Tipp sieht man aber, dass es zu jeder Lösung, eine weitere gibt, die genau gegenüber ankommt. Also müssen sich die acht Lösungen die beiden Seiten 4 zu 4 teilen.

Zitat:

Original von tmo
Eine kleine Alternative, die vielleicht mehr den mathematischen Hintergrund hinter dieser Aussage erkennen lässt:

Der Isomorphismus (für $\begin{eqnarray*} r \geq 3 \end{eqnarray*}$ )

$\begin{eqnarray*} \varphi: \mathbb Z/2 \mathbb Z \oplus \mathbb Z/2^{r-2} \mathbb Z \to (\mathbb Z/2^r \mathbb Z)^* \end{eqnarray*}$ , $\begin{eqnarray*} (i,j) \mapsto (-1)^i 5^j \end{eqnarray*}$

führt zum Ziel.

Da HAL eine elementare Lösung vorgeschlagen hat, will ich meine Lösung auch elementarer halten und den Isomorphismus kurz erläutern:
Wenn man für $\begin{eqnarray*} r\geq 3 \end{eqnarray*}$ mal $\begin{eqnarray*} 5^{2^{r-3}} \equiv 2^{r-1} +1 \pmod {2^r} \end{eqnarray*}$ induktiv nachweist, so folgert man schnell, dass $\begin{eqnarray*} 5 \end{eqnarray*}$ die Ordnung $\begin{eqnarray*} 2^{r-2} \end{eqnarray*}$ in $\begin{eqnarray*} (\mathbb Z/2^r \mathbb Z)^* \end{eqnarray*}$ hat. Also erfüllen die beiden Untergruppen $\begin{eqnarray*} \langle -1 \rangle \end{eqnarray*}$ und $\begin{eqnarray*} \langle 5 \rangle \end{eqnarray*}$ alles was man braucht, um zu folgern, dass $\begin{eqnarray*} (\mathbb Z/2^r \mathbb Z)^* \end{eqnarray*}$ ihre direktes Produkt ist:

Vielen Dank. Konnte mit der Hilfe die Sache erfolgreich nachweisen.

Du sagtest:

Zitat:

Original von tmo
Sie schneiden sich trivial und ihre Ordnungen multiplizieren sich zur Gruppenordnung.

Brauchen wir nicht noch zusätzlich, dass die beiden Untergruppen miteinanderer kommutieren (was hier trivialerweise erfüllt ist, weil unsere Gruppe abelsch ist)?

03.10.2012, 08:15

HAL 9000

Auf diesen Beitrag antworten »

Zitat:

Original von mathinitus
Mal salopp beschrieben: Über vollständige Induktion bekommt man, dass es für jedes n acht potentielle Lösungen gibt.

Acht? Kommt drauf an, was genau man da per Induktion beweist, ich hatte eher an folgendes gedacht:

Zitat:

Für alle $\begin{eqnarray*} r\geq 2 \end{eqnarray*}$ gilt: Die $\begin{eqnarray*} 2^{r-2} \end{eqnarray*}$ Quadrate der ungeraden $\begin{eqnarray*} x=1,3,\ldots,2^{r-1}-1 \end{eqnarray*}$ ergeben genau die Werte $\begin{eqnarray*} (8n+1) \bmod 2^{r+1} \end{eqnarray*}$ für $\begin{eqnarray*} n=0,1,\ldots,2^{r-2}-1 \end{eqnarray*}$

Rückgerechnet auf $\begin{eqnarray*} \bmod 2^r \end{eqnarray*}$ sowie $\begin{eqnarray*} (-x) \end{eqnarray*}$ einbezogen, ergeben sich die genau 4 Lösungen $\begin{eqnarray*} \bmod 2^r \end{eqnarray*}$ .

03.10.2012, 09:56

tmo

Auf diesen Beitrag antworten »

@HAL: Der Zeitpunkt der Alternative war etwas unglücklich, das gebe ich zu. Er kam übrigens so zustande:
Unmittelbar nachdem ich den Thread gesehen hatte (und er noch ohne Antwort war), tippte ich meine Idee mit dem Iso ein. Als ich absenden wollte, sah ich deine Antwort und schickte daher erstmal nicht ab, aber ließ das Fenster offen. Zwischenzeitlich machte ich was anderes und als ich wieder am PC saß, schickte ich dann doch ab (primär einfach nur, weil ich es ja schon getippt hatte, sekundär wegen dem, mit dem ich auch oben schon gerechtfertigt hatte).
Das nächste mal werde ich glaube ich besser abwarten bis das Problem gelöst ist und dann eine Alternative anbieten (so ist es hier ja normalerweise auch üblich).

Zitat:

Original von mathinitus
Du sagtest:

Zitat:

Original von tmo
Sie schneiden sich trivial und ihre Ordnungen multiplizieren sich zur Gruppenordnung.

Brauchen wir nicht noch zusätzlich, dass die beiden Untergruppen miteinanderer kommutieren (was hier trivialerweise erfüllt ist, weil unsere Gruppe abelsch ist)?

Ja meistens fordert man noch, dass die Untergruppen Normalteiler sind, dann folgt auch, dass sie kommutieren. Aber weil hier eh alles abelsch ist, brauchen wir das nicht, wie du auch schon erwähnt hast.

Im Übrigen: Dass dann auch alle Quadrate von der Form $\begin{eqnarray*} 8n+1 \end{eqnarray*}$ sind, folgt (unabhängig vom Beweis) schon aus der Aussage selbst, schließlich ist jede 4. Zahl in $\begin{eqnarray*} (\mathbb Z/2^r\mathbb Z)^* \end{eqnarray*}$ von der Form $\begin{eqnarray*} 8n+1 \end{eqnarray*}$ . Da ist für andere Quadrate einfach kein Platz mehr smile

03.10.2012, 10:58

Mystic

Auf diesen Beitrag antworten »

Ja, HAL's Lösung gefällt mir ebenfalls ausgezeichnet, obwohl er mich jetzt sicher zu den von ihm so apostrophierten "Algebraikern" zählen würde... Freude

Eine etwas andere Sichtweise bestünde darin, dass man von vorneherein nur die Kongruenz

$\begin{eqnarray*} x^2 \equiv 1 \mod 2^r \quad (r \ge 3) \quad (*) \end{eqnarray*}$

betrachtet, denn es ist ja offensichtlich so, dass man aus jeder partikulären Lösung von

$\begin{eqnarray*} x^2 \equiv 8n+1 \mod 2^r \quad (r \ge 3) \quad (**) \end{eqnarray*}$

durch Multiplikation mit allen Lösungen von (*) dann auch alle Lösungen von (**) (jede genau einmal) gewinnt...

Nun sind aber die Lösungen von (*) gegeben durch

$\begin{eqnarray*} \pm 1, 2^{r-1}\pm1 \end{eqnarray*}$

Dies prüft man für r=3 leicht direkt nach und für r>3 folgt dies induktiv durch Nachrechnen daraus, dass von den 8 in Frage kommenden Möglichkeiten (man beachte, dass jede Lösung mod $\begin{eqnarray*} 2^r \end{eqnarray*}$ ja auch Lösung mod $\begin{eqnarray*} 2^{r-1} \end{eqnarray*}$ sein muss!)

$\begin{eqnarray*} \pm 1 +k2^{r-1}, \pm1 +2^{r-1}+k2^{r-1} \quad (k=0,1) \end{eqnarray*}$

tatsächlich wieder nur die 4 Möglichkeiten

$\begin{eqnarray*} \pm 1 +k2^{r-1} \quad (k=0,1) \end{eqnarray*}$

auch wirklich Lösungen sind... Anschaulich gesprochen ist es also so, dass sich nur 2 der 4 Lösungen mod $\begin{eqnarray*} 2^{r-1} \end{eqnarray*}$ auch zu Lösungen mod $\begin{eqnarray*} 2^r \end{eqnarray*}$ fortsetzen lassen, dass es dafür aber für diese dann jeweils 2 Fortsetzungen gibt, sodass man schlußendlich wieder auf die Gesamtzahl 4 kommt..

Edit: Dass übrigens überhaupt partikuläre Lösungen zu (**) existieren, folgt leicht daraus, das das Qaudrat einer ungeraden Zahl stets von der Form 8n+1 sein muss... Da Zahlen dieser Form gerade ein Viertel aller ungeraden Zahlen mod $\begin{eqnarray*} 2^r \end{eqnarray*}$ ausmachen und es zu (**) nach obigem entweder 0 oder genau 4 Lösungen gibt, kann der Fall 0 nicht wirklich auftreten...

Neue Frage »

Antworten »

Jeweils vier Lösungen von x^2=8n+1 mod 2^r

Verwandte Themen