O pequeno teorema de Fermat

Na teoria dos números, o pequeno teorema de Fermat afirma que se p é um número primo, então, para qualquer número inteiro a, o número a ^p − a é um múltiplo inteiro de p. Na notação da aritmética modular, isso é expresso como

${displaystyle a^{p}equiv a{pmod {p}}.}$

Por exemplo, se um = 2 e p = 7, então 2⁷ = 128e 128 − 2 = 126 = 7 × 18 é um inteiro múltiplo de 7.

Se a não for divisível por p; isto é, se a for coprimo com p, então o pequeno teorema de Fermat é equivalente à afirmação de que a^{p − 1< /sup> − 1} é um múltiplo inteiro de p, ou em símbolos:

${displaystyle a^{p-1}equiv 1 pmod {p}}.}$

Por exemplo, se a = 2 e p = 7, então 2⁶ = 64 e 64 − 1 = 63 = 7 × 9 é portanto um múltiplo de 7.

O pequeno teorema de Fermat é a base para o teste de primalidade de Fermat e é um dos resultados fundamentais da teoria elementar dos números. O teorema recebeu o nome de Pierre de Fermat, que o declarou em 1640. É chamado de "pequeno teorema" para distingui-lo do Último Teorema de Fermat.

Histórico

Pierre de Fermat afirmou pela primeira vez o teorema em uma carta datada de 18 de outubro de 1640, a seu amigo e confidente Frénicle de Bessy. Sua formulação é equivalente ao seguinte:

Se p é um primo e um é qualquer inteiro não divisível por p, então um ^{p - 1} - 1 é divisível por p.

A declaração original de Fermat foi

Tout nombre premier mesure infailliblement une des puissances $Não. -1$ de quelque progression que ce soit, et l'exposant de la dite puissance est sous-multiple du nombre premier donné $Não. -1$; et, après qu'on a trouvé la première puissance qui satisfazait à la question, toutes celles dont les exposiants sont multiples de l'exposant de la première satisfont tout de même à la question.

Isso pode ser traduzido, com explicações e fórmulas adicionadas entre colchetes para facilitar a compreensão, como:

Cada número primo [p] divide necessariamente um dos poderes menos uma de qualquer progressão [geométrica]um, um², um³...Isso é, existe. ) tal que p divide um⁾ – 1], e o expoente deste poder [)] divide o dado primo menos um [divides p – 1]. Depois de um ter encontrado o primeiro poder [)] que satisfaz a pergunta, todos aqueles cujos expoentes são múltiplos do expoente do primeiro satisfazem da mesma forma a pergunta [isto é, todos os múltiplos do primeiro ) tem a mesma propriedade].

Fermat não considerou o caso em que um é um múltiplo de p nem provar sua afirmação, apenas afirmando:

Et cette proposição est généralement vraie en toutes progressions et en tous nombres premiers; de quoi je vous envoierois la démonstration, si je n'appréhendois d'être trop long.

(E esta proposição é geralmente verdadeira para todas as séries [Sic] e para todos os números primos; eu lhe enviaria uma demonstração disso, se eu não tivesse medo de continuar por muito tempo.)

Euler forneceu a primeira prova publicada em 1736, em um artigo intitulado "Theorematum Quorundam ad Numeros Primos Spectantium Demonstratio" nos Anais da Academia de São Petersburgo, mas Leibniz deu praticamente a mesma prova em um manuscrito não publicado de algum tempo antes de 1683.

O termo "teorema pequeno de Fanmat" foi provavelmente usado pela primeira vez na impressão em 1913 Zahlenthe por Kurt Hensel:

Für jede endliche Gruppe besteht nun ein Fundamentalsatz, welcher der kleine Fermatsche Satz genannt zu werden pflegt, weil ein ganz spezieller Teil desselben zuerst von Fermat bewiesen worden ist.

