Eulers kriterium

Den här artikeln behöver källhänvisningar för att kunna verifieras. (2022-09) Åtgärda genom att lägga till pålitliga källor (gärna som fotnoter). Uppgifter utan källhänvisning kan ifrågasättas och tas bort utan att det behöver diskuteras på diskussionssidan.

Eulers kriterium kallas inom talteorin en speciell egenskap hos Legendresymbolen som i vissa fall kan användas till att beräkna denna, men som framförallt har ett stort teoretiskt värde för att härleda ännu enklare metoder för denna beräkning.

Eulers kriterium säger att om p är ett udda primtal och a är ett heltal som inte är delbart med p så gäller:

${\displaystyle \left({\frac {a}{p}}\right)\equiv a^{\frac {p-1}{2}}\ \operatorname {mod} \ p}$

Vi tecknar Legendresymbolen i detta bevis även som (a/p). Antag först att (a/p) = 1. Då har enligt definitionen på Legendresymbolen kongruensen x² ≡ a mod p en lösning. Kalla denna lösning x₀. Nu gäller att:

${\displaystyle a^{\frac {p-1}{2}}\equiv (x_{0}^{2})^{\frac {p-1}{2}}\ \operatorname {mod} \ p}$

${\displaystyle \equiv x_{0}^{p-1}\ \operatorname {mod} \ p}$

${\displaystyle \equiv 1\ \operatorname {mod} \ p}$ (Fermats lilla sats ty p delar ej x₀.)

${\displaystyle \equiv \left({\frac {a}{p}}\right)\operatorname {mod} \ p}$

Antag sedan att (a/p) = -1. För varje heltal i mellan 1 och p-1 finns ett unikt annat heltal j mellan 1 och p-1 så att ij ≡ a mod p, eftersom dessa linjära kongruenser alla är lösbara. Vidare kan i och j inte vara samma tal, eftersom då ij = i² ≡ a mod p och a är en kvadratisk rest modulo p och vi får (a/p) = 1 som motsäger förutsättningen. Alltså kan heltalen mellan 1 och p-1 paras ihop till (p-1)/2 par som alla har produkten a modulo p. Om vi multiplicerar samman dessa heltal får vi:

${\displaystyle (p-1)!\equiv a^{\frac {p-1}{2}}\ \operatorname {mod} \ p}$

vilket ger

${\displaystyle -1\equiv a^{\frac {p-1}{2}}\ \operatorname {mod} \ p}$ (Wilsons sats)

och

${\displaystyle \left({\frac {a}{p}}\right)\equiv a^{\frac {p-1}{2}}\ \operatorname {mod} \ p}$

Satsen är härmed bevisad.