Legendre-Symbol ausrechnen

Question

ich brauche Hilfe beim ausrechnen vom Legendre Symbol insbesondere bei größeren Zahlen.

Denn ich habe zwar alle Definitionen und Sätze, kann diese aber nicht anwenden.

Dazu würde ich gerne wissen wie man bei (-20/31) auf -1 und bei (42/47) auf 1 kommt.

Answer 1

z.B. bei dem zweiten kannst du verwenden

(42/47) =  (6/47) *  (7/47)

6 und 7 sind beides quadratische Reste mod 47

denn z.B.  ist 2+47 = 49 und das ist ja eine bekannte Quadratzahl

Bei der 6 findest du durch jeweiliges addieren von 47 auch relativ schnell

6      53    100   auch eine Quadratzahl.

Also sind  (6/47) = 1   und    (7/47) = 1

und damit alles klar.