(Há um teorema fundamental em cada grupo finito, geralmente chamado de pouco teorema de Fermat, porque Fermat foi o primeiro a ter provado uma parte muito especial dele.)

Um uso antigo em inglês ocorre em A.A. A Álgebra Superior Moderna de Albert (1937), que se refere à "chamada 'pequena' Teorema de Fermat" na página 206.

Mais história

Alguns matemáticos formularam independentemente a hipótese relacionada (às vezes chamada incorretamente de hipótese chinesa) de que 2^p ≡ 2 (mod p) se e somente se p for primo. Na verdade, o "se" parte é verdadeira e é um caso especial do pequeno teorema de Fermat. No entanto, o "somente se" parte é falsa: por exemplo, 2³⁴¹ ≡ 2 (mod 341), mas 341 = 11 × 31 é um pseudoprimo da base 2. Veja abaixo.

Provas

Várias provas do pequeno teorema de Fermat são conhecidas. É frequentemente provado como um corolário do teorema de Euler.

Generalizações

O teorema de Euler é uma generalização do pequeno teorema de Fermat: Para qualquer módulo n e qualquer inteiro a coprime para n, um tem

${displaystyle a^{varphi (n)}equiv 1{pmod {n}},}$

onde φ(n) denota a função totiente de Euler (que conta os inteiros de 1 a n que são coprimos com n). O pequeno teorema de Fermat é de fato um caso especial, porque se n é um número primo, então φ(n) = n − 1.

Um corolário do teorema de Euler é: Para cada inteiro positivo n, se o inteiro a é coprime com n, então

${displaystyle xequiv y{pmod {varphi (n)}}quad {text{implies}}quad a^{x}equiv a^{y}{pmod {n}},}$

para qualquer inteiro x e Sim.. Isto segue do teorema de Euler, desde então, se ${displaystyle xequiv y{pmod {varphi (n)}}}$, então x = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = Sim. + k)(n) para alguns inteiros k, e um tem

${displaystyle a^{x}=a^{y+varphi (n)k}=a^{y}(a^{varphi (n)})^{k}equiv a^{y}1^{k}equiv a^{y}{pmod {n}}.}$

Se n é primo, isso também é um corolário do pequeno teorema de Fermat. Isso é amplamente utilizado em aritmética modular, porque permite reduzir a exponenciação modular com expoentes grandes para expoentes menores que n.

O teorema de Euler é usado com n não primo na criptografia de chave pública, especificamente no sistema criptográfico RSA, normalmente da seguinte maneira:

Se $Não. y=x^{e}{pmod {n}},}$

recuperando x dos valores de y, e e n é fácil se alguém souber φ(n). Na verdade, o algoritmo euclidiano estendido permite calcular o inverso modular de e módulo φ (n); isto é, o inteiro f tal que

${displaystyle efequiv 1{pmod {varphi (n)}}}$

Segue-se que

${displaystyle xequiv x^{ef}equiv (x^{e})^{f}equiv - Sim. Não.$

Por outro lado, se n = pq é o produto de dois números primos distintos, então φ(n) = (p − 1)(q − 1)< /span>. Neste caso, encontrar f de n e e é tão difícil quanto computar φ (n) (isso não foi comprovado, mas nenhum algoritmo é conhecido para calcular f sem saber φ(n)). Conhecendo apenas n, o cálculo de φ( n) tem essencialmente a mesma dificuldade que a fatoração de n, já que φ(n) = (p − 1)(q − 1) e, inversamente, os fatores p e q são as soluções (inteiras) da equação x² – (n − < i>φ(n) + 1) x + n = 0.

A ideia básica do criptossistema RSA é a seguinte: Se uma mensagem x for criptografada como y = x^e (mod n), usando valores públicos de n e e, então, com o atual conhecimento, ele não pode ser descriptografado sem encontrar os fatores (secretos) p e q de n.

O pequeno teorema de Fermat também está relacionado à função de Carmichael e ao teorema de Carmichael, bem como ao teorema de Lagrange na teoria dos grupos.

Conversar

A recíproca do pequeno teorema de Fermat geralmente não é verdadeira, pois falha para os números de Carmichael. No entanto, uma forma ligeiramente mais forte do teorema é verdadeira e é conhecida como teorema de Lehmer. O teorema é o seguinte:

Se existir um inteiro a tal que

${displaystyle a^{p-1}equiv 1 {p}}}$

