Lösbarkeit < Zahlentheorie < Algebra+Zahlentheo. < Hochschule < Mathe < Vorhilfe
|
| Status: |
(Frage) beantwortet  | | Datum: | 01:17 Fr 08.06.2012 | | Autor: | sissile |
| Aufgabe | | [mm] x^2 \equiv [/mm] 59 (mod 79) |
Hallo, ich habe eine kurze Frage.
WIe überprüfe ich ob z.B die Kongruenz [mm] x^2 \equiv [/mm] 59 (mod 79) lösbar ist?
|
|
| |
|
> [mm]x^2 \equiv[/mm] 59 (mod 79)
> Hallo, ich habe eine kurze Frage.
> WIe überprüfe ich ob z.B die Kongruenz [mm]x^2 \equiv[/mm] 59
> (mod 79) lösbar ist?
Hallo,
Stichworte: Legendre-Symbol, Euler-Kriterium.
LG Angela
|
|
|
| |
|
| Status: |
(Frage) beantwortet | | Datum: | 14:26 Fr 08.06.2012 | | Autor: | sissile |
Hallo,
Euler:
a ist quadratischer Rset mod p
<=>
[mm] a^{\frac{p-1}{2}} \equiv [/mm] 1 (mod p)
Hier [mm] 59^{\frac{79-1}{2}} [/mm] = [mm] 59^{39}
[/mm]
Wie kann ich dass denn ohne TR überprüfen (mod 79) ?
|
|
|
| |
|
> Hallo,
> Euler:
> a ist quadratischer Rset mod p
> <=>
> [mm]a^{\frac{p-1}{2}} \equiv[/mm] 1 (mod p)
>
> Hier [mm]59^{\frac{79-1}{2}}[/mm] = [mm]59^{39}[/mm]
> Wie kann ich dass denn ohne TR überprüfen (mod 79) ?
>
>
Hallo,
ich würde mich hier völlig hausbacken über kleine Potenzen und fröhliches Dividieren mit Rest zum Ergebnis vorwurschteln.
Beginnen würde ich mit [mm] 59^2 [/mm] und dann nutzen
[mm] 59^{39}=((59^2)^6*59)^3.
[/mm]
Ich will nicht ausschließen, daß es für diejenigen, die sich in der Zahlentheorie auskennen, Raffinierteres gibt, aber zum Ziel kommt man auf meinem Weg.
LG Angela
|
|
|
| |
|
| Status: |
(Frage) beantwortet | | Datum: | 14:46 Fr 08.06.2012 | | Autor: | sissile |
> $ [mm] 59^39=(59^2)^6\cdot{}59. [/mm] $
Das stimmt doch nicht?
Nicht eher [mm] 59^{39} [/mm] = [mm] (59^{2})^{19} [/mm] * 59
?
|
|
|
| |
|
Hallo sissile,
> > [mm]59^39=(59^2)^6\cdot{}59.[/mm]
> Das stimmt doch nicht?
Nein, da war wohl noch was vergessen.
> Nicht eher [mm]59^{39}[/mm] = [mm](59^{2})^{19}[/mm] * 59
> ?
Mühsam. Ich denke, Angela meinte
[mm] 59^{39}=\left((59^2)^6*59\right)^3
[/mm]
Oder so. Hängt manchmal auch von den Zwischenergebnissen ab. Besonders, wenn sie klein und überschaubar sind, finden sich manchmal nettere Zerlegungen, aber die hier ist doch schonmal ganz gut, zumal ja auch noch 6=2*3 ist...
Grüße
reverend
|
|
|
| |
|
| Status: |
(Frage) beantwortet | | Datum: | 15:06 Fr 08.06.2012 | | Autor: | sissile |
$ [mm] 59^{39}=\left((59^2)^6\cdot{}59\right)^3 [/mm] $ [mm] \equiv (5^6*59)^3 =((5^3)^2*59)^3 \equiv (46^2*59)^3 \equiv (46^2*59)^3 \equiv (62*59)^3 \equiv 24^3 \equiv [/mm] -1 (79)
-> 59 kein quadratischer Rest modulo 79.
|
|
|
| |
|
Hallo nochmal,
> [mm]59^{39}=\left((59^2)^6\cdot{}59\right)^3[/mm] [mm]\equiv (5^6*59)^3 =((5^3)^2*59)^3 \equiv (46^2*59)^3 \equiv (46^2*59)^3 \equiv (62*59)^3 \equiv 24^3 \equiv[/mm]
> -1 (79)
> -> 59 kein quadratischer Rest modulo 79.
So ist es.
hast Du meinen etwas aus dem Baum ausbrechenden Beitrag gelesen? Das Ergebnis kann man noch schneller haben.
Grüße
rev
|
|
|
| |
|
Hallo sissile,
manchmal gibt es auch noch schnellere Wege, so hier. Das ist bei Klausuraufgaben oft so, man soll ja gar nicht ewig herumrechnen.
Wenn 59 ein quadratischer Rest mod 79 ist, dann ist a*59 mod 79 auch ein QR, sofern a selbst ein QR ist. Es lohnt sich darum oft, mal die kleineren QR hier für a einzusetzen, und siehe:
a=4 (ganz offenbar immer ein QR) liefert hier [mm] 4*59\equiv -1\mod{79}.
[/mm]
Nun bleibt zu überprüfen, ob -1 hier QR ist, aber das fällt ja leicht. Man muss ja nur noch (-1)^39 [mm] \mod{79} [/mm] bestimmen. 
Grüße
reverend
|
|
|
| |
|
| Status: |
(Frage) beantwortet | | Datum: | 15:18 Fr 08.06.2012 | | Autor: | sissile |
Hallo
> Wenn 59 ein quadratischer Rest mod 79 ist, dann ist a*59 mod 79 auch ein QR, sofern a selbst ein QR ist. Es lohnt sich darum oft, mal die kleineren QR hier für a einzusetzen, und siehe:
> a=4 (ganz offenbar immer ein QR) liefert hier $ [mm] 4\cdot{}59\equiv -1\mod{79}. [/mm] $
> Nun bleibt zu überprüfen, ob -1 hier QR ist, aber das fällt ja leicht. Man muss ja nur noch (-1)^39 $ [mm] \mod{79} [/mm] $ bestimmen.
-> da kann man ja auch den ersten ergänzungssatz verwenden.
Ich verstehe jedoch nicht, wieso man das so machen darf?
z.B bei bsp b)
[mm] x^2 \equiv [/mm] 17 (mod 41)
liefert hier 4* [mm] 17\equiv [/mm] 27 [mm] \mod{41}
[/mm]
nun noch auszurechnen [mm] (27)^{20} [/mm] (mod 41)
Oder ist hier diese methode nicht hilfreich? und man kann gleich anfang zu euler übergehen?
|
|
|
| |
|
Hallo,
> Wenn 59 ein quadratischer Rest mod 79 ist, dann ist a*59
> mod 79 auch ein QR, sofern a selbst ein QR ist. Es lohnt
> sich darum oft, mal die kleineren QR hier für a
> einzusetzen, und siehe:
> > a=4 (ganz offenbar immer ein QR) liefert hier
> [mm]4\cdot{}59\equiv -1\mod{79}.[/mm]
>
> > Nun bleibt zu überprüfen, ob -1 hier QR ist, aber das
> fällt ja leicht. Man muss ja nur noch (-1)^39 [mm]\mod{79}[/mm]
> bestimmen.
> -> da kann man ja auch den ersten ergänzungssatz
> verwenden.
Ja, kann man auch, aber man braucht ihn doch gar nicht.
> Ich verstehe jedoch nicht, wieso man das so machen darf?
Wenn der Modul prim ist, QR Quadratischer Rest bedeutet und NQ Nicht-Quadratischer Rest, dann gilt:
QR*QR=QR
NQ*QR=NQ
QR*NQ=NQ
NQ*NQ=QR
Wir brauchen hier nur die erste Gleichung (eigentlich natürlich eine Äquivalenz).
> z.B bei bsp b)
> [mm]x^2 \equiv[/mm] 17 (mod 41)
> liefert hier 4* [mm]17\equiv[/mm] 27 [mm]\mod{41}[/mm]
> nun noch auszurechnen [mm](27)^{20}[/mm] (mod 41)
> Oder ist hier diese methode nicht hilfreich?
Auf den ersten Blick nicht, es sei denn Du schreibst [mm] 27^{20}=3^{60}=(3^4)^{15}\equiv (-1)^{15}\mod{41}
[/mm]
Grüße
reverend
> und man kann
> gleich anfang zu euler übergehen?
|
|
|
| |
|
| Status: |
(Frage) beantwortet | | Datum: | 17:03 Fr 08.06.2012 | | Autor: | sissile |
okay danke, also wieder kein Quadaratische Rest
Mein letztes Bsp ist c)
[mm] x^2 \equiv [/mm] 29 (mod 101)
[mm] 29^{50} [/mm] = [mm] (29^2)^{25} \equiv (40)^{25} [/mm] = [mm] (40^2)^{12} [/mm] * 40 [mm] \equiv (-1)^{12} [/mm] * 40 = 40 (mod 101)
-> kein Quadratischer Rest
|
|
|
| |
|
Hallo sissile,
da ist Dir ein Rechenfehler unterlaufen:
> okay danke, also wieder kein Quadaratische Rest
(das war ja noch zu vorher und stimmt so)
> Mein letztes Bsp ist c)
>
> [mm]x^2 \equiv[/mm] 29 (mod 101)
> [mm]29^{50}[/mm] = [mm](29^2)^{25} \equiv (40)^{25}[/mm] = [mm](40^2)^{12}[/mm] * 40
> [mm]\red{\equiv} (-1)^{12}[/mm] * 40 = 40 (mod 101)
Dieser rot markierte Übergang stimmt nicht. [mm] 40^2\not\equiv -1\mod{101}
[/mm]
Wie Du sicher weißt, gibt es ja überhaupt nur drei mögliche Endergebnisse: -1,0,+1.
> -> kein Quadratischer Rest
Das ist zwar das richtige Ergebnis, aber nicht auf dem richtigen Weg erhalten.
Wenn man übrigens keine geschickte Zerlegung des Exponenten findet, dann empfiehlt sich immer die Umrechnung in eine Binärzahl.
[mm] 50=2^5+2^4+2^1, [/mm] und damit kann man ein bisschen fortgesetzt quadrieren:
[mm] 29^1\equiv \blue{29}\mod{101}
[/mm]
[mm] 29^2\equiv \blue{33}\mod{101}
[/mm]
[mm] 29^4\equiv (29^2)^2\equiv 33^2\equiv \blue{79}\mod{101}
[/mm]
[mm] 29^8\equiv (29^4)^2\equiv 79^2\equiv \blue{80}\mod{101}
[/mm]
[mm] 29^{16}\equiv (29^8)^2\equiv 80^2\equiv \blue{37}\mod{101}
[/mm]
[mm] 29^{32}\equiv (29^{16})^2\equiv 37^2\equiv \blue{56}\mod{101}
[/mm]
Dann ist [mm] 29^{50}\equiv \blue{56*37*33}\equiv -1\mod{101}
[/mm]
Also: kein QR.
Die "Binärmethode" sieht aufwändig aus, ist es aber ganz und gar nicht. Vor allem bei großen Exponenten ist sie schnell und vor allem für einen selbst übersichtlich.
Grüße
reverend
|
|
|
| |
|
| Status: |
(Frage) beantwortet | | Datum: | 20:13 Fr 08.06.2012 | | Autor: | sissile |
Hallo, ich verstehe nicht ganz wie du das gerechnet hast!
> $ [mm] 50=2^5+2^4+2^1, [/mm] $
okay klar
> und damit kann man ein bisschen fortgesetzt quadrieren:
> $ [mm] 29^1\equiv \blue{29}\mod{101} [/mm] $
> $ [mm] 29^2\equiv \blue{33}\mod{101} [/mm] $
> $ [mm] 29^4\equiv (29^2)^2\equiv 33^2\equiv \blue{79}\mod{101} [/mm] $
> $ [mm] 29^8\equiv (29^4)^2\equiv 79^2\equiv \blue{80}\mod{101} [/mm] $
> $ [mm] 29^{16}\equiv (29^8)^2\equiv 80^2\equiv \blue{37}\mod{101} [/mm] $
> $ [mm] 29^{32}\equiv (29^{16})^2\equiv 37^2\equiv \blue{56}\mod{101} [/mm] $
> Dann ist $ [mm] 29^{50}\equiv \blue{56\cdot{}37\cdot{}33}\equiv -1\mod{101} [/mm] $
> Also: kein QR.
Wie hast du das mit Binärzahlen gemacht??
LG
|
|
|
| |
|
Hallo,
na, Du kennst doch Binärzahlen, oder? Umrechnung am einfachsten mit dem Euklidischen Algorithmus.
Jedenfalls ist [mm] 50_{dez}=110010_{bin}, [/mm] also eben [mm] 2^5+2^4+2^1.
[/mm]
Verstehst Du das mit dem Quadrieren denn?
lg
rev
|
|
|
| |
|
| Status: |
(Frage) beantwortet | | Datum: | 20:23 Fr 08.06.2012 | | Autor: | sissile |
Hallo, die Darstellung verstehe ich schon. Ich scheitere eher am quadrieren. Weil ich weiß nicht wie du die binear-form quadrierst!
LG
|
|
|
| |
|
Hi,
> Hallo, die Darstellung verstehe ich schon. Ich scheitere
> eher am quadrieren. Weil ich weiß nicht wie du die
> binear-form quadrierst!
Dann lies meinen Post nochmal, ich habs sehr detailliert vorgerechnet.
lg
rev
|
|
|
|
