Criteri de Euler

En teoria de números, concretament en aritmètica modular, el criteri de Euler és utilisat per a calcular si un número entero x és un residu quadràtic mòdul un número primo. El seu nom es deu al matemàtic suís Leonhard Euler.

Enunciat

Siga p > 2 un número primer i a un número entero coprimo en p. Llavors a és un residu quadràtic mòdul p si i solament si

$a^{(p-1)/2}\equiv 1(\mathrm{mod}p).$

Com corolari d'esta teorema s'obté que si a no és un residu quadràtic mòdul p llavors

$a^{(p-1)/2}\equiv -1(\mathrm{mod}p).$

Aixina, el criteri de Euler pot ser reformulat de manera més compacta usant el símbol de Legendre:

$a^{(p-1)/2}\equiv \left(\frac{a}{p}\right)(\mathrm{mod}p).$

Demostració

Suponga's que $a\equiv x^2(\mathrm{mod}p)$. Se sap pel menuda teorema de Fermat que si p és primer i és coprimo en a, és dir, p no dividix al número a, llavors $a^{p-1}\equiv 1(\mathrm{mod}p)$. Després es té que

$a^{(p-1)/2}$	$\equiv (x^2{)}^{(p-1)/2}(\mathrm{mod}p)$
	$\equiv x^{p-1}(\mathrm{mod}p)$
	$\equiv 1(\mathrm{mod}p)$

A l'inversa, se supon que $a^{(p-1)/2}\equiv 1(\mathrm{mod}p)$. Siga b un element primitiu mòdul p. Llavors $a\equiv b^i(\mathrm{mod}p)$ per a algun i. Després es té que

$a^{(p-1)/2}$	$\equiv (b^i{)}^{(p-1)/2}(\mathrm{mod}p)$
	$\equiv b^{i(p-1)/2}(\mathrm{mod}p)$

Com a b és d'orde p-1, deu donar-se el cas de que p-1 dividix a i(p-1)/2. Per lo tant, i és parell, i les raïls quadrades de a sò $\pm b^{i/2}$.

Referències

Bibliografia

Tom M. Apostol (1976): Introduction to Analytic Number Theory, Springer-Verlag, New York. ISBN 0-387-90163-9, (Capítul 9.2)