quadratischer Rest < Zahlentheorie < Algebra+Zahlentheo. < Hochschule < Mathe < Vorhilfe
|
| Status: |
(Frage) beantwortet  | | Datum: | 14:52 Mi 08.06.2011 | | Autor: | katrin10 |
| Aufgabe | 1. Es sei p eine Primzahl mit p [mm] \equiv [/mm] 3 mod 4 und a ein Quadrat mod p. Zeige, dass [mm] x=a^{(p+1)/4} [/mm] eine Lösung von [mm] x^2 \equiv [/mm] a mod p ist.
2. Zeige, dass a = 83 ein quadratischer Rest mod n=361 ist und finde eine Lösung von [mm] x^2 \equiv [/mm] a mod 361.
3. Es sei p eine Primzahl mit p [mm] \equiv [/mm] 5 mod 8 und a ein Quadrat mod p. Finde einen expliziten Ausdruck für eine Lösung der Gleichung [mm] x^2 [/mm] kongruent a mod p. |
Hallo,
bei der ersten Teilaufgabe habe ich p als p=3+4q geschrieben und dann für [mm] x^2 a^{2(q+1)} [/mm] erhalten. Nun muss ich zeigen, dass [mm] a^{2(q+1)} \equiv [/mm] a mod p ist, was gilt, falls a eine Primitivwurzel mod p ist.
Bei der zweiten Aufgabe habe ich gezeigt, dass es sich um einen quadratischen Rest handelt. Da 83+361q für ein q \ IZ eine Primzahl sein muss, habe ich dann ausgetestet, wann eine Quadratzahl herauskommt und als Lösung für x 122 erhalten. Allerdings frage ich mich, ob es auch einen mathematischeren Weg gibt.
Bei der letzten Aufgabe habe ich bisher noch keine Idee.
Über einen Tipp wäre ich sehr dankbar.
Katrin
|
|
| |
|
| Status: |
(Antwort) fertig  | | Datum: | 15:02 Mi 08.06.2011 | | Autor: | abakus |
> 1. Es sei p eine Primzahl mit p [mm]\equiv[/mm] 3 mod 4 und a ein
> Quadrat mod p. Zeige, dass [mm]x=a^{(p+1)/4}[/mm] eine Lösung von
> [mm]x^2 \equiv[/mm] a mod p ist.
> 2. Zeige, dass a = 83 ein quadratischer Rest mod n=361 ist
> und finde eine Lösung von [mm]x^2 \equiv[/mm] a mod 361.
> 3. Es sei p eine Primzahl mit p [mm]\equiv[/mm] 5 mod 8 und a ein
> Quadrat mod p. Finde einen expliziten Ausdruck für eine
> Lösung der Gleichung [mm]x^2[/mm] kongruent a mod p.
> Hallo,
> bei der ersten Teilaufgabe habe ich p als p=3+4q
> geschrieben und dann für [mm]x^2 a^{2(q+1)}[/mm] erhalten. Nun muss
> ich zeigen, dass [mm]a^{2(q+1)} \equiv[/mm] a mod p ist, was gilt,
> falls a eine Primitivwurzel mod p ist.
> Bei der zweiten Aufgabe habe ich gezeigt, dass es sich um
> einen quadratischen Rest handelt. Da 83+361q für ein q \
> IZ eine Primzahl sein muss, habe ich dann ausgetestet, wann
> eine Quadratzahl herauskommt und als Lösung für x 122
> erhalten. Allerdings frage ich mich, ob es auch einen
> mathematischeren Weg gibt.
Weiß ich auch nicht. Mir fällt nur auf, dass [mm] 361=19^2 [/mm] ist.
Bringt das irgendetwas?
Gruß Abakus
> Bei der letzten Aufgabe habe ich bisher noch keine Idee.
> Über einen Tipp wäre ich sehr dankbar.
> Katrin
|
|
|
| |
|
| Status: |
(Antwort) fertig | | Datum: | 15:40 Mi 08.06.2011 | | Autor: | statler |
Hi!
> 2. Zeige, dass a = 83 ein quadratischer Rest mod n=361 ist
> und finde eine Lösung von [mm]x^2 \equiv[/mm] a mod 361.
Du kannst die Kongruenz erstmal mod 19 betrachten und lösen. Also [mm] x^2 \equiv [/mm] 7 mod 19 gibt x [mm] \equiv [/mm] 8 und x [mm] \equiv [/mm] 11. Jetzt benutzt du das Newtonsche Näherungsverfahren (auch wenn es nicht so aussieht). Du setzt y = 8 + 19z. Dann ist [mm] y^2 [/mm] = 64 + 304z + [mm] 19^{2}z^2 \equiv [/mm] 64 + 304z mod [mm] 19^2. [/mm] Aus dieser Gl. kannst du z mod 19 bestimmen:
64 + 304z [mm] \equiv [/mm] 83 [mm] \gdw [/mm] 304z [mm] \equiv [/mm] 19 mod [mm] 19^2
[/mm]
Jetzt durch 19 teilen: 16z [mm] \equiv [/mm] 1 mod 19 [mm] \gdw [/mm] z [mm] \equiv [/mm] 6
Also 8 + 6 [mm] $\cdot$ [/mm] 19 und 11 + 6 [mm] $\cdot$ [/mm] 19 Lösungen mod 361. Die erste hattest du auch.
Gruß aus HH-Harburg
Dieter
|
|
|
|
