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:

( a p ) ≡ a p − 1 2   mod ⁡   p {\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 x2 ≡ a mod p en lösning. Kalla denna lösning x0. Nu gäller att:

a p − 1 2 ≡ ( x 0 2 ) p − 1 2   mod ⁡   p {\displaystyle a^{\frac {p-1}{2}}\equiv (x_{0}^{2})^{\frac {p-1}{2}}\ \operatorname {mod} \ p}
≡ x 0 p − 1   mod ⁡   p {\displaystyle \equiv x_{0}^{p-1}\ \operatorname {mod} \ p}
≡ 1   mod ⁡   p {\displaystyle \equiv 1\ \operatorname {mod} \ p} (Fermats lilla sats ty p delar ej x0.)
≡ ( a p ) mod ⁡   p {\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 = i2 ≡ 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:

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

vilket ger

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

och

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

Satsen är härmed bevisad.