Encontro de Ensino, Pesquisa e Extensão, Presidente Prudente, 20 a 23 de outubro, 2014
1
APLICAÇÕES DO PEQUENO TEOREMA DE FERMAT
APPLICATIONS OF THE FERMAT'S LITTLE THEOREM
Vanessa de Freitas Travello1; Luana Beatriz Cardoso¹; Juliano Ferreira
Lima¹; Thiago Mariano Viana¹; Antonio Carlos Tamarozzi².
Universidade Federal de Mato Grosso do Sul – UFMS, Três Lagoas. MS. e-mail:
1
[email protected].
Bolsista do Grupo PET MATEMÁTICA –
Matemática/CPTL/UFMS.
²Tutor
do
Grupo
PET
MATEMÁTICA
–
Matemática/CPTL/UFMS
RESUMO - O Pequeno Teorema de Fermat é um resultado de impacto
para a divisibilidade na Teoria dos Números. O tema foi inserido como
parte de um projeto de iniciação cientifica desenvolvida pelos autores
como uma das atividades do grupo PET/Matemática da UFMS/Campus
de Três Lagoas. O desenvolvimento do projeto foi realizado através de
levantamento bibliográfico, estudo teórico do assunto, discussões e
apresentações de seminários com a orientação do tutor e elaboração
do relatório final. O trabalho propiciou contato com algumas das
técnicas comumente utilizadas em problemas introdutórios da teoria
dos números, mais especificamente a análise de congruências. Como
aplicações foram estabelecidas diversas congruências importantes,
algumas delas de impacto para o desenvolvimento da Teoria dos
Números. O estudo pode ser estendido a resultados com a função de
Euler, em consequência pode ser apresentado o funcionamento do
método criptográfico RSA que, constitui uma aplicação extremamente
poderosa desta teoria Matemática.
Palavras-chave - Teste de Primalidade, Criptografia, Teoria dos
números.
ABSTRACT - Fermat's Little Theorem is a result of impact for
divisibility in Number Theory. The theme was inserted as part of a
research project developed by the authors as one of the activities of
the group PET/Math UFMS/CPTL. The development project was
conducted through a literature review, theoretical study of the subject,
discussions and seminar presentations with guidance from the tutor
and preparing the final report. The work led to contact with some of
the techniques commonly used in introductory problems of number
theory, specifically the analysis of congruences. As applications several
important congruences, some impact to the development of the
Theory of Numbers were established. The study was extended to
results with the Euler function, therefore the operation of the RSA
cryptographic method that is an extremely powerful Maths application
of this theory can be displayed.
Keywords - Primality test, Cryptography, number theory.
Colloquium Exactarum, vol. 6, n. Especial, Jul–Dez, 2014, p. 01-10. ISSN: 2178-8332. DOI: 10.5747/ce.2014.v6.nesp.000077
Encontro de Ensino, Pesquisa e Extensão, Presidente Prudente, 20 a 23 de outubro, 2014
2
1 INTRODUÇÃO
Pierre de
2 METODOLOGIA
Fermat
não
era
um
O trabalho é resultado de uma
matemático de fato, prestava serviço como
pesquisa teórica, desenvolvido através de
juiz e dedicava-se à Matemática em suas
discussões do tema com o orientador e
horas de lazer. Assim foi considerado um
apresentações de seminários como parte das
matemático amador e conhecido como o
atividades do programa PET - Matemática no
“Príncipe dos Amadores”. A influencia de
estudo de Introdução à Teoria dos números.
Fermat na matemática foi limitada pela não
O trabalho incluiu uma etapa de
publicação de seus trabalhos e descobertas.
leitura
Assim como outros matemáticos, suas
desenvolvimento das atividades propostas e
pesquisas eram conhecidas através de cartas
um relatório dissertativo dos resultados
e anotações enviadas a amigos e também
obtidos.
matemáticos.
desenvolvidas foram avaliados através da
Fermat estudou diversas áreas da
e
resoluções
O
estudo
de
e
exercícios,
as
atividades
apresentação de seminários de discussões.
matemática, mas foi graças aos seus estudos
em Teoria dos Números que ele ficou
3 RESULTADOS
famoso. Foi o primeiro a descobrir e enunciar
O resultado de Pierre de Fermat,
o Pequeno Teorema de Fermat, apesar de
conhecido como Pequeno Teorema de
que a demonstração de tal teorema ter sido
Fermat, pode ser assim enunciado:
dada por Euler.
Este trabalho tem como objetivo o
aprimoramento das teorias algébricas com
3.1 TEOREMA DE FERMAT - Dados
inteiros com
(
base em congruência e suas aplicações. A
e
primo, então
)
|(
)
execução deste trabalho como método de
Para a demonstração desse teorema
investigação cientifica, propiciou a inserção
dos alunos do PET (Programa de Educação
utilizamos o lema: Seja
um número primo.
Tutorial) envolvidos na pesquisa Matemática,
Os números da forma ( ), onde
através do desenvolvimento de ferramentas
são todos divisíveis por .
,
introdutórias para a teoria dos números e,
em consequência, a ramos importantes da
Demonstração do teorema - Vamos provar o
Matemática.
resultado por indução sobre , com
resultado vale claramente para
| .
Colloquium Exactarum, vol. 6, n. Especial, Jul–Dez, 2014, p. 01-10. ISSN: 2178-8332. DOI: 10.5747/ce.2014.v6.nesp.000077
.O
, pois
Encontro de Ensino, Pesquisa e Extensão, Presidente Prudente, 20 a 23 de outubro, 2014
3
Supondo o resultado válido para
iremos prova-lo para
. Pela formula
do binômio de Newton,
(
( )
TEOREMA
FERMAT

e
um primo que
(
)
) .
Pelo lema apresentado acima e pela
hipótese de indução, o segundo membro da
igualdade acima é divisível por . Que é o
que queríamos provar.
Demonstração - Pelo Pequeno Teorema de
Fermat 3.1 temos que
|
e como (
que
Notação: utilizaremos (
| (
)
),
segue-se imediatamente,
divide
.
) para designar o
máximo divisor comum entre os números
Observação: Temos como consequência
desse teorema o teste de não primalidade,
.
que é dado por: Seja
Pode-se mostrar que a recíproca do
fato, considerando
)
(
)
e
(
, então
Note
essa condição é equivalente a (
pois
que
)
,
não é primo.
teorema de Fermat, serão apresentadas duas
proposições importantes de congruência e
A proposição seguinte é um resultado
Por outro lado
)
tal que se
divisibilidade de números primos.
.
(
)
, se
Antes de apresentar as aplicações do
tal que
)
com
com (
existir um
Pequeno Teorema de Fermat não é valida. De
(
(SEGUNDA
, tem-se,
)
(
inteiros
DE
VERSÃO) - Dados
não divide
(
)
3.2
(
)
(
clássico que caracteriza os números primos.
)
e portanto, pelo pequeno teorema de Fermat
|(
|(
)
|(
)
3.3 PROPOSIÇÃO – Sejam
)
primo. Se |
.
para todo
tal que (
)
,
, Mas 561
que
(
|
, então existe tal
. Vamos supor que
)
, com
então | ou | .
Demonstração - Se
Segue-se daí que 561 divide
e
Assim, existe
então
tais que
não é primo.
Multiplicando
O Pequeno Teorema de Fermat
em ambos os lados da
igualdade acima, temos que
adquire outro formato que pode ser assim
descrito:
Colloquium Exactarum, vol. 6, n. Especial, Jul–Dez, 2014, p. 01-10. ISSN: 2178-8332. DOI: 10.5747/ce.2014.v6.nesp.000077
Encontro de Ensino, Pesquisa e Extensão, Presidente Prudente, 20 a 23 de outubro, 2014
4
substituindo
por
nesta
última
igualdade, temos que
Teorema
de
Fermat,
para
melhor
entendimento do conceito dado.
(
)
1.
e portanto | .
Seja
primo maior que 2,
provaremos que
(
De forma análoga suponhamos que
(
| .
e chegamos que
Portanto | ou |
)
)
Prova:
Vamos analisar a congruência de cada uma
A
proposição
consequências
seguinte
importantes
tem
para
das parcelas do primeiro membro.
|
este
(
trabalho:
, com
(
e
não ambos nulos, temos que | e |
equivale que (
)
Demonstração - temos que | e | implica
que
com
como ((
) (
)
)
)
)
segue que (
que
assim
(
| ,o
).
)
|( — )
(
)
ou
seja
).
Portanto, somando congruências, obtemos
que
que implica que
(
(
como
temos
Assim prosseguindo obtemos similarmente
(
)
temos
que
. Logo
(
assim
|
(
(
que
).
que
| .
temos
).
|
3.4 PROPOSIÇÃO - Dado
assim
)
(
Dado que, (
o resultado segue.
)
)
)
(
) , segue
por transitividade que
Observação:
Um
caso
particular
da
(
(
proposição 3.4 é o seguinte resultado: dados
, com
e
que | e | . Então
)
)
primos entre si, tais
| .
2.
Encontrar o resto da divisão de
por 17.
Com
o
trabalho
de
pesquisa,
exploramos algumas aplicações do Pequeno
Temos que 17 é primo e não divide 2,
então pelo Pequeno Teorema de Fermat
Colloquium Exactarum, vol. 6, n. Especial, Jul–Dez, 2014, p. 01-10. ISSN: 2178-8332. DOI: 10.5747/ce.2014.v6.nesp.000077
Encontro de Ensino, Pesquisa e Extensão, Presidente Prudente, 20 a 23 de outubro, 2014
5
(
),
O resultado segue da seguinte fatoração
(
mas 100 000 = (6 250) (16).
(
Portanto
[(
)
]
(
(
)(
(
)
(
)
Assim, temos pelo Pequeno Teorema
por
|
é
)
)(
)(
)(
)(
)
)
haja vista que, pelo pequeno teorema de
Fermat,
de Fermat que o resto da divisão de
)
(
temos que
)
.
4. Mostraremos que, para todo
3. Usamos o Teorema para mostrar
que
|
,
é natural o número:
para todo número inteiro .
Temos que 42 é divisível por 2, 3 e 7
sendo estes números primos entre si. De
Prova: Efetuamos inicialmente a seguinte
simplificação da expressão dada:
acordo com a proposição 3.4, é suficiente
verificarmos que cada um deles divide
. Esta verificação será feita nos itens
(
a) ,b) e c) que seguem:
(
a)
)
por
)
(
Fermat.
Temos pelo Pequeno Teorema de
Fermat que
é divisível por 5, ou seja
(
|
.
)e
(
seja
Temos
)
)
(
(
((
)
)(
é divisível por 3, ou
). Assim existem
tais que
(
( )
uma
aplicação direta do Pequeno teorema de
b)
)
e
,
, logo
substituindo em (*) teremos:
)
)(
)
(
)
(
)
Pelo Pequeno Teorema de Fermat
(
temos que
)
que é suficiente para termos |
|
o
.
assim temos que
c)
|
.
número natural para todo
Colloquium Exactarum, vol. 6, n. Especial, Jul–Dez, 2014, p. 01-10. ISSN: 2178-8332. DOI: 10.5747/ce.2014.v6.nesp.000077
é um
.
Encontro de Ensino, Pesquisa e Extensão, Presidente Prudente, 20 a 23 de outubro, 2014
6
5. Podemos verificar que, para todo
|(
).
|(
)e
)(
)
(
)(
)(
)
Como sabemos, 5 é primo ,
Temos que 15 é divisível por 3 e 5,
logo basta provar que | (
(
, segue que |
e
.
) , o que será feito nos
itens seguintes:
b)
Se
a)
, então |
,
,
.
Temos pelo Pequeno Teorema de
Temos claramente que
(
|(
)(
)(
)
)(
)
Como sabemos
, de acordo com o Pequeno
Teorema de Fermat. Logo segue que
, mas
(
é
divisível por 5, sendo o mesmo ocorrendo
com
então |
Fermat que se
.
e
|(
, segue da proposição 3.3 que
)
).
b)
7. Mostraremos que
divisível por 13, se
Temos que
porque,
|
é divisível por 3,
(pelo pequeno teorema de
Fermat). Dado que |
é imediato,
Mostraremos
e
são primos com 13.
também
divisível por 91, se
e
é
que
é
são primos com 91.
Solução:
Sendo (
a)
segue que 3 também divide a soma, ou seja,
|
)
e
b)
um divisor. Logo, pela proposição 3.4 temos
que 15|
(
c)
Uma análise similar mostra que 5 também é
|
)
, mostremos que
. Mas
, para qualquer
.
6.
Seja
a)
Se
então |
.
Como
Mostremos que:
,
,
,
Fermat que se
então |
, mas
, segue do
Pequeno Teorema de Fermat,
|
Temos pelo Pequeno Teorema de
e
|
e
. Em particular, temos que 13
também divide o oposto, ou seja, 13|
Portanto
|
Colloquium Exactarum, vol. 6, n. Especial, Jul–Dez, 2014, p. 01-10. ISSN: 2178-8332. DOI: 10.5747/ce.2014.v6.nesp.000077
Encontro de Ensino, Pesquisa e Extensão, Presidente Prudente, 20 a 23 de outubro, 2014
7
(
|
d)
)(
)(
)(
)
E segue imediatamente o resultado.
Temos que 91 é divisível somente por
|
ii)
(
7 e 13, que são primos entre si. Logo é
(
suficiente mostrarmos que 7 e 13 são
divisores de
(
. Observemos que
)
)(
)(
)
)(
)
Assim pelo Pequeno teorema de Fermat
(
(
)
)(
)
(
)
(
(
temos que
)(
)
)
|
Logo
|
Agora basta provarmos que temos a
soma de dois produtos divisíveis por 7.
Como (
)
então
, logo
iii)
|
(
temos pelo Pequeno teorema de Fermat que
|
= (
. Da mesma forma o somando
(
)(
|
assim
assegurado
|
e
|
que
)(
)
Assim pelo Pequeno teorema de Fermat
) é divisível por 7.
Como 7 divide as duas partes da
soma,
)
já
temos
,
resulta
(
temos que
)
|
Logo
|
, como desejado.
iv)
8.
|
.
(
Provaremos que para todo
, o número
definição
(
)(
)
Assim pelo Pequeno teorema de Fermat
5, 7, 13 e 273.
Da
(
é divisível por 2, 3,
)
de
congruência
) temos que |
.
(
temos que
)
|
Logo
|
Temos que 273 é divisível por 3,7 e
13; assim basta mostrarmos que 3,7 e 13
divide
i)
v)
(proposição 3.4).
Essa é uma aplicação direta do pequeno
|
(
|
(
)
(
)(
)(
)(
teorema de Fermat
)
)
vi)
|
Colloquium Exactarum, vol. 6, n. Especial, Jul–Dez, 2014, p. 01-10. ISSN: 2178-8332. DOI: 10.5747/ce.2014.v6.nesp.000077
Encontro de Ensino, Pesquisa e Extensão, Presidente Prudente, 20 a 23 de outubro, 2014
8
Temos 273 é fatorável por 3, 7, e 13.
3.6 TEOREMA DE EULER-FERMAT – Sejam
Pela proposição 3.4 e por ii), iv) e v) temos
e(
, com
( )
que
|
Demonstração:
)
então
(
)
Seja
( )
sistema reduzido módulo
Apresentaremos agora uma pequena
(
)
introdução ao teorema de Euler, que é uma
(
)
extensão do teorema apresentado neste
um sistema reduzido módulo
trabalho. Necessitamos da definição da
Portanto,
Definição:
, para todo
Designaremos
por
( )
2, que
corresponde à quantidade de números
( )
( )
(
Como
( )
(
)
)
( )
Segue que
naturais entre 0 e m -1 que são primos com
m. Pondo
.
( ) o
,
forma
( )
número de elementos de um sistema
reduzido de resíduos módulo
seja,
. E como
então
( )
função phi de Euler
, ou
um
( )
(
)
, está definida uma
importante função
:
, conhecida
como função phi de Euler.
Um importante resultado da função
de Euler é dado por: Sejam
Observamos que resulta diretamente
(
)
, então
da definição que para todos
(
( )
tais que
)
( )
( ).
Tal resultado não será demonstrado
nesse trabalho.
3.5
PROPOSIÇÃO
( )
-
Se
, então
se, e somente se,
for
primo.
Exemplos
1) Determinemos (
Demonstração: De fato, se
é primo então
o sistema reduzido modulo
é formado por:
( )
Temos que 1024 =
(
)
, assim
)
(
)
Como 2 é primo e usando a consequência da
proposição 3.5 teremos
Utilizando a proposição anterior e
(
)
(
)
(
uma contagem simples, podemos mostrar
que, se
é primo, então
(
)
)
.
Logo, (
)
.
.
Colloquium Exactarum, vol. 6, n. Especial, Jul–Dez, 2014, p. 01-10. ISSN: 2178-8332. DOI: 10.5747/ce.2014.v6.nesp.000077
Encontro de Ensino, Pesquisa e Extensão, Presidente Prudente, 20 a 23 de outubro, 2014
9
2) Ache o resto da divisão 34|
Pequeno Teorema de Fermat para quaisquer
Temos que
(
)
números inteiros, utilizando, para isso a
( ) (
)
(
função
)(
)
ser apresentado o funcionamento do método
Então pelo teorema de Euler-Fermat
(
de Euler, em consequência pode
)
criptográfico
RSA
que,
constitui
uma
aplicação extremamente poderosa desta
Assim
teoria Matemática.
(
(
)
)
(
(
)
A sequência didática apresentada
)
neste trabalho teve resultados de impacto
Portanto 13 é o resto da divisão de
por
34.
motivador para o estudo da Matemática,
desenvolvido com alunos do curso de
Licenciatura em Matemática.
4 DISCUSSÃO
Ao longo do trabalho estudamos
AGRADECIMENTOS
congruências e divisibilidade sob a ótica do
Os autores agradecem ao programa
Pequeno Teorema de Fermat. A partir deste
de Educação Tutorial (PET-MAT), o apoio
resultado
financeiro.
obtemos
apresentações
de
problemas da álgebra básica com maior
elegância e precisão, alem de possibilitar
REFERÊNCIAS
generalizações importantes.
COUTINHO, Severino C., Números Inteiros e
Criptografia RSA, Série Computação e
Matemática, SBM, 1997.
5 CONSIDERAÇÕES FINAIS
O trabalho propiciou contato com
DOMINGUES,
Hygino
moderna,São Paulo: Atual, 2003.
H.,Álgebra
algumas das técnicas comumente utilizadas
em problemas introdutórios da teoria dos
números, mais especificamente a análise de
congruências.
estabelecidas
Como
aplicações
diversas
foram
congruências
importantes, algumas delas de impacto para
HEFEZ, Abramo. Elementos de Aritmética. 2
ed. Rio de Janeiro, RJ: SBM, 2006. iv, 169.
(textos universitários).
MARTINEZ, Fabio Brochero; et al. Teoria dos
números: um passeio com primos e outros
números familiares pelo mundo inteiro, 2 ed.
Rio de Janeiro: IMPA, 2011
o desenvolvimento da Teoria dos Números.
A continuidade do estudo deste tema
pode ser estendido a resultados com a
SANTOS, José Plínio de Oliveira. Introdução à
Teoria dos Números. Rio de Janeiro, Instituto
de Matemática Pura e Aplicada, CNPq,1998.
função de Euler que visa generalizar o
Colloquium Exactarum, vol. 6, n. Especial, Jul–Dez, 2014, p. 01-10. ISSN: 2178-8332. DOI: 10.5747/ce.2014.v6.nesp.000077
Encontro de Ensino, Pesquisa e Extensão, Presidente Prudente, 20 a 23 de outubro, 2014
10
SCHEINERMAN, Edward R. Matemática
discreta: uma introdução. Tradução da 2. Ed.
Norte americana. São Paulo: Cengage
learning, 2011
Colloquium Exactarum, vol. 6, n. Especial, Jul–Dez, 2014, p. 01-10. ISSN: 2178-8332. DOI: 10.5747/ce.2014.v6.nesp.000077