Critério de Euler
# Critério de Euler

Na teoria dos números, o critério de Euler é uma fórmula para determinar se um inteiro é um resíduo quadrático módulo um primo. Precisamente,
Seja $p$ um primo ímpar e $a$ um inteiro coprimo a $p$. Então
    $a^{\tfrac {p-1}{2}}\equiv {\begin{cases}\;\;\,1{\pmod {p}}&{\text{ se houver um inteiro }}x{\text{ tal que }}a\equiv x^{2}{\pmod {p}},\\-1{\pmod {p}}&{\text{ se não houver tal número inteiro.}}\end{cases}}$
O critério de Euler pode ser reformulado de forma concisa usando o símbolo de Legendre:
    $\left({\frac {a}{p}}\right)\equiv a^{\tfrac {p-1}{2}}{\pmod {p}}.$
O critério apareceu pela primeira vez em um artigo de 1748 de Leonhard Euler.

## Prova

A prova usa o fato de que as classes residuais módulo um número primo são um corpo.
Como o módulo é primo, o teorema de Lagrange se aplica: um polinômio de grau $k$ só pode ter no máximo $k$ raízes. Em particular, $x^{2}\equiv a{\pmod {p}}$ tem no máximo 2 soluções para cada $a$. Isso imediatamente implica que além de $0$, há pelo menos ${\tfrac {p-1}{2}}$ resíduos quadráticos distintos módulo $p$: cada um dos $p-1$ valores possíveis de $x$ só pode ser acompanhado por um outro para dar o mesmo resíduo.
De fato, $(p-x)^{2}\equiv x^{2}{\pmod {p}}.$ Isto é porque $(p-x)^{2}\equiv p^{2}-{2}{x}{p}+x^{2}\equiv x^{2}{\pmod {p}}.$ Então os ${\tfrac {p-1}{2}}$ resíduos quadráticos distintos são: $1^{2},2^{2},...,({\tfrac {p-1}{2}})^{2}{\pmod {p}}.$
Como $a$ é coprimo com $p$, o pequeno teorema de Fermat diz que
    $a^{p-1}\equiv 1{\pmod {p}},$
que pode ser escrito como
    $\left(a^{\tfrac {p-1}{2}}-1\right)\left(a^{\tfrac {p-1}{2}}+1\right)\equiv 0{\pmod {p}}.$
Como os inteiros${\bmod {p}}$ formam um corpo, para cada $a$, um ou outro desses fatores deve ser zero.
Agora, se $a$ é um resíduo quadrático, $a\equiv x^{2}$,
    $a^{\tfrac {p-1}{2}}\equiv {(x^{2})}^{\tfrac {p-1}{2}}\equiv x^{p-1}\equiv 1{\pmod {p}}.$
Portanto, cada resíduo quadrático $(\mathrm {mod} \ p)$ torna o primeiro fator zero.
Aplicando o teorema de Lagrange novamente, notamos que não pode haver mais do que ${\tfrac {p-1}{2}}$ valores de $a$ que tornam o primeiro fator zero. Mas, como observamos no início, existem pelo menos ${\tfrac {p-1}{2}}$ resíduos quadráticos distintos $(\mathrm {mod} \ p)$ (além de $0$). Portanto, são precisamente as classes de resíduos que tornam o primeiro fator zero. As outras ${\tfrac {p-1}{2}}$ classes de resíduos, os não-resíduos, devem tornar o segundo fator zero, ou não satisfariam o pequeno teorema de Fermat. Esse é o critério de Euler.

### Prova alternativa

Esta prova usa apenas o fato de que qualquer congruência $kx\equiv l{\pmod {p}}$ tem uma solução única $x$ (módulo $p$) dado que $p$ não divide $k$. (Isso é verdade porque como $x$ percorre todos os restos diferentes de zero módulo $p$ sem repetições, o mesmo acontece com $kx$ - se tivermos $kx_{1}\equiv kx_{2}{\pmod {p}}$, então $p|k(x_{1}-x_{2})$, portanto $p|(x_{1}-x_{2})$, mas $x_{1}$ e $x_{2}$ não são congruentes módulo $p$.) Decorre deste fato que todos os restos diferentes de zero módulo $p$ o quadrado do qual não é congruente com $a$ podem ser agrupados em pares $(x,y)$ de acordo com a regra que o produto dos membros de cada par é congruente com $a$ um módulo $p$ (visto que por este fato para cada $y$ podemos encontrar tal $x$, exclusivamente e vice-versa, e eles serão diferentes uns dos outros se $y^{2}$ não é congruente com $a$). Se $a$ é um não-resíduo quadrático, este é simplesmente um reagrupamento de todos os resíduos $p-1$ diferente de zero em ${\tfrac {p-1}{2}}$ pares, portanto, concluímos que $1\cdot 2\cdot ...\cdot (p-1)\equiv a^{\frac {p-1}{2}}\!\!\!{\pmod {p}}$. Se $a$ é um resíduo quadrático, exatamente dois restos não estavam entre aqueles emparelhados, $r$ e $-r$ tal que $r^{2}\equiv a{\pmod {p}}$. Se emparelharmos esses dois remanescentes ausentes, seu produto será $-a$ ao invés de $a$, onde neste caso $1\cdot 2\cdot ...\cdot (p-1)\equiv -a^{\frac {p-1}{2}}{\pmod {p}}$. Em resumo, considerando esses dois casos, demonstramos que para $a\not \equiv 0{\pmod {p}}$ temos $1\cdot 2\cdot ...\cdot (p-1)\equiv -\left({\frac {a}{p}}\right)a^{\frac {p-1}{2}}{\pmod {p}}$, Resta substituir $a=1$ (que é obviamente um quadrado) nesta fórmula para obter de uma vez o teorema de Wilson, o critério de Euler e (elevando ao quadrado ambos os lados do critério de Euler) o pequeno teorema de Fermat.

