Saltar para o conteúdo

Critério de Euler

Origem: Wikipédia, a enciclopédia livre.

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 um primo ímpar e um inteiro coprimo a . Então[1][2][3]

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

O critério apareceu pela primeira vez em um artigo de 1748 de Leonhard Euler.[5][6]

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 só pode ter no máximo raízes. Em particular, tem no máximo 2 soluções para cada . Isso imediatamente implica que além de , há pelo menos resíduos quadráticos distintos módulo : cada um dos valores possíveis de só pode ser acompanhado por um outro para dar o mesmo resíduo.

De fato, Isto é porque Então os resíduos quadráticos distintos são:

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

que pode ser escrito como

Como os inteiros formam um campo, para cada , um ou outro desses fatores deve ser zero.

Agora, se é um resíduo quadrático, ,

Portanto, cada resíduo quadrático torna o primeiro fator zero.

Aplicando o teorema de Lagrange novamente, notamos que não pode haver mais do que valores de que tornam o primeiro fator zero. Mas, como observamos no início, existem pelo menos resíduos quadráticos distintos (além de ). Portanto, são precisamente as classes de resíduos que tornam o primeiro fator zero. As outras 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

[editar | editar código-fonte]

Esta prova usa apenas o fato de que qualquer congruência tem uma solução única (módulo ) dado que não divide . (Isso é verdade porque como percorre todos os restos diferentes de zero módulo sem repetições, o mesmo acontece com - se tivermos , então , portanto , mas e não são congruentes módulo .) Decorre deste fato que todos os restos diferentes de zero módulo o quadrado do qual não é congruente com podem ser agrupados em pares de acordo com a regra que o produto dos membros de cada par é congruente com um módulo (visto que por este fato para cada podemos encontrar tal , exclusivamente e vice-versa, e eles serão diferentes uns dos outros se não é congruente com ). Se é um não-resíduo quadrático, este é simplesmente um reagrupamento de todos os resíduos diferente de zero em pares, portanto, concluímos que . Se é um resíduo quadrático, exatamente dois restos não estavam entre aqueles emparelhados, e tal que . Se emparelharmos esses dois remanescentes ausentes, seu produto será ao invés de , onde neste caso . Em resumo, considerando esses dois casos, demonstramos que para temos , Resta substituir (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.

Exemplo 1: Encontrar números primos para os quais a é um resíduo

Seja . Para quais primos , 17 é um resíduo quadrático?

Podemos testar os s primos manualmente com a fórmula acima.

Em um caso, testando , temos , portanto, 17 não é um resíduo quadrático módulo 3.

Em outro caso, testando , temos , portanto, 17 é um resíduo quadrático módulo 13. Como confirmação, observe que , e .

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:

para (17 é um resíduo quadrático módulo estes valores)
para (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:

.

Portanto, o conjunto dos resíduos quadráticos módulo 17 é . 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, , então ).

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 , portanto, é um resíduo quadrático. Para testar se 3 é um resíduo quadrático módulo 17, calculamos , portanto, não é um resíduo quadrático.

O critério de Euler está relacionado à Lei da reciprocidade quadrática.

Na prática, é mais eficiente usar uma variante estendida do algoritmo de Euclides para calcular o símbolo de Jacobi . Se é um primo ímpar, isso é igual ao símbolo de Legendre, e decide se é um módulo de resíduo quadrático .

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

  1. Gauss, DA, Art. 106
  2. Dense, Joseph B.; Dence, Thomas P. (1999). «Theorem 6.4, Chap 6. Residues». Elements of the Theory of Numbers. [S.l.]: Harcourt Academic Press. p. 197 
  3. Leonard Eugene Dickson, "History Of The Theory Of Numbers", vol 1, p 205, Chelsea Publishing 1952
  4. Hardy & Wright, thm. 83
  5. Lemmermeyer, p. 4 cites two papers, E134 and E262 in the Euler Archive
  6. L Euler, Novi commentarii Academiae Scientiarum Imperialis Petropolitanae, 8, 1760-1, 74; Opusc Anal. 1, 1772, 121; Comm. Arith, 1, 274, 487

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 

Ligações externas

[editar | editar código-fonte]