terça-feira, 15 de dezembro de 2009

O Pequeno Teorema e o grande erro de Fermat

WARNING (temporário): As fontes estão zuadas, o blogger é muito ruim pra editar, estou arrumando aos poucos.

Fermat foi um grande "matemático" e tem uma vida repleta de curiosidades interessantes. As aspas na palavra matemático são porque ele não era de fato um matemático formado, Fermat era juiz. Desta forma, foi-lhe atribuído o rótulo de Matemático Amador, mas de amador seu trabalho não tem nada.

Mais sobre a vida de Fermat pode ser visto aqui. O assunto que quero tratar neste texto versa sobre um famoso teorema de Fermat, e a sua mais irônica consequência.


Lembre-se que, se você tiver alguma dúvida, clique nos links ou acesse as notas referenciadas por [*].

O Pequeno Teorema de Fermat

Não confunda com o Último Teorema de Fermat [1], o Pequeno Teorema é simples de ser demonstrado e pode ser enunciado na seguinte forma:

Teorema: Seja p um número primo e a um inteiro qualquer, então é múltiplo de p.

Em notação de moderna, a notação de congruências [2] (originalmente criada por Gauss), diríamos que



Uma consequência direta (ou uma outra possível formulação deste teorema) é que, com a hipótese adicional de que a é primo com p (isto é, não tem fator em comum com p), então



Cabe ressaltar que, se você já estudou um pouco de Grupos, este teorema é uma consequência direta do Teorema de Lagrange aplicado ao grupo .

Se você quiser tentar demonstrar o Pequeno Teorema (não é difícil!), eis uma dica na nota de rodapé [3]. Caso contrário, lá você também pode encontrar um link para a demonstração.

Um fato interessante sobre o Pequeno Teorema de Fermat é que o primeiro registro histório da atribuição deste nome ao famoso teorema data do século passado, num artigo sobre Criptografia RSA. O que também mostra que este teorema, apesar de simples, é bastante poderoso e tem diversas aplicações, tanto teóricas quanto práticas.

Outro fato interessante é que a primeira demonstração deste teorema foi publicada por Euler, e não por Fermat. Aliás, Fermat nunca publicava suas descobertas. Acredita-se que outros matemáticos além de Fermat e Euler conseguiram demonstrar este teorema independentemente uns dos outros.

A contribuição de Euler não para por aí, este brilhante e prolífico matemático suíço conseguiu também generalizar esta fórmula para quando p não é necessariamente um número primo. Mas isto é uma outra história.

O grande erro de Fermat


O que eu chamo de "grande erro de Fermat" é um fato bastante conhecido para quem estuda Teoria dos Números ou simplesmente gosta do assunto. Em diversas cartas trocadas por Fermat, este conjecturava aos seus colegas que os números da forma



eram primos para todo natural n. Números desta forma são conhecidos hoje como Números de Fermat.

Se você atribuir valores pequenos para n, perceberá que, realmente, os resultados serão primos. Por exemplo: 5, 17, 257 e 65537.

O problema, que você já deve ter percebido, é que números desta forma crescem muito rapidamente, o que tornava inviável para Fermat checar se eram realmente primos ou não.

Para resolver este problema, Euler entra de novo nesta história e agora ele é o protagonista. De fato, Euler mostrou que a conjectura de Fermat estava errada, e falhava para n=5. A grande ironia desta história toda, é que, para obter tal feito, Euler fez uso do Pequeno Teorema de Fermat.

A demonstração original de Euler é um pouco diferente do que iremos fazer aqui, mas essencialmente é a mesma coisa.

não é primo!

Para mostrar que não é primo precisaremos do conceito de ordem. Novamente, se você estudou Grupos já deve estar familiarizado com a ordem de um elemento.

Definimos a ordem de a módulo n como sendo o menor inteiro positivo d tal que . Notamos .

Agora, precisaremos do seguinte Lema , bastante inocente mas muito importante:

Lema ("ordem divide"): Se e , então , isto é, d divide m ( ou m é múltiplo de d).

Demonstração: Dividindo m por d, temos que existem inteiros q e r tais que




com r satisfazendo . Então,




Pela minimalidade de d, concluímos que r só pode ser 0, e portanto .


Agora temos tudo o que precisamos para mostrar a seguinte

Proposição: não é primo.

Demonstração: Seja p um divisor primo de . Vamos achar uma forma de caracterizar p.

Utilizando a notação de congruências, temos que




Elevando os dois lados ao quadrado, temos




Seja d a ordem de 2 módulo p, isto é, . Pelo Lema acima, . Portanto, d é da forma , com .

Obviamente, k não pode ser 5, pois . Suponha , então




Elevando ambos os lados a (note que 5-k é positivo), temos




O que é absurdo, pois, novamente, sabemos que . Desta forma, concluímos que .

Pelo Pequeno Teorema de Fermat, temos




Como p é ímpar, então p não tem fator em comum com 2, o que implica




Agora, vamos aplicar o lema de novo.




para algum q inteiro. Desta forma, sabemos que um divisor primo de tem que, necessariamente, ser da forma , com .

Agora, basta testar alguns casos. Para isso, vamos expandir o número em notação decimal, substituir valores de q e achar os respectivos primos p.




Note que você pode jogar fora os p que não derem números primos, pois estamos supondo p primo. Para isso, você pode usar aquela técnica do Crivo de Eratóstenes (ou seja, testar só até a raiz quadrada do número).

Testando alguns casos (pegue uma calculadora!) você descobrirá que 641 divide 4294967297. É uma pena, Fermat estava errado!


Conclusões

Este pequeno artigo exemplifica bem um papel importante do matemático: tornar as contas mais fáceis (ou até possíveis, em alguns casos). Pudemos ver que um curto raciocínio reduziu drásticamente nossas necessidades computacionais, e isto era particularmente importante naquela época em que as contas eram feitas no papel.

Para encerrar, note que também é curioso o fato de Fermat ter realizado uma conjectura tendo por base somente 4 casos! Isso não é de se esperar de alguém com a sua tamanha inteligência. Pesquisando um pouco na internet, descobri que existe uma possível explicação para tal erro de Fermat, como não achei fontes confiáveis, a pergunta fica para você. O que você acha que levou Fermat afirmar que é primo para todo n.

Até.

Bônus:
Demonstração original de Euler do Pequeno Teorema de Fermat aqui. Demonstração original de Euler de que Fermat estava errado aqui.

Notas:


[1] O Último Teorema de Fermat foi um dos problemas mais difíceis da história da matemática, e durou 300 anos sem ser resolvido. Boa parte da criação da Álgebra Moderna se deveu a este Teorema. Clique aqui

[2] Se você não está acostumado com a notação de congruências, seria bom que estivesse. Neste link poderá encontrar alguma ajuda: http://erdos.ime.usp.br/index.php/Congru%C3%AAncias


[3] A dica para demonstrar o Pequeno Teorema de Fermat é fixar um primo p, e provar por indução em a. Se você tentou e não conseguiu, ou simplesmente está com preguiça de tentar, eis aqui a demonstração. Cabe ressaltar que existem MUITAS demonstrações deste teorema, basta dar uma "googlada" e você encontrará diversas outras demonstrações bem interessantes.




3 comentários: