Quadratische Reste < Zahlentheorie < Algebra+Zahlentheo. < Hochschule < Mathe < Vorhilfe
|
| Status: |
(Frage) beantwortet  | | Datum: | 21:41 Di 12.07.2011 | | Autor: | Physy |
| Aufgabe | Es ist 10001 = 73 * 137. Außerdem sind 73 und 137 Primzahlen.
Finde säamtliche Lösungen der Kongruenz
[mm] x^2 \equiv [/mm] 1 mod 10001. |
Wir sind gerade bei dem Thema Potenzreste, jedoch haben wir in der Vorlesung nur gezeigt, wie man mittels des Legendre-Symbols herausfindet, ob eine Kongruenz [mm] x^2 \equiv [/mm] a mod n überhaupt lösbar ist.
Wie aber bestimmte ich nun die Lösung einer solchen bzw. dieser Kongruenz?
Vielen Dank im Voraus.
|
|
| |
|
| Status: |
(Antwort) fertig  | | Datum: | 22:34 Di 12.07.2011 | | Autor: | felixf |
Moin!
> Es ist 10001 = 73 * 137. Außerdem sind 73 und 137
> Primzahlen.
> Finde säamtliche Lösungen der Kongruenz
> [mm]x^2 \equiv[/mm] 1 mod 10001.
> Wir sind gerade bei dem Thema Potenzreste, jedoch haben
> wir in der Vorlesung nur gezeigt, wie man mittels des
> Legendre-Symbols herausfindet, ob eine Kongruenz [mm]x^2 \equiv[/mm]
> a mod n überhaupt lösbar ist.
>
> Wie aber bestimmte ich nun die Lösung einer solchen bzw.
> dieser Kongruenz?
a) Finde alle Loesungen von [mm] $x^2 \equiv [/mm] 1 [mm] \pmod{73}$
[/mm]
b) Finde alle Loesungen von [mm] $x^2 \equiv [/mm] 1 [mm] \pmod{137}$
[/mm]
c) Wende den chinesischen Restsatz an
Da fehlen jetzt noch ein paar Details, aber etwas musst du ja auch selber tun  Versuch das damit mal zu loesen... Wenn du haengenbleibst, sag was du schon hast und ob du Ideen hast wie's weitergehen koennte.
LG Felix
|
|
|
| |
|
| Status: |
(Frage) beantwortet | | Datum: | 23:29 Di 12.07.2011 | | Autor: | Physy |
Das ist mir schon klar, bloß das Problem ist eben die Größe der Zahl. Wie kann ich auf die Lösungen [mm] x^2 \equiv [/mm] 1 mod 137 kommen ohne sukzessiv alle Zahlen durchzuprobieren? Und wie kann ich diese Fragestellung in Beziehung mit Potenzresten bringen? Ich weiß nur, dass ich den Aufwand auf 68 Überprüfungen reduzieren kann, da [mm] x^2 [/mm] = [mm] (-x)^2..
[/mm]
|
|
|
| |
|
Hallo Physy,
> Das ist mir schon klar, bloß das Problem ist eben die
> Größe der Zahl. Wie kann ich auf die Lösungen [mm]x^2 \equiv[/mm]
> 1 mod 137 kommen ohne sukzessiv alle Zahlen
> durchzuprobieren?
Na, Du weißt ja, dass 137 prim ist. Damit hat jede Äuqivalenz [mm] x^2\equiv a\mod{137} [/mm] genau zwei Lösungen, x und -x.
Dass die 1 eine Lösung ist, solltest Du ohne langes Rechnen erkennen. Wie lautet also die andere? Damit hast Du dann alle.
> Und wie kann ich diese Fragestellung in
> Beziehung mit Potenzresten bringen? Ich weiß nur, dass ich
> den Aufwand auf 68 Überprüfungen reduzieren kann, da [mm]x^2[/mm]
> = [mm](-x)^2..[/mm]
Ich sehe wohl, dass [mm] 68=\bruch{137-1}{2} [/mm] ist, damit also die Zahl der existierenden quadratischen Reste, aber ich sehe nicht, wieso Du alle anderen auch durchprüfen musst - sofern eben gesichert ist, dass 137 eine Primzahl ist und nicht etwa zerlegbar.
Grüße
reverend
|
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig  | | Datum: | 00:12 Mi 13.07.2011 | | Autor: | abakus |
> Hallo Physy,
>
> > Das ist mir schon klar, bloß das Problem ist eben die
> > Größe der Zahl. Wie kann ich auf die Lösungen [mm]x^2 \equiv[/mm]
> > 1 mod 137 kommen ohne sukzessiv alle Zahlen
> > durchzuprobieren?
>
> Na, Du weißt ja, dass 137 prim ist. Damit hat jede
> Äuqivalenz [mm]x^2\equiv a\mod{137}[/mm] genau zwei Lösungen, x
> und -x.
>
> Dass die 1 eine Lösung ist, solltest Du ohne langes
> Rechnen erkennen. Wie lautet also die andere? Damit hast Du
> dann alle.
Man kann auch dieses überlegen:
Aus [mm]x^2\equiv 1\mod{137}[/mm] folgt
[mm]x^2-1\equiv 0\mod{137}[/mm]
also
137 teilt [mm] x^2-1,
[/mm]
demzufolge gilt
137 teilt (x+1)(x-1)
Gruß Abakus
>
> > Und wie kann ich diese Fragestellung in
> > Beziehung mit Potenzresten bringen? Ich weiß nur, dass ich
> > den Aufwand auf 68 Überprüfungen reduzieren kann, da [mm]x^2[/mm]
> > = [mm](-x)^2..[/mm]
>
> Ich sehe wohl, dass [mm]68=\bruch{137-1}{2}[/mm] ist, damit also die
> Zahl der existierenden quadratischen Reste, aber ich sehe
> nicht, wieso Du alle anderen auch durchprüfen musst -
> sofern eben gesichert ist, dass 137 eine Primzahl ist und
> nicht etwa zerlegbar.
>
> Grüße
> reverend
>
|
|
|
| |
|
| Status: |
(Frage) beantwortet | | Datum: | 00:32 Mi 13.07.2011 | | Autor: | Physy |
Ok, das war ja gar nicht so schwer :) Wir hatten sogar einen Satz dazu merke ich gerade. Nämlich, dass die Anzahl der Lösungen = ggT(2,phi(137))=2 ist. Dann sind also mit dem Chinesischen Restsatz folgende Kongruenzsysteme zu lösen:
1.) x [mm] \equiv [/mm] 1 (mod 137), x [mm] \equiv [/mm] 1 (mod 73)
2.) x [mm] \equiv [/mm] 1 (mod 137), x [mm] \equiv [/mm] 72 (mod 73)
3.) x [mm] \equiv [/mm] 136 (mod 137), x [mm] \equiv [/mm] 1 (mod 73)
4.) x [mm] \equiv [/mm] 136 (mod 137), x [mm] \equiv [/mm] 72 (mod 73)
Bis auf den 1. Fall werde ich wohl mit einer Tabelle nicht sehr weit kommen, oder? Die Tabelle wird ja viel zu groß ... bzw. wie wende ich den Chinesischen Restsatz für große Zahlen am besten an?
|
|
|
| |
|
| Status: |
(Antwort) fertig | | Datum: | 00:41 Mi 13.07.2011 | | Autor: | felixf |
Moin!
> Ok, das war ja gar nicht so schwer :) Wir hatten sogar
> einen Satz dazu merke ich gerade. Nämlich, dass die Anzahl
> der Lösungen = ggT(2,phi(137))=2 ist. Dann sind also mit
> dem Chinesischen Restsatz folgende Kongruenzsysteme zu
> lösen:
> 1.) x [mm]\equiv[/mm] 1 (mod 137), x [mm]\equiv[/mm] 1 (mod 73)
> 2.) x [mm]\equiv[/mm] 1 (mod 137), x [mm]\equiv[/mm] 72 (mod 73)
> 3.) x [mm]\equiv[/mm] 136 (mod 137), x [mm]\equiv[/mm] 1 (mod 73)
> 4.) x [mm]\equiv[/mm] 136 (mod 137), x [mm]\equiv[/mm] 72 (mod 73)
> Bis auf den 1. Fall werde ich wohl mit einer Tabelle nicht
> sehr weit kommen, oder?
Naja, Fall 4 ist auch sehr trivial. Die Loesung ist naemlich einfach -1.
> Die Tabelle wird ja viel zu groß
> ... bzw. wie wende ich den Chinesischen Restsatz für
> große Zahlen am besten an?
Ihr habt den Satz doch sicher mit dem Euklidischen Algorithmus bewiesen, oder? Oder mal ein Beispiel dazu mit Hilfe des euklidischen Algorithmus gerechnet? Schau mal nach. Mit dem geht es naemlich sehr effizient.
LG Felix
|
|
|
| |
|
| Status: |
(Frage) beantwortet | | Datum: | 00:44 Mi 13.07.2011 | | Autor: | Physy |
Wir haben den Satz nicht mit dem Euklidischen Algorithmus bewiesen und ein Beispiel dazu haben wir auch nicht. Ich habe bisher auch nicht gewusst, dass man Kongruenzsysteme mit dem Euklidischen Algorithmus lösen kann. Wie funktioniert das denn?
|
|
|
| |
|
| Status: |
(Antwort) fertig | | Datum: | 01:00 Mi 13.07.2011 | | Autor: | felixf |
Moin!
> Wir haben den Satz nicht mit dem Euklidischen Algorithmus
> bewiesen
Wie habt ihr ihn denn bewiesen?
> und ein Beispiel dazu haben wir auch nicht. Ich
> habe bisher auch nicht gewusst, dass man Kongruenzsysteme
> mit dem Euklidischen Algorithmus lösen kann. Wie
> funktioniert das denn?
Guck mal ![[]](/images/popup.gif) hier, da ist ein Beispiel.
LG Felix
|
|
|
|
