Lösungen quadr. Kongruenz < Zahlentheorie < Algebra+Zahlentheo. < Hochschule < Mathe < Vorhilfe
|
| Status: |
(Frage) beantwortet  | | Datum: | 17:44 Sa 02.10.2010 | | Autor: | daN-R-G |
| Aufgabe | | Bestimmen sie alle Lösungen [mm] \in [/mm] {1, 2, ..., 32}, der Kongruenz [mm] x^2 \equiv [/mm] 1 [mm] \pmod{33} [/mm] |
Huhu...
Ich hätte mal ne Frage zu solch einer Art an Aufgabe: Gibt es einen Trick, die Lösungen zu finden, ohne dass ich all die Werte durchrechnen muss?
Es ist ja klar, dass [mm] 1^2 \equiv [/mm] 1 [mm] \pmod{33} [/mm] ist, das gleiche gilt auch für [mm] 10^2 [/mm] = 100 aber nun alle Werte von 2 bis 32 zu quadrieren halte ich doch für sehr aufwändig.
Ich kann gewisse Werte doch mit Sicherheit auf im Vorfeld aussortieren, oder? Gibts da einen Satz, der mir dabei hilft?
Nebenbei wäre -1 und -10 ja ebenfalls eine Lösung. Ich denke diese ist aber nicht gesucht mit der oben angegebenen Aufgabe, oder?
Vielen Dank! ;)
|
|
| |
|
Hallo daN-R-G,
> Bestimmen sie alle Lösungen [mm]\in[/mm] {1, 2, ..., 32}, der
> Kongruenz [mm]x^2 \equiv[/mm] 1 [mm]\pmod{33}[/mm]
> Huhu...
>
> Ich hätte mal ne Frage zu solch einer Art an Aufgabe: Gibt
> es einen Trick, die Lösungen zu finden, ohne dass ich all
> die Werte durchrechnen muss?
>
> Es ist ja klar, dass [mm]1^2 \equiv[/mm] 1 [mm]\pmod{33}[/mm] ist, das
> gleiche gilt auch für [mm]10^2[/mm] = 100 aber nun alle Werte von 2
> bis 32 zu quadrieren halte ich doch für sehr aufwändig.
> Ich kann gewisse Werte doch mit Sicherheit auf im Vorfeld
> aussortieren, oder? Gibts da einen Satz, der mir dabei
> hilft?
Nun, die Zahl 33 läßt sich zerlegen in 3*11, das heisst:
Ist [mm]x^{2} \equiv 1 \ \left(33\right)[/mm],
dann erfüllt diese Quadratzahl ebenfalls die Kongruenzen
[mm]x^{2} \equiv 1 \ \left(3\right), \ x^{2} \equiv 1 \ \left(11\right)[/mm]
>
> Nebenbei wäre -1 und -10 ja ebenfalls eine Lösung. Ich
> denke diese ist aber nicht gesucht mit der oben angegebenen
> Aufgabe, oder?
Es sind hier nur Zahlen gesucht, die in der oben angegebenen Menge liegen.
>
> Vielen Dank! ;)
Gruss
MathePower
|
|
|
| |
|
| Status: |
(Frage) beantwortet | | Datum: | 19:02 Sa 02.10.2010 | | Autor: | daN-R-G |
Ah! Super... Daran habe ich garnicht gedacht! Dann muss ich ja in der Tat nur die Zahlen 1 bis 10 betrachten. Also wäre die Lösungsmenge dementsprechend {1, 10}.
[mm] x^2 \equiv [/mm] 1 [mm] \pmod{33} [/mm] heißt ja eigentlich, dass gilt [mm] $33|(x^2-1). [/mm] Also müssen auch 3 und 11 diese Zahl teilen. Klingt irgendwie logisch.
Nehmen wir nun einmal die 31 statt der 33. Das ist ja ne Primzahl. Gäbe es denn dann einen anderen weg, ohne wirklich alle Werte durchzuprobieren?
Danke erstmal für die Antwort :)
|
|
|
| |
|
Hallo,
> Ah! Super... Daran habe ich garnicht gedacht! Dann muss ich
> ja in der Tat nur die Zahlen 1 bis 10 betrachten.
Nein, wieso das denn?
> Also
> wäre die Lösungsmenge dementsprechend {1, 10}.
Der Bereich, aus dem die Lösungen stammen sollen, war doch vorgegeben. Dir fehlen noch die 23 und die 32. Dabei hattest Du die zugehörigen Restklassen doch schon identifiziert: -1,-10.
> [mm]x^2 \equiv[/mm] 1 [mm]\pmod{33}[/mm] heißt ja eigentlich, dass gilt
> [mm]$33|(x^2-1).[/mm] Also müssen auch 3 und 11 diese Zahl teilen.
> Klingt irgendwie logisch.
Nicht wahr?
> Nehmen wir nun einmal die 31 statt der 33. Das ist ja ne
> Primzahl. Gäbe es denn dann einen anderen weg, ohne
> wirklich alle Werte durchzuprobieren?
Wie oft taucht ein quadratischer Rest denn bei einem primen Modul auf?
Und um zu sehen, ob Du nun wirklich weißt, wie die Lösung eigentlich funktionierte, bestimme doch mal alle x mit 0<x<105 und [mm] x^2\equiv 1\mod{105}. [/mm] Wieviele gibt es davon?
Oder, nur damit Du nicht probierst - die gleiche Frage zum Modul 219029. Hilfe bei der Faktorisierung findest Du ![[]](/images/popup.gif) hier.
> Danke erstmal für die Antwort :)
Och, gern doch 
reverend
|
|
|
| |
|
| Status: |
(Frage) beantwortet | | Datum: | 20:20 Sa 02.10.2010 | | Autor: | daN-R-G |
Also wieso genau die 23 und 32 mir noch fehlen ist mir glaube ich noch nicht 100% klar. Weil 23 in der Restklasse -10 und 32 in der Restklasse -1 liegt?
Soweit ich weiß, tritt ein quadr. Rest immer 2 mal bei einem primen Modul auf.
Für den Fall [mm] x^2 \equiv [/mm] 1 [mm] \pmod{105} [/mm] betrachte ich nun folgendes: 105 = [mm] 3\cdot5\cdot7
[/mm]
Also muss gelten:
[mm] x^2 \equiv 1\pmod{3}
[/mm]
[mm] x^2 \equiv 1\pmod{5}
[/mm]
[mm] x^2 \equiv 1\pmod{7}
[/mm]
Wobei bei den einzelnen Kongruenzen dann die Lösungen wären:
{1, 2}, {1, 4}, {1, 6}
Dementsprechend wäre meine Lösung dann für diese Kongruenz {1, 2, 4, 6}?
Ich hoffe ich mache es ansatzweise richtig :)
Danke!
|
|
|
| |
|
Hallo nochmal,
> Also wieso genau die 23 und 32 mir noch fehlen ist mir
> glaube ich noch nicht 100% klar. Weil 23 in der Restklasse
> -10 und 32 in der Restklasse -1 liegt?
Jaaa.
> Soweit ich weiß, tritt ein quadr. Rest immer 2 mal bei
> einem primen Modul auf.
Jaaaa.
> Für den Fall [mm]x^2 \equiv[/mm] 1 [mm]\pmod{105}[/mm] betrachte ich nun
> folgendes: 105 = [mm]3\cdot5\cdot7[/mm]
Jaaaaa.
> Also muss gelten:
> [mm]x^2 \equiv 1\pmod{3}[/mm]
> [mm]x^2 \equiv 1\pmod{5}[/mm]
> [mm]x^2 \equiv 1\pmod{7}[/mm]
Jaaaaaa.
> Wobei bei den einzelnen Kongruenzen dann die Lösungen
> wären:
> {1, 2}, {1, 4}, {1, 6}
Jaaaaaaa.
> Dementsprechend wäre meine Lösung dann für diese
> Kongruenz {1, 2, 4, 6}?
Hm. Nein.
> Ich hoffe ich mache es ansatzweise richtig :)
Der Ansatz ist gut, aber hier kommt der chinesische Restsatz eindeutig ins Spiel. Es gibt immerhin acht voneinander verschiedene Systeme von Kongruenzen zu lösen, jedes mit genau einer Lösung, die sich von denen der anderen Systeme unterscheidet.
Bei der gleichen Frage [mm] \mod{3003} [/mm] wären es entsprechend 16 Lösungen, da 3003=3*7*11*13.
> Danke!
Wir sind am Kern des Problems angelangt, denke ich.
In der ursprünglichen Aufgabe waren folgende vier Systeme zu lösen:
[mm] x\equiv 1\mod{3}
[/mm]
[mm] x\equiv 1\mod{11}
[/mm]
Lösung: [mm] x\equiv 1\mod{33}
[/mm]
[mm] x\equiv 1\mod{3}
[/mm]
[mm] x\equiv -1\mod{11}
[/mm]
Lösung: [mm] x\equiv 10\mod{33}
[/mm]
[mm] x\equiv -1\mod{3}
[/mm]
[mm] x\equiv 1\mod{11}
[/mm]
Lösung: [mm] x\equiv 23\mod{33}
[/mm]
[mm] x\equiv -1\mod{3}
[/mm]
[mm] x\equiv -1\mod{11}
[/mm]
Lösung: [mm] x\equiv 32\mod{33}
[/mm]
Alles klar?
Grüße
reverend
|
|
|
| |
|
| Status: |
(Frage) beantwortet | | Datum: | 20:54 Sa 02.10.2010 | | Autor: | daN-R-G |
Ah! Ich glaube ich komme dahinter. Den chin. Restsatz werde ich mir glaube ich noch genauer anschauen und mit Kongruenzen generell ein bissle arbeiten müssen.
Ich würd mich gerne noch einmal an dem Beispiel mit mod 105 probieren:
Zu lösen habe ich also
1)
x [mm] \equiv [/mm] 1 [mm] \pmod{3}
[/mm]
x [mm] \equiv [/mm] 1 [mm] \pmod{5}
[/mm]
x [mm] \equiv [/mm] 1 [mm] \pmod{7}
[/mm]
2)
x [mm] \equiv [/mm] 1 [mm] \pmod{3}
[/mm]
x [mm] \equiv [/mm] 1 [mm] \pmod{5}
[/mm]
x [mm] \equiv [/mm] -1 [mm] \pmod{7}
[/mm]
3)
x [mm] \equiv [/mm] 1 [mm] \pmod{3}
[/mm]
x [mm] \equiv [/mm] -1 [mm] \pmod{5}
[/mm]
x [mm] \equiv [/mm] 1 [mm] \pmod{7}
[/mm]
4)
x [mm] \equiv [/mm] -1 [mm] \pmod{3}
[/mm]
x [mm] \equiv [/mm] 1 [mm] \pmod{5}
[/mm]
x [mm] \equiv [/mm] 1 [mm] \pmod{7}
[/mm]
5)
x [mm] \equiv [/mm] 1 [mm] \pmod{3}
[/mm]
x [mm] \equiv [/mm] -1 [mm] \pmod{5}
[/mm]
x [mm] \equiv [/mm] -1 [mm] \pmod{7}
[/mm]
6)
x [mm] \equiv [/mm] -1 [mm] \pmod{3}
[/mm]
x [mm] \equiv [/mm] -1 [mm] \pmod{5}
[/mm]
x [mm] \equiv [/mm] 1 [mm] \pmod{7}
[/mm]
7)
x [mm] \equiv [/mm] -1 [mm] \pmod{3}
[/mm]
x [mm] \equiv [/mm] 1 [mm] \pmod{5}
[/mm]
x [mm] \equiv [/mm] -1 [mm] \pmod{7}
[/mm]
8)
x [mm] \equiv [/mm] -1 [mm] \pmod{3}
[/mm]
x [mm] \equiv [/mm] -1 [mm] \pmod{5}
[/mm]
x [mm] \equiv [/mm] -1 [mm] \pmod{7}
[/mm]
Offensichtlich ist ja nun die Lösung bei 1), dort kommt ja einfach 1 heraus.
Gibt es denn nun einen trick, wie ich bei den anderen Lösungen darauf komme, ohne irgendwie wild durchzuprobieren? Ich habe da irgendwie noch kein System gefunden.
|
|
|
| |
|
Hallo nochmal,
soweit alles richtig!
Ja, es geht ohne wildes Probieren. Lies mal den Wikipedia-Artikel, der ist ganz gut.
Das 2. System hat die Lösung 76, wie Du einigermaßen leicht (ohne trial and error!) ermitteln kannst.
lg
rev
|
|
|
| |
|
| Status: |
(Frage) beantwortet | | Datum: | 14:10 So 03.10.2010 | | Autor: | daN-R-G |
Also ich hätte dann nun folgende Lösungen heraus:
1) Lösung: 1
2) Lösung: 76
3) Lösung: 64
4) Lösung: 71
5) Lösung: 34
6) Lösung: 29
7) Lösung: 41
8) Lösung: 104
Gemacht habe ich das folgendermaßen, z.b. an 2)
x [mm] \equiv [/mm] 1 [mm] \pmod{3}
[/mm]
x [mm] \equiv [/mm] 1 [mm] \pmod{5}
[/mm]
x [mm] \equiv [/mm] -1 [mm] \pmod{7}
[/mm]
Jetzt habe ich die beiden letzten Kongruenzen betrachtet und versucht eine Lösung zu finden. Die ist mit 6 ja auch schon gefunden. Nun habe ich auf 6 immer den kgv(5,7) = 35 hinzuaddiert. Und bei 6 + 2*(35) = 76 wars auch für die erste Kongruenz lösbar.
Wenn ich das richtig verstanden habe, haben dann alle Lösungen dieses Systems die Form [mm] 76+z\cdot(kgv(3, [/mm] 5, 7)) = [mm] 76+z\cdot105, [/mm] z [mm] \in \IZ [/mm] ?
Macht man das im allgemeinen dann so? Wir hatten das zwar mal in der Übung... aber dort haben wir immer alle möglichen Restklassen der einzelnen Kongruenzen aufgeschrieben und dann geschaut, welche die erste ist, die in allen dreien vorkommt.
Bei einem kleinen Modul geht das ja noch, aber bei 105 fände ich das schonz u aufwändig, geschweige denn von noch größeren Zahlen...
|
|
|
| |
|
Hallo,
genau - das sind die acht Lösungen!
> Also ich hätte dann nun folgende Lösungen heraus:
>
> 1) Lösung: 1
> 2) Lösung: 76
> 3) Lösung: 64
> 4) Lösung: 71
> 5) Lösung: 34
> 6) Lösung: 29
> 7) Lösung: 41
> 8) Lösung: 104
>
> Gemacht habe ich das folgendermaßen, z.b. an 2)
> x [mm]\equiv[/mm] 1 [mm]\pmod{3}[/mm]
> x [mm]\equiv[/mm] 1 [mm]\pmod{5}[/mm]
> x [mm]\equiv[/mm] -1 [mm]\pmod{7}[/mm]
>
> Jetzt habe ich die beiden letzten Kongruenzen betrachtet
> und versucht eine Lösung zu finden. Die ist mit 6 ja auch
> schon gefunden. Nun habe ich auf 6 immer den kgv(5,7) = 35
> hinzuaddiert. Und bei 6 + 2*(35) = 76 wars auch für die
> erste Kongruenz lösbar.
Gut so. Das spart doch schon eine Menge Rechenarbeit.
> Wenn ich das richtig verstanden habe, haben dann alle
> Lösungen dieses Systems die Form [mm]76+z\cdot(kgv(3,[/mm] 5, 7)) =
> [mm]76+z\cdot105,[/mm] z [mm]\in \IZ[/mm] ?
Richtig. Das besagt die Angabe [mm] \mod{105}.
[/mm]
> Macht man das im allgemeinen dann so? Wir hatten das zwar
> mal in der Übung... aber dort haben wir immer alle
> möglichen Restklassen der einzelnen Kongruenzen
> aufgeschrieben und dann geschaut, welche die erste ist, die
> in allen dreien vorkommt.
Ja, das geht im allgemeinen so.
> Bei einem kleinen Modul geht das ja noch, aber bei 105
> fände ich das schonz u aufwändig, geschweige denn von
> noch größeren Zahlen...
Eben. So kann man aber ziemlich zielgerichtet suchen, und hat bei z.B. drei Faktoren nicht so viel Arbeit.
Grüße
reverend
|
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig  | | Datum: | 16:46 So 03.10.2010 | | Autor: | daN-R-G |
Vielen Dank!
Habs verstanden! ;)
|
|
|
|
