Eulers kriterium

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}$

Bevis

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.