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 detem 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.
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:
Post muito foda, deve ter dado trabalho bagarai =P
Ta com uns errinhos ainda, mas com o tempo vc vai ajeitando huauah
Aliás essas coisas do Fermat são meio obscuras, as pessoas sabem que ele realmente acreditava nisso?
De repente foi só um chute que ele deu, mas ele não tinha tanta fé assim de que a hipótese era verdade. =P
Até porque Fermat era um "brincalhão". Msa, até onde li, em diversas cartas que ele trocava com outros matemáticos ele conjecturava isto, o que pode indicar duas coisas: ou ele realmente acreditava, ou ele apenas os desafiando para que provassem (ou achassem um contra-exemplo) da afirmação.
Postar um comentário