Aufgabe zu quadratische Reste, Legendre Symbol
-
Ich habe ein Beispiel zu der Berechnung des Legendre Symbol das ich nicht so Recht verstehe.
Das Legendre Symbol ist so definiert dass sofern b eine Primzahl ist dann gilt (a/b)=1 wenn a ein quadratische Rest modulo b ist und (a/b)=-1 wenn a kein quadratischer Rest modulo b ist.
Beispiel: a=1993, b=65537=2^16+1
(1993/65537)=(65537/1993)=(1761/1993)=(232/1761)=(2/1761)^3(29/1761)=(1761/29)=(21/29)=(3/29)(7/29)=(29/3)(29/7)=(2/3)(1/7)=(2/3)=-1
Es gilt (ab/p)=(a/p)(b/p). Ich weis aber nicht warum (a/b)=(b/a) sein soll.
-
Ich würde vermuten, daß es was mit
https://en.wikipedia.org/wiki/Legendre_symbol#Legendre_symbol_and_quadratic_reciprocity
zu tun hat.
-
(a/b)=1 gilt genau dann, wenn mindestens eines von a,b == 1 (mod 4) ist.
-
Der erste Schritt (1993/65537)=(65537/1993) verstehe ich nicht. Der zweite Schritt (65537/1993)=(1761/1993) ist einfach die Modulo Operation.
@Zahlentheoretiker:
Inwiefern nutzt mir diese Angabe?
-
Habe es herausgefunden.
Wenn mindestens eine Zahl von a, b kongruent 1 mod 4 ist, sind x^2 = a mod b und x^2=b mod a beide lösbar oder beide nicht lösbar.
-
Zahlentheoretiker schrieb:
(a/b)=1 gilt genau dann, wenn mindestens eines von a,b == 1 (mod 4) ist.
Sorry, das sollte heißen: (a/b)=(b/a) gilt genau dann, wenn mindestens eines von a,b == 1 (mod 4) ist.