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 campo.

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 campo, 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$.

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 

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

Ligações externas

• The Euler Archive