## Exemplos

Exemplo 1: Encontrar números primos para os quais a é um resíduo
Seja $a=17$. Para quais primos $p$, 17 é um resíduo quadrático?
Podemos testar os $p$s primos manualmente com a fórmula acima.
Em um caso, testando $p=3$, temos $17^{\frac {3-1}{2}}=17^{1}\equiv 2\equiv -1{\pmod {3}}$, portanto, 17 não é um resíduo quadrático módulo 3.
Em outro caso, testando $p=13$, temos $17^{\frac {13-1}{2}}=17^{6}\equiv 1{\pmod {13}}$, portanto, 17 é um resíduo quadrático módulo 13. Como confirmação, observe que $17\equiv 4{\pmod {13}}$, e $2^{2}=4$.
Podemos fazer esses cálculos mais rapidamente usando várias propriedades da aritmética modular e do símbolo de Legendre.
Se continuarmos calculando os valores, encontramos:
    $\left({\frac {17}{p}}\right)=+1$ para $p=\{13,19,...\}$ (17 é um resíduo quadrático módulo estes valores)
    $\left({\frac {17}{p}}\right)=-1$ para $p=\{3,5,7,11,23,...\}$ (17 não é um resíduo quadrático módulo esses valores).
Exemplo 2: Encontrar resíduos dado um primo módulo p
Quais números são quadrados módulo 17 (resíduos quadráticos módulo 17)?
Podemos calculá-lo manualmente como:
    $1^{2}=1$
    $2^{2}=4$
    $3^{2}=9$
    $4^{2}=16$
    $5^{2}=25\equiv 8{\pmod {17}}$
    $6^{2}=36\equiv 2{\pmod {17}}$
    $7^{2}=49\equiv 15{\pmod {17}}$
    $8^{2}=64\equiv 13{\pmod {17}}$.
Portanto, o conjunto dos resíduos quadráticos módulo 17 é $\{1,2,4,8,9,13,15,16\}$. Observe que não precisamos calcular quadrados para os valores de 9 a 16, pois eles são todos negativos dos valores anteriormente quadrados (por exemplo, $9\equiv -8{\pmod {17}}$, então $9^{2}\equiv (-8)^{2}=64\equiv 13{\pmod {17}}$).
Podemos encontrar resíduos quadráticos ou verificá-los usando a fórmula acima. Para testar se 2 é um resíduo quadrático módulo 17, calculamos $2^{\frac {17-1}{2}}=2^{8}\equiv 1{\pmod {17}}$, portanto, é um resíduo quadrático. Para testar se 3 é um resíduo quadrático módulo 17, calculamos $3^{\frac {17-1}{2}}=3^{8}\equiv 16\equiv -1{\pmod {17}}$, portanto, não é um resíduo quadrático.
O critério de Euler está relacionado à Lei da reciprocidade quadrática.

## Aplicações

Na prática, é mais eficiente usar uma variante estendida do algoritmo de Euclides para calcular o símbolo de Jacobi $\left({\frac {a}{n}}\right)$. Se $n$ é um primo ímpar, isso é igual ao símbolo de Legendre, e decide se $a$ é um módulo de resíduo quadrático $n$.
Por outro lado, uma vez que a equivalência de $a^{\frac {n-1}{2}}$ ao símbolo Jacobi se mantém para todos os primos ímpares, mas não necessariamente para números compostos, calcular ambos e compará-los pode ser usado como um teste de primalidade, especificamente o teste de primalidade de Solovay-Strassen. Números compostos para os quais a congruência é válida para um determinado $a$ são chamados de pseudoprimos de Euler-Jacobi para basear $a$.