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^{\frac{p-1}{2}}\equiv \{\begin{array}{cc}1(\mathrm{mod}p)& \text{ se houver um inteiro }x\text{ tal que }a\equiv x^2(\mathrm{mod}p),\\ -1(\mathrm{mod}p)& \text{ se não houver tal número inteiro.}\end{array}$

O critério de Euler pode ser reformulado de forma concisa usando o símbolo de Legendre:

$\left(\frac{a}{p}\right)\equiv a^{\frac{p-1}{2}}(\mathrm{mod}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(\mathrm{mod}p)$ tem no máximo 2 soluções para cada $a$. Isso imediatamente implica que além de $0$, há pelo menos $\frac{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(\mathrm{mod}p).$ Isto é porque $(p-x{)}^2\equiv p^2-2xp+x^2\equiv x^2(\mathrm{mod}p).$ Então os $\frac{p-1}{2}$ resíduos quadráticos distintos são: $1^2,2^2,...,(\frac{p-1}{2}{)}^2(\mathrm{mod}p).$

Como $a$ é coprimo com $p$, o pequeno teorema de Fermat diz que

$a^{p-1}\equiv 1(\mathrm{mod}p),$

que pode ser escrito como

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

Como os inteiros$modp$ 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^{\frac{p-1}{2}}\equiv {(x^2)}^{\frac{p-1}{2}}\equiv x^{p-1}\equiv 1(\mathrm{mod}p).$

Portanto, cada resíduo quadrático $(\mathrm{m}\mathrm{o}\mathrm{d}p)$ torna o primeiro fator zero.

Aplicando o teorema de Lagrange novamente, notamos que não pode haver mais do que $\frac{p-1}{2}$ valores de $a$ que tornam o primeiro fator zero. Mas, como observamos no início, existem pelo menos $\frac{p-1}{2}$ resíduos quadráticos distintos $(\mathrm{m}\mathrm{o}\mathrm{d}p)$ (além de $0$). Portanto, são precisamente as classes de resíduos que tornam o primeiro fator zero. As outras $\frac{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(\mathrm{mod}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 $k{x}_1\equiv k{x}_2(\mathrm{mod}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 $\frac{p-1}{2}$ pares, portanto, concluímos que $1\cdot 2\cdot ...\cdot (p-1)\equiv a^{\frac{p-1}{2}}(\mathrm{mod}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(\mathrm{mod}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}}(\mathrm{mod}p)$. Em resumo, considerando esses dois casos, demonstramos que para $a\equiv ̸0(\mathrm{mod}p)$ temos $1\cdot 2\cdot ...\cdot (p-1)\equiv -\left(\frac{a}{p}\right)a^{\frac{p-1}{2}}(\mathrm{mod}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(\mathrm{mod}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(\mathrm{mod}13)$, portanto, 17 é um resíduo quadrático módulo 13. Como confirmação, observe que $17\equiv 4(\mathrm{mod}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(\mathrm{mod}17)$

$6^2=36\equiv 2(\mathrm{mod}17)$

$7^2=49\equiv 15(\mathrm{mod}17)$

$8^2=64\equiv 13(\mathrm{mod}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(\mathrm{mod}17)$, então $9^2\equiv (-8{)}^2=64\equiv 13(\mathrm{mod}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(\mathrm{mod}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(\mathrm{mod}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.

• Predefinição:Citation

• Predefinição:Citation

• Predefinição:Citation

• Predefinição:Citation

Ligações externas

• The Euler Archive