Quadratischer Rest < Zahlentheorie < Algebra+Zahlentheo. < Hochschule < Mathe < Vorhilfe
|
| Status: |
(Frage) beantwortet  | | Datum: | 06:52 Mo 25.01.2010 | | Autor: | Unk |
| Aufgabe | | Welche der Zahlen 281, 291, 301, 311 sind quadratische Reste modulo 2008? |
Hallo,
ich weiß nicht so recht, wie ich hier weiterkomme, da 2008 keine Primzahl ist, sonst hätte ich einfach das Legendre-Symbol draufgehauen.
Was ich bis jetzt gemacht habe, ist das Jacobi-Symbol angewendet. Die notwendige Bedingung damit x quadratischer Rest ist, ist ja, dass das Jacobi-Symbol eine 1 liefert. Wenn das schonmal nicht passt, so ist x kein quadratischer Rest. 281 scheidet dann schonmal aus, da das Jacobi Symbol eine -1 liefert. Nun ist ja aber die Tatsache, dass wenn das Jacobi Symbol für x eine 1 liefert noch nicht ausreichend dafür, dass x wirklich quadratischer rest ist.
Da muss es doch dann noch einen (einfachen) Trick geben, wie man das praktisch sofort sieht oder? ich könnte zwar alle Zahlen [mm] \leq [/mm] 2008 quadrieren und dann mal nachschauen, aber das missfällt mir doch sehr...
|
|
| |
|
Hallo Unk,
2008=8*251. Die angegebenen Zahlen müssen also sowohl quadratische Reste [mm] \mod{8} [/mm] als auch [mm] \mod{251} [/mm] sein.
[mm] \mod{8} [/mm] sind ja nur 0,1,4 quadratische Reste.
Es kommt damit nur 281 als Lösung in Frage.
Nun ist aber noch zu prüfen, ob [mm] 281\equiv 30\mod{251} [/mm] ein quadratischer Rest ist.
(Die Antwort ist: nein).
lg
reverend
|
|
|
|
