Mostra la font per a Criteri d'Euler

En [[Matemàtiques]], el '''criteri d'Euler''' és utilitzat per a calcular [[residu quadràtic|residus quadràtics]].

== Definició ==
Sigui ''p'' > 2 un nombre [[primer]]. Llavors ''x'' és un residu quadràtic mòdul ''p'' si i només si
: <math> X^{(p-1)/2}\equiv 1 \pmod p </math>

== Demostració ==
Suposem que <math> x \equiv y^2 \pmod p </math>. Se sap pel [[petit teorema de Fermat]] que si ''p'' és primer, aleshores <math> x^{p-1}\equiv 1
\pmod p </math>. Després tenim

{|
|<math> X^{(p-1)/2}</math>
|<math> \equiv (y^2)^{(p-1)/2}\pmod p </math>
|-
|
|<math> \equiv y^{p-1}\pmod p </math>
|-
|
|<math> \equiv 1 \pmod p </math>
|-
|}

A la inversa, suposem que <math> x^{(p-1)/2}\equiv 1 \pmod p </math>. Sigui ''b'' un [[element primitiu]] mòdul ''p''. Llavors <math> x \equiv b^i \pmod p </math> per algun ''i''. Aleshores tenim
{|
|<math> X^{(p-1)/2}</math>
|<math> \equiv (b^i)^{(p-1)/2}\pmod p </math>
|-
|
|<math> \equiv b^{i (p-1)/2}\pmod p </math>
|-
|}

Com que ''b'' és d'ordre ''p''-1, s'ha de donar el cas que ''p''-1 divideix ''i'' (''p''-1)/2. Per tant, ''i'' és parell, i les arrels quadrades de ''x'' són <math> \pm b^{i/2}</math>.


{{ORDENA:Criteri D'Euler}}	<!--ORDENA generat per bot-->
[[Categoria:Aritmètica]]
[[Categoria:Teoria de nombres]]