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:
- <math>\left(\frac{a}{p}\right) \equiv a^{\frac{p-1}{2}} \ \operatorname{mod} \ p</math>
Bevis
[redigera | redigera wikitext]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:
- <math>a^{\frac{p-1}{2}}\equiv(x_0^2)^{\frac{p-1}{2}}\ \operatorname{mod} \ p</math>
- <math>\equiv x_0^{p-1}\ \operatorname{mod}\ p</math>
- <math>\equiv 1 \ \operatorname{mod}\ p</math> (Fermats lilla sats ty p delar ej x0.)
- <math>\equiv \left(\frac{a}{p}\right) \operatorname{mod}\ p</math>
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:
- <math>(p-1)!\equiv a^{\frac{p-1}{2}}\ \operatorname{mod}\ p</math>
vilket ger
- <math>-1\equiv a^{\frac{p-1}{2}}\ \operatorname{mod}\ p</math> (Wilsons sats)
och
- <math>\left(\frac{a}{p}\right) \equiv a^{\frac{p-1}{2}} \ \operatorname{mod} \ p</math>
Satsen är härmed bevisad.