e para todos os números primos q dividindo p − 1 um tem

${displaystyle a^{(p-1)/q}not equiv 1{pmod {p}},}$

então p é primo.

Este teorema forma a base para o teste de primalidade de Lucas, um importante teste de primalidade, e para o certificado de primalidade de Pratt.

Pseudoprimos

Se a e p< /span> são números primos tais que a^p−1 − 1 é divisível por p, então p não precisa ser primo. Se não for, então p é chamado de (Fermat) pseudoprimo para basear a. O primeiro pseudoprimo de base 2 foi encontrado em 1820 por Pierre Frédéric Sarrus: 341 = 11 × 31.

Um número p que é um pseudoprimo de Fermat para basear a para cada número a coprimo com p é chamado de número Carmichael (por exemplo, 561). Alternativamente, qualquer número p satisfazendo a igualdade

${displaystyle gcd left(p,sum _{a=1}^{p-1}a^{p-1}right)=1}$

é um número primo ou um número de Carmichael.

Teste de primalidade de Miller-Rabin

O teste de primalidade de Miller-Rabin usa a seguinte extensão do pequeno teorema de Fermat:

Se p é um primo estranho e p - 1 = 2^SD com > 0 e D odd > 0, então para cada um coprime para pOu um^D ≡ 1 (mod p) ou existe R tal que 0 ≤ R < S e um^2RD ≡ −1 (mod p).

Este resultado pode ser deduzido do pequeno teorema de Fermat pelo fato de que, se p é um primo ímpar, então o módulo inteiro p forma um campo finito, no qual 1 módulo p tem exatamente duas raízes quadradas, 1 e −1 módulo p.

Observe que a^d ≡ 1 (mod p)< /span> vale trivialmente para a ≡ 1 (mod p), porque a relação de congruência é compatível com exponenciação. E a^d = a^{20< /sup>d ≡ −1 (mod p)} vale trivialmente para a ≡ −1 (mod p) já que d é ímpar, pois o mesma razão. É por isso que geralmente se escolhe um a aleatório no intervalo 1 < a < p − 1.

O teste de Miller-Rabin usa esta propriedade da seguinte maneira: dado um número inteiro ímpar p para o qual a primalidade deve ser testado, escreva p − 1 = 2^sd com s > 0 e d ímpar > 0 e escolha um a aleatório tal que 1 < a < p − 1; então calcule b = a^d mod p; se b não for 1 nem −1, então eleve-o ao quadrado repetidamente módulo p até obter −1 ou ter ao quadrado s − 1 vezes. Se b ≠ 1 e −1 não foi obtido por quadratura, então p é um composto e a é uma testemunha da composição de p. Caso contrário, p é um primo provável forte para basear a; isto é, pode ser primo ou não. Se p for composto, a probabilidade de que o teste o declare um primo provável forte de qualquer maneira é no máximo 1⁄4, nesse caso estilo p é um pseudoprimo forte e a é um mentiroso. Portanto, após k testes aleatórios não conclusivos, a probabilidade de que p é composto é no máximo 4^−k e pode, portanto, ser tão baixo quanto desejado aumentando k.

Em resumo, o teste prova que um número é composto ou afirma que é primo com uma probabilidade de erro que pode ser escolhida tão baixa quanto desejado. O teste é muito simples de implementar e computacionalmente mais eficiente do que todos os testes determinísticos conhecidos. Portanto, geralmente é usado antes de iniciar uma prova de primalidade.