De kwadratische reciprociteitswet kan gebruikt worden bij het berekenen van Legendresymbolen.
Een probleem daarbij—als het om grote getallen gaat—is dat voor het berekenen van
het
getal
ontbonden moet worden. Dat is echter geheel te vermijden door het Legendresymbool uit te
breiden tot het meer algemene Jacobisymbool en te laten zien dat daar analoge rekenregels
voor gelden.
12.29 Definitie. Laten
en
gehele getallen zijn met
oneven en positief. We definiëren het Jacobisymbool
door
Ofwel: als
(met
priemgetallen), dan
Omdat
oneven is, zijn alle priemfactoren
ook oneven. (Voor
zijn er
priemfactoren en is het product .)
Carl Jacobi (Potsdam 1804 – Berlijn 1851)
Jacobi leverde al op jonge leeftijd belangrijke bijdragen aan de getaltheorie en later aan de
theorieën van elliptische integralen en differentiaalvergelijkingen. De ‘Jacobiaan’ in de
theorie van functies van meer variabelen is naar hem genoemd; hij had er uitvoerig over
geschreven, maar bij Cauchy trad dit begrip al eerder op.
12.34Voorbeeld. We gaan na of een
kwadraatrest is modulo het priemgetal .
Dus is het een kwadraatrest.
Algoritme
De in bovenstaand voorbeeld gevolgde methode lijkt op het algoritme van Euclides.
Hier begin je met twee getallen waarvan je weet dat hun grootste gemene deler
is en verder is het nodig tussentijds factoren
eruit te halen. Het gaat erom bij iedere stap het teken aan te passen.