Jacobisymbol (Legendresymbol) < Zahlentheorie < Algebra+Zahlentheo. < Hochschule < Mathe < Vorhilfe
|
Hallo,
ich habe mal eine Frage zum Jacobi-Symbol. Wir haben gelernt, dass gilt:
Wenn [mm] (\bruch{a}{m}) [/mm] = 1 mit m ungerade, aber nicht prim kann man nicht schlussfolgern, dass quadratischer Rest. Dafür müssten die Terme [mm] (\bruch{a}{p_i}) [/mm] für die Primfaktoren p von m jeweils einzeln +1 ergeben.
Ist mir soweit auch klar. Meine Frage jetzt: Wenn die einzelnen Terme, also [mm] (\bruch{a}{p_i}) [/mm] jetzt für alle p = -1 sind, ist dann a Quadratischer Nichtrest modulo m oder kann man dazu nichts sagen? Weil [mm] (\bruch{a}{m}) [/mm] wäre ja dann 1, aber de facto kein Quadratischer Rest. Und was ist mit dem Fall, dass ein Term [mm] (\bruch{a}{p_1})= [/mm] - 1 wäre und [mm] (\bruch{a}{p_2})= [/mm] 1 ? Was kann ich dann über mein a modulo m sagen? QR oder QNR?
Vielen Dank,
liebe Grüße,
Julia
|
|
| |
|
| Status: |
(Antwort) fertig  | | Datum: | 10:33 Sa 24.07.2010 | | Autor: | felixf |
Moin Julia!
> ich habe mal eine Frage zum Jacobi-Symbol. Wir haben
> gelernt, dass gilt:
> Wenn [mm](\bruch{a}{m})[/mm] = 1 mit m ungerade, aber nicht prim
> kann man nicht schlussfolgern, dass quadratischer Rest.
> Dafür müssten die Terme [mm](\bruch{a}{p_i})[/mm] für die
> Primfaktoren p von m jeweils einzeln +1 ergeben.
Genau.
> Ist mir soweit auch klar. Meine Frage jetzt: Wenn die
> einzelnen Terme, also [mm](\bruch{a}{p_i})[/mm] jetzt für alle p =
> -1 sind, ist dann a Quadratischer Nichtrest modulo m oder
> kann man dazu nichts sagen?
Es reicht schon, wenn eins der [mm] $(\frac{a}{p_i}) [/mm] = -1$ ist, damit es kein quadratischer Rest modulo $m$ ist.
> Weil [mm](\bruch{a}{m})[/mm] wäre ja
> dann 1, aber de facto kein Quadratischer Rest.
Ja.
> Und was ist
> mit dem Fall, dass ein Term [mm](\bruch{a}{p_1})=[/mm] - 1 wäre und
> [mm](\bruch{a}{p_2})=[/mm] 1 ? Was kann ich dann über mein a modulo
> m sagen? QR oder QNR?
Es ist dann ein quadratischer Nichtrest: falls es ein quadratischer Rest waer, also es ein $x$ gaeb mit [mm] $x^2 \equiv [/mm] a [mm] \pmod{m}$, [/mm] dann muesste auch [mm] $x^2 \equiv [/mm] a [mm] \pmod{p_1}$ [/mm] geben, also $a$ ein QR modulo [mm] $p_1$ [/mm] sein -- was wegen [mm] $(\frac{a}{p_1}) [/mm] = -1$ nicht geht.
LG Felix
|
|
|
| |
|
Hey!
Super, danke! Das heißt, dass ich bei der Aussage: "Das Produkt zweier Quadratischer Nichtreste ist wieder Quadratischer Nichtrest ", richtig ankreuzen kann, ne? :) Und es wäre auch richtig: Das Produkt eines Quadratischen Restes mit einem Quadratischen Nichtrest ist ein Quadratischer Nichtrest, oder?
Lg, Julia
|
|
|
| |
|
Hallo Julia,
> Hey!
>
> Super, danke! Das heißt, dass ich bei der Aussage: "Das
> Produkt zweier Quadratischer Nichtreste ist wieder
> Quadratischer Nichtrest ", richtig ankreuzen kann, ne? :)
Besser nicht, das ist nämlich falsch!
Es ist das Produkt zweier quadrat. Reste wieder ein quadr. Rest, aber das Produkt zweier quadr. Nicht-Reste ist ein quadr. Rest!
> Und es wäre auch richtig: Das Produkt eines Quadratischen
> Restes mit einem Quadratischen Nichtrest ist ein
> Quadratischer Nichtrest, oder? ![[ok]](/images/smileys/ok.gif "[ok]")
>
> Lg, Julia
Gruß
schachuzipus
|
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig  | | Datum: | 11:37 Sa 24.07.2010 | | Autor: | felixf |
Moin!
> > Super, danke! Das heißt, dass ich bei der Aussage: "Das
> > Produkt zweier Quadratischer Nichtreste ist wieder
> > Quadratischer Nichtrest ", richtig ankreuzen kann, ne? :)
>
> Besser nicht, das ist nämlich falsch!
>
> Es ist das Produkt zweier quadrat. Reste wieder ein quadr.
> Rest, aber das Produkt zweier quadr. Nicht-Reste ist ein
> quadr. Rest!
Vorsicht! Das gilt nur modulo einer Primzahl! Modulo einer zusammengesetzten Zahl kann das Ergebnis sowohl ein QR oder ein QNR sein.
Das einzige, was das Jacobi-Symbol gesichert aussagt, ist: wenn [mm] $(\frac{a}{m}) [/mm] = -1$ ist, dann ist $a$ kein quadratischer Rest modulo $m$.
> > Und es wäre auch richtig: Das Produkt eines Quadratischen
> > Restes mit einem Quadratischen Nichtrest ist ein
> > Quadratischer Nichtrest, oder?
>
Ja, das stimmt immer.
LG Felix
|
|
|
| |
|
Hey!
Also nochmal langsam.
Folgende Fragen:
1) Seien [mm] p_1, p_2 [/mm] Primzahlen und [mm] (\bruch{a}{p_1}) [/mm] = -1 und [mm] (\bruch{a}{p_2}) [/mm] = -1 , ist dann jetzt das Produkt, also [mm] (\bruch{a}{m}) [/mm] mit m= [mm] p_1*p_2 [/mm] Quadratischer Nichtrest? (Ich hatte das jetzt so verstanden, wenn das falsch ist, denk ich mal nach Felix' Aussage, dass es BEIDES sein kann, also manchmal halt nen QR und manchmal QNR).
2) Sei jetzt [mm] (\bruch{a}{m_2}) [/mm] = -1 und [mm] (\bruch{a}{m_2}) [/mm] = -1 mit m zusammengesetzte Zahl, dann gilt, dass das Produkt [mm] (\bruch{a}{m_1*m_2}) [/mm] sowohl QR als auch QNR sein kann?
Da ich ein wenig durcheinander bin , wärs cool, wenn einer diese beiden Fragen nochmal kurz beantworten könnte!
Liebe Grüße und vielen Dank,
Julia
|
|
|
| |
|
| Status: |
(Antwort) fertig | | Datum: | 12:11 Sa 24.07.2010 | | Autor: | felixf |
Moin!
> Also nochmal langsam.
> Folgende Fragen:
>
> 1) Seien [mm]p_1, p_2[/mm] Primzahlen und [mm](\bruch{a}{p_1})[/mm] = -1 und
> [mm](\bruch{a}{p_2})[/mm] = -1 , ist dann jetzt das Produkt, also
> [mm](\bruch{a}{m})[/mm] mit m= [mm]p_1*p_2[/mm] Quadratischer Nichtrest?
In diesem Fall ist es immer ein QNR. (Das waer auch der Fall, wenn [mm] $p_1$ [/mm] und [mm] $p_2$ [/mm] keine Primzahlen waeren.)
> (Ich hatte das jetzt so verstanden, wenn das falsch ist, denk
> ich mal nach Felix' Aussage, dass es BEIDES sein kann, also
> manchmal halt nen QR und manchmal QNR).
In der Diskussion mit schachuzipus ging es um [mm] $(\frac{a}{m}) (\frac{b}{m})$ [/mm] und nicht um [mm] $(\frac{a}{m}) (\frac{a}{m'})$.
[/mm]
> 2) Sei jetzt [mm](\bruch{a}{m_2})[/mm] = -1 und [mm](\bruch{a}{m_2})[/mm] =
> -1 mit m zusammengesetzte Zahl, dann gilt, dass das Produkt
> [mm](\bruch{a}{m_1*m_2})[/mm] sowohl QR als auch QNR sein kann?
Es ist immer ein QNR.
LG Felix
|
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig | | Datum: | 12:21 Sa 24.07.2010 | | Autor: | BieneJulia |
Ah okay. Ja gut, dann war das ein Missverständnis!
Liebe Grüße und danke,
Julia
|
|
|
| |
|
Das ist mir dann doch noch nicht klar. Wieso ist das Produkt zweier Quadratischer Nichtreste wieder ein Quadratischer Rest? Also wenn [mm] (\bruch{a}{p_1}) [/mm] = -1 und [mm] (\bruch{a}{p_2}) [/mm] = -1, hatten wir ja vorher geklärt, das zwar [mm] (\bruch{a}{p_1*p_2 }) [/mm] = 1 gilt, aber es KEIN quadratischer Rest ist (zumindest sein muss, da gibts ja Gegenbeispiele). Meine erste Frage (weiter oben)war ja, ob man dann schließen kann, dass [mm] (\bruch{a}{m}) [/mm] mit [mm] m=p_1*p_2 [/mm] ein Quadratischer Nichtrest ist (Quadratischer Rest muss er ja zumindest nicht sein) oder ob man daraus nichts schließen kann (das heißt, es kann entweder QR oder QNR sein). Ich hatte Felix so verstanden, dass es ein QNR ist . Oder liegt das Problem bei der "Produktbildung" ?
Lg, Julia
|
|
|
| |
|
| Status: |
(Antwort) fertig | | Datum: | 12:24 Sa 24.07.2010 | | Autor: | felixf |
Hallo Julia
> Das ist mir dann doch noch nicht klar. Wieso ist das
> Produkt zweier Quadratischer Nichtreste wieder ein
> Quadratischer Rest?
Modulo einer Primzahl ist das so, weil $a$ modulo $p$ genau dann ein QR ist, wenn [mm] $(\frac{a}{p}) [/mm] = 1$ ist.
> Also wenn [mm](\bruch{a}{p_1})[/mm] = -1 und
> [mm](\bruch{a}{p_2})[/mm] = -1, hatten wir ja vorher geklärt, das
> zwar [mm](\bruch{a}{p_1*p_2 })[/mm] = 1 gilt, aber es KEIN
> quadratischer Rest ist (zumindest sein muss, da gibts ja
> Gegenbeispiele).
Vorsicht. Oben hast du von etwas ganz anderem geredet als hier.
> Meine erste Frage (weiter oben)war ja, ob
> man dann schließen kann, dass [mm](\bruch{a}{m})[/mm] mit [mm]m=p_1*p_2[/mm]
> ein Quadratischer Nichtrest ist (Quadratischer Rest muss er
> ja zumindest nicht sein) oder ob man daraus nichts
> schließen kann (das heißt, es kann entweder QR oder QNR
> sein). Ich hatte Felix so verstanden, dass es ein QNR ist .
> Oder liegt das Problem bei der "Produktbildung" ?
Wenn $a$ modulo einer Primzahl $p$ ein QNR ist und $m$ ein Vielfaches von $p$ ist, dann ist $a$ auch QNR modulo $m$.
LG Felix
|
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig | | Datum: | 12:36 Sa 24.07.2010 | | Autor: | BieneJulia |
Ja, danke - dann hab ichs jetzt verstanden.
Habe irgendwie Produkt geschrieben, obwohl ich ja immer vom selben a mod p bzw. m gesprochen hab und nicht von a mod p und b mod p.
Lg, Julia
|
|
|
|
