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 ${\displaystyle p}$ um primo ímpar e ${\displaystyle a}$ um inteiro coprimo a ${\displaystyle p}$. Então^[1][2][3]

${\displaystyle 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:^[4]

${\displaystyle \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.^[5][6]

Prova

A prova usa o fato de que as classes residuais módulo um número primo são um campo.

Como o módulo é primo, o teorema de Lagrange se aplica: um polinômio de grau ${\displaystyle k}$ só pode ter no máximo ${\displaystyle k}$ raízes. Em particular, ${\displaystyle x^{2}\equiv a{\pmod {p}}}$ tem no máximo 2 soluções para cada ${\displaystyle a}$. Isso imediatamente implica que além de ${\displaystyle 0}$, há pelo menos ${\displaystyle {\tfrac {p-1}{2}}}$ resíduos quadráticos distintos módulo ${\displaystyle p}$: cada um dos ${\displaystyle p-1}$ valores possíveis de ${\displaystyle x}$ só pode ser acompanhado por um outro para dar o mesmo resíduo.

De fato, ${\displaystyle (p-x)^{2}\equiv x^{2}{\pmod {p}}.}$ Isto é porque ${\displaystyle (p-x)^{2}\equiv p^{2}-{2}{x}{p}+x^{2}\equiv x^{2}{\pmod {p}}.}$ Então os ${\displaystyle {\tfrac {p-1}{2}}}$ resíduos quadráticos distintos são: ${\displaystyle 1^{2},2^{2},...,({\tfrac {p-1}{2}})^{2}{\pmod {p}}.}$

Como ${\displaystyle a}$ é coprimo com ${\displaystyle p}$, o pequeno teorema de Fermat diz que

${\displaystyle a^{p-1}\equiv 1{\pmod {p}},}$

que pode ser escrito como

${\displaystyle \left(a^{\tfrac {p-1}{2}}-1\right)\left(a^{\tfrac {p-1}{2}}+1\right)\equiv 0{\pmod {p}}.}$

Como os inteiros${\displaystyle {\bmod {p}}}$ formam um campo, para cada ${\displaystyle a}$, um ou outro desses fatores deve ser zero.

Agora, se ${\displaystyle a}$ é um resíduo quadrático, ${\displaystyle a\equiv x^{2}}$,

${\displaystyle 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 ${\displaystyle (\mathrm {mod} \ p)}$ torna o primeiro fator zero.

Aplicando o teorema de Lagrange novamente, notamos que não pode haver mais do que ${\displaystyle {\tfrac {p-1}{2}}}$ valores de ${\displaystyle a}$ que tornam o primeiro fator zero. Mas, como observamos no início, existem pelo menos ${\displaystyle {\tfrac {p-1}{2}}}$ resíduos quadráticos distintos ${\displaystyle (\mathrm {mod} \ p)}$ (além de ${\displaystyle 0}$). Portanto, são precisamente as classes de resíduos que tornam o primeiro fator zero. As outras ${\displaystyle {\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 ${\displaystyle kx\equiv l{\pmod {p}}}$ tem uma solução única ${\displaystyle x}$ (módulo ${\displaystyle p}$) dado que ${\displaystyle p}$ não divide ${\displaystyle k}$. (Isso é verdade porque como ${\displaystyle x}$ percorre todos os restos diferentes de zero módulo ${\displaystyle p}$ sem repetições, o mesmo acontece com ${\displaystyle kx}$ - se tivermos ${\displaystyle kx_{1}\equiv kx_{2}{\pmod {p}}}$, então ${\displaystyle p|k(x_{1}-x_{2})}$, portanto ${\displaystyle p|(x_{1}-x_{2})}$, mas ${\displaystyle x_{1}}$ e ${\displaystyle x_{2}}$ não são congruentes módulo ${\displaystyle p}$.) Decorre deste fato que todos os restos diferentes de zero módulo ${\displaystyle p}$ o quadrado do qual não é congruente com ${\displaystyle a}$ podem ser agrupados em pares ${\displaystyle (x,y)}$ de acordo com a regra que o produto dos membros de cada par é congruente com ${\displaystyle a}$ um módulo ${\displaystyle p}$ (visto que por este fato para cada ${\displaystyle y}$ podemos encontrar tal ${\displaystyle x}$, exclusivamente e vice-versa, e eles serão diferentes uns dos outros se ${\displaystyle y^{2}}$ não é congruente com ${\displaystyle a}$). Se ${\displaystyle a}$ é um não-resíduo quadrático, este é simplesmente um reagrupamento de todos os resíduos ${\displaystyle p-1}$ diferente de zero em ${\displaystyle {\tfrac {p-1}{2}}}$ pares, portanto, concluímos que ${\displaystyle 1\cdot 2\cdot ...\cdot (p-1)\equiv a^{\frac {p-1}{2}}\!\!\!{\pmod {p}}}$. Se ${\displaystyle a}$ é um resíduo quadrático, exatamente dois restos não estavam entre aqueles emparelhados, ${\displaystyle r}$ e ${\displaystyle -r}$ tal que ${\displaystyle r^{2}\equiv a{\pmod {p}}}$. Se emparelharmos esses dois remanescentes ausentes, seu produto será ${\displaystyle -a}$ ao invés de ${\displaystyle a}$, onde neste caso ${\displaystyle 1\cdot 2\cdot ...\cdot (p-1)\equiv -a^{\frac {p-1}{2}}{\pmod {p}}}$. Em resumo, considerando esses dois casos, demonstramos que para ${\displaystyle a\not \equiv 0{\pmod {p}}}$ temos ${\displaystyle 1\cdot 2\cdot ...\cdot (p-1)\equiv -\left({\frac {a}{p}}\right)a^{\frac {p-1}{2}}{\pmod {p}}}$, Resta substituir ${\displaystyle 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 ${\displaystyle a=17}$. Para quais primos ${\displaystyle p}$, 17 é um resíduo quadrático?

Podemos testar os ${\displaystyle p}$s primos manualmente com a fórmula acima.

Em um caso, testando ${\displaystyle p=3}$, temos ${\displaystyle 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 ${\displaystyle p=13}$, temos ${\displaystyle 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 ${\displaystyle 17\equiv 4{\pmod {13}}}$, e ${\displaystyle 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:

${\displaystyle \left({\frac {17}{p}}\right)=+1}$ para ${\displaystyle p=\{13,19,...\}}$ (17 é um resíduo quadrático módulo estes valores)

${\displaystyle \left({\frac {17}{p}}\right)=-1}$ para ${\displaystyle 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:

${\displaystyle 1^{2}=1}$

${\displaystyle 2^{2}=4}$

${\displaystyle 3^{2}=9}$

${\displaystyle 4^{2}=16}$

${\displaystyle 5^{2}=25\equiv 8{\pmod {17}}}$

${\displaystyle 6^{2}=36\equiv 2{\pmod {17}}}$

${\displaystyle 7^{2}=49\equiv 15{\pmod {17}}}$

${\displaystyle 8^{2}=64\equiv 13{\pmod {17}}}$.

Portanto, o conjunto dos resíduos quadráticos módulo 17 é ${\displaystyle \{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, ${\displaystyle 9\equiv -8{\pmod {17}}}$, então ${\displaystyle 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 ${\displaystyle 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 ${\displaystyle 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 ${\displaystyle \left({\frac {a}{n}}\right)}$. Se ${\displaystyle n}$ é um primo ímpar, isso é igual ao símbolo de Legendre, e decide se ${\displaystyle a}$ é um módulo de resíduo quadrático ${\displaystyle n}$.

Por outro lado, uma vez que a equivalência de ${\displaystyle 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 ${\displaystyle a}$ são chamados de pseudoprimos de Euler-Jacobi para basear ${\displaystyle a}$.

Notas

Referências

O Disquisitiones Arithmeticae foi traduzido do latim ciceroniano de Gauss para o inglês e o alemão. A edição alemã inclui todos os seus artigos sobre a teoria dos números: todas as provas de reciprocidade quadrática, a determinação do sinal da soma de Gauss, as investigações sobre a reciprocidade biquadrática e notas não publicadas.

• Gauss, Carl Friedrich; Clarke, Arthur A. (translator into English) (1986), Disquisitiones Arithemeticae (Second, corrected edition), ISBN 0-387-96254-9, New York: Springer 

• Gauss, Carl Friedrich; Maser, H. (translator into German) (1965), Untersuchungen über höhere Arithmetik (Disquisitiones Arithemeticae & other papers on number theory) (Second edition), ISBN 0-8284-0191-8, New York: Chelsea 

• Hardy, G. H.; Wright, E. M. (1980), An Introduction to the Theory of Numbers (Fifth edition), ISBN 978-0-19-853171-5, Oxford: Oxford University Press  Verifique o valor de |url-access=registration (ajuda)

• Lemmermeyer, Franz (2000), Reciprocity Laws: from Euler to Eisenstein, ISBN 3-540-66957-4, Berlin: Springer 

Ligações externas

• The Euler Archive

• Portal da matemática