Aplicações Do Pequeno Teorema de Fermat

Encontro de Ensino, Pesquisa e Extenso, Presidente Prudente, 20 a 23 de outubro, 2014 1

Colloquium Exactarum, vol. 6, n. Especial, JulDez, 2014, p. 01-10. ISSN: 2178-8332. DOI: 10.5747/ce.2014.v6.nesp.000077

APLICAES 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, Trs Lagoas. MS. e-mail: [email protected].

1Bolsista do Grupo PET MATEMTICA

Matemtica/CPTL/UFMS. Tutor do Grupo PET MATEMTICA Matemtica/CPTL/UFMS

RESUMO - O Pequeno Teorema de Fermat um resultado de impacto para a divisibilidade na Teoria dos Nmeros. O tema foi inserido como parte de um projeto de iniciao cientifica desenvolvida pelos autores como uma das atividades do grupo PET/Matemtica da UFMS/Campus de Trs Lagoas. O desenvolvimento do projeto foi realizado atravs de levantamento bibliogrfico, estudo terico do assunto, discusses e apresentaes de seminrios com a orientao do tutor e elaborao do relatrio final. O trabalho propiciou contato com algumas das tcnicas comumente utilizadas em problemas introdutrios da teoria dos nmeros, mais especificamente a anlise de congruncias. Como aplicaes foram estabelecidas diversas congruncias importantes, algumas delas de impacto para o desenvolvimento da Teoria dos Nmeros. O estudo pode ser estendido a resultados com a funo de Euler, em consequncia pode ser apresentado o funcionamento do mtodo criptogrfico RSA que, constitui uma aplicao extremamente poderosa desta teoria Matemtica. Palavras-chave - Teste de Primalidade, Criptografia, Teoria dos nmeros. 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.



1 INTRODUO

Pierre de Fermat no era um

matemtico de fato, prestava servio como

juiz e dedicava-se Matemtica em suas

horas de lazer. Assim foi considerado um

matemtico amador e conhecido como o

Prncipe dos Amadores. A influencia de

Fermat na matemtica foi limitada pela no

publicao de seus trabalhos e descobertas.

Assim como outros matemticos, suas

pesquisas eram conhecidas atravs de cartas

e anotaes enviadas a amigos e tambm

matemticos.

Fermat estudou diversas reas da

matemtica, mas foi graas aos seus estudos

em Teoria dos Nmeros que ele ficou

famoso. Foi o primeiro a descobrir e enunciar

o Pequeno Teorema de Fermat, apesar de

que a demonstrao de tal teorema ter sido

dada por Euler.

Este trabalho tem como objetivo o

aprimoramento das teorias algbricas com

base em congruncia e suas aplicaes. A

execuo deste trabalho como mtodo de

investigao cientifica, propiciou a insero

dos alunos do PET (Programa de Educao

Tutorial) envolvidos na pesquisa Matemtica,

atravs do desenvolvimento de ferramentas

introdutrias para a teoria dos nmeros e,

em consequncia, a ramos importantes da

Matemtica.

2 METODOLOGIA

O trabalho resultado de uma

pesquisa terica, desenvolvido atravs de

discusses do tema com o orientador e

apresentaes de seminrios como parte das

atividades do programa PET - Matemtica no

estudo de Introduo Teoria dos nmeros.

O trabalho incluiu uma etapa de

leitura e resolues de exerccios,

desenvolvimento das atividades propostas e

um relatrio dissertativo dos resultados

obtidos. O estudo e as atividades

desenvolvidas foram avaliados atravs da

apresentao de seminrios de discusses.

3 RESULTADOS

O resultado de Pierre de Fermat,

conhecido como Pequeno Teorema de

Fermat, pode ser assim enunciado:

3.1 TEOREMA DE FERMAT - Dados e

inteiros com primo, ento

( ) |( )

Para a demonstrao desse teorema

utilizamos o lema: Seja um nmero primo.

Os nmeros da forma ( ), onde ,

so todos divisveis por .

Demonstrao do teorema - Vamos provar o

resultado por induo sobre , com . O

resultado vale claramente para , pois

| .



Supondo o resultado vlido para

iremos prova-lo para . Pela formula

do binmio de Newton,

( ) ( )

( ) (

) .

Pelo lema apresentado acima e pela

hiptese de induo, o segundo membro da

igualdade acima divisvel por . Que o

que queramos provar.

Notao: utilizaremos ( ) para designar o

mximo divisor comum entre os nmeros

inteiros .

Pode-se mostrar que a recproca do

Pequeno Teorema de Fermat no valida. De

fato, considerando e tal que

( ) ( ) ( ) Note que

essa condio equivalente a ( ) ,

pois .

Por outro lado

( ) ( ) ( )

e portanto, pelo pequeno teorema de Fermat

|( ) |( )

|( ) .

Segue-se da que 561 divide ,

para todo tal que ( ) , Mas 561

no primo.

O Pequeno Teorema de Fermat

adquire outro formato que pode ser assim

descrito:

3.2 TEOREMA DE FERMAT (SEGUNDA

VERSO) - Dados e um primo que

no divide , tem-se,

( )

Demonstrao - Pelo Pequeno Teorema de

Fermat 3.1 temos que

| | ( ),

e como ( ) segue-se imediatamente,

que divide .

Observao: Temos como consequncia

desse teorema o teste de no primalidade,

que dado por: Seja com , se

existir um com ( ) tal que se

, ento no primo.

Antes de apresentar as aplicaes do

teorema de Fermat, sero apresentadas duas

proposies importantes de congruncia e

divisibilidade de nmeros primos.

A proposio seguinte um resultado

clssico que caracteriza os nmeros primos.

3.3 PROPOSIO Sejam e , com

primo. Se | ento | ou | .

Demonstrao - Se | , ento existe tal

que . Vamos supor que ento

( ) Assim, existe tais que

Multiplicando em ambos os lados da

igualdade acima, temos que



substituindo por nesta ltima

igualdade, temos que

( )

e portanto | .

De forma anloga suponhamos que

e chegamos que | .

Portanto | ou |

A proposio seguinte tem

consequncias importantes para este

trabalho:

3.4 PROPOSIO - Dado , com e

no ambos nulos, temos que | e |

equivale que

( )| .

Demonstrao - temos que | e | implica

que com . Logo

( )

( )

como (

( )

( )) segue que

( )| ,o

que implica que

( )

como o resultado segue.

Observao: Um caso particular da

proposio 3.4 o seguinte resultado: dados

, com e primos entre si, tais

que | e | . Ento | .

Com o trabalho de pesquisa,

exploramos algumas aplicaes do Pequeno

Teorema de Fermat, para melhor

entendimento do conceito dado.

1. Seja primo maior que 2,

provaremos que

( )

( )

Prova:

Vamos analisar a congruncia de cada uma

das parcelas do primeiro membro.

| assim temos que

( ).

| assim temos que

( ).

| assim temos

que ( ).

Assim prosseguindo obtemos similarmente

que

( ) |( ) ou seja

( ) ( ).

Portanto, somando congruncias, obtemos

que

( )

( )

Dado que, ( ) ( ) , segue

por transitividade que

( )

( )

2. Encontrar o resto da diviso de

por 17.

Temos que 17 primo e no divide 2,

ento pelo Pequeno Teorema de Fermat



( ),

mas 100 000 = (6 250) (16).

Portanto

[( ) ] ( )

( )

Assim, temos pelo Pequeno Teorema

de Fermat que o resto da diviso de

por

3. Usamos o Teorema para mostrar

que | para todo nmero inteiro .

Temos que 42 divisvel por 2, 3 e 7

sendo estes nmeros primos entre si. De

acordo com a proposio 3.4, suficiente

verificarmos que cada um deles divide

. Esta verificao ser feita nos itens

a) ,b) e c) que seguem:

a) ( ) por uma

aplicao direta do Pequeno teorema de

Fermat.

b) | .

Temos

( ) (( )

) ( )( )

( )( )

Pelo Pequeno Teorema de Fermat

temos que ( ) | o

que suficiente para termos | .

c) | .

O resultado segue da seguinte fatorao

( )

( )( )

( )( )( )

( )( )( )

haja vista que, pelo pequeno teorema de

Fermat, temos que ( )

| .

4. Mostraremos que, para todo ,

natural o nmero:

Prova: Efetuamos inicialmente a seguinte

simplificao da expresso dada:

( )

( ) ( )

Temos pelo Pequeno Teorema de

Fermat que divisvel por 5, ou seja

( ) e divisvel por 3, ou

seja ( ). Assim existem ,

tais que e , logo

substituindo em (*) teremos:

( )

( )

assim temos que um

nmero natural para todo .



5. Podemos verificar que, para todo

| ( ) .

Temos que 15 divisvel por 3 e 5,

logo basta provar que | ( ) e

|( ) , o que ser feito nos

itens seguintes:

a)

.

Temos claramente que

divisvel por 5, sendo o mesmo ocorrendo

com , de acordo com o Pequeno

Teorema de Fermat. Logo segue que

| ( ).

b)

Temos que divisvel por 3,

porque, | (pelo pequeno teorema de

Fermat). Dado que | imediato,

segue que 3 tambm divide a soma, ou seja,

|

Uma anlise similar mostra que 5 tambm

um divisor. Logo, pela proposio 3.4 temos

que 15| , para qualquer

.

6. Seja Mostremos que:

a) Se , , ,

ento | .


Fermat que se ento | , mas

( )( )

( )( )( )

Como sabemos, 5 primo ,

e , segue que | .

b) Se , ,

, ento | .


Fermat que se ento | , mas

( )( )

( )( )( )

Como sabemos e

, segue da proposio 3.3 que |(

)

7. Mostraremos que

divisvel por 13, se e so primos com 13.

Mostraremos tambm que

divisvel por 91, se e so primos com 91.

Soluo:

a) Sendo ( ) e

b)

c) ( ) , mostremos que

| . Mas

Como e , segue do

Pequeno Teorema de Fermat, | e

| . Em particular, temos que 13

tambm divide o oposto, ou seja, 13|

Portanto

|



d) |

Temos que 91 divisvel somente por

7 e 13, que so primos entre si. Logo

suficiente mostrarmos que 7 e 13 so

divisores de . Observemos que

( ) ( )

( )( ) ( )( )

Agora basta provarmos que temos a

soma de dois produtos divisveis por 7.

Como ( ) ento , logo

temos pelo Pequeno teorema de Fermat que

| . Da mesma forma o somando

( )( ) divisvel por 7.

Como 7 divide as duas partes da

soma, assim | e j temos

assegurado que | , resulta

| , como desejado.

8. Provaremos que para todo

, o nmero divisvel por 2, 3,

5, 7, 13 e 273.

Da definio de congruncia

( ) temos que | .

Temos que 273 divisvel por 3,7 e

13; assim basta mostrarmos que 3,7 e 13

divide (proposio 3.4).

i) |

( )

( )( )

( )( )( )

( )( )( )( )

E segue imediatamente o resultado.

ii) |

( )

( )( )

( )( )( )

Assim pelo Pequeno teorema de Fermat

temos que ( ) |

Logo

|

iii) |

( )

= ( )( )


temos que ( ) |

Logo

|

iv) | .

( )

( )( )


temos que ( ) |

Logo

|

v) |

Essa uma aplicao direta do pequeno

teorema de Fermat

vi) |



Temos 273 fatorvel por 3, 7, e 13.

Pela proposio 3.4 e por ii), iv) e v) temos

que

|

Apresentaremos agora uma pequena

introduo ao teorema de Euler, que uma

extenso do teorema apresentado neste

trabalho. Necessitamos da definio da

funo phi de Euler

Definio: Designaremos por ( ) o

nmero de elementos de um sistema

reduzido de resduos mdulo , 2, que

corresponde quantidade de nmeros

naturais entre 0 e m -1 que so primos com

m. Pondo ( ) , est definida uma

importante funo : , conhecida

como funo phi de Euler.

Observamos que resulta diretamente

da definio que para todos

( )

3.5 PROPOSIO - Se , ento

( ) se, e somente se, for

primo.

Demonstrao: De fato, se primo ento

o sistema reduzido modulo formado por:

( )

Utilizando a proposio anterior e

uma contagem simples, podemos mostrar

que, se primo, ento

( ) .

3.6 TEOREMA DE EULER-FERMAT Sejam

, com e ( ) ento

( ) ( )

Demonstrao: Seja ( ) um

sistema reduzido mdulo , ou seja,

( ) , para todo . E como

( ) ento ( ) forma

um sistema reduzido mdulo .

Portanto,

( ) ( )

( )

( ) ( )

Como ( ) ( )

Segue que

( ) ( )

Um importante resultado da funo

de Euler dado por: Sejam tais que

( ) , ento

( ) ( ) ( ).

Tal resultado no ser demonstrado

nesse trabalho.

Exemplos

1) Determinemos ( )

Temos que 1024 = , assim

( ) ( )

Como 2 primo e usando a consequncia da

proposio 3.5 teremos

( ) ( ) ( )

.

Logo, ( ) .



2) Ache o resto da diviso 34|

Temos que

( ) ( ) ( )

( )( )

Ento pelo teorema de Euler-Fermat

( )

Assim

( ) ( ) ( )

( )

Portanto 13 o resto da diviso de por

34.

4 DISCUSSO

Ao longo do trabalho estudamos

congruncias e divisibilidade sob a tica do

Pequeno Teorema de Fermat. A partir deste

resultado obtemos apresentaes de

problemas da lgebra bsica com maior

elegncia e preciso, alem de possibilitar

generalizaes importantes.

5 CONSIDERAES FINAIS

O trabalho propiciou contato com

algumas das tcnicas comumente utilizadas

em problemas introdutrios da teoria dos

nmeros, mais especificamente a anlise de

congruncias. Como aplicaes foram

estabelecidas diversas congruncias

importantes, algumas delas de impacto para

o desenvolvimento da Teoria dos Nmeros.

A continuidade do estudo deste tema

pode ser estendido a resultados com a

funo de Euler que visa generalizar o

Pequeno Teorema de Fermat para quaisquer

nmeros inteiros, utilizando, para isso a

funo de Euler, em consequncia pode

ser apresentado o funcionamento do mtodo

criptogrfico RSA que, constitui uma

aplicao extremamente poderosa desta

teoria Matemtica.

A sequncia didtica apresentada

neste trabalho teve resultados de impacto

motivador para o estudo da Matemtica,

desenvolvido com alunos do curso de

Licenciatura em Matemtica.

AGRADECIMENTOS

Os autores agradecem ao programa

de Educao Tutorial (PET-MAT), o apoio

financeiro.

REFERNCIAS

COUTINHO, Severino C., Nmeros Inteiros e Criptografia RSA, Srie Computao e Matemtica, SBM, 1997. DOMINGUES, Hygino H.,lgebra moderna,So Paulo: Atual, 2003. HEFEZ, Abramo. Elementos de Aritmtica. 2 ed. Rio de Janeiro, RJ: SBM, 2006. iv, 169. (textos universitrios). MARTINEZ, Fabio Brochero; et al. Teoria dos nmeros: um passeio com primos e outros nmeros familiares pelo mundo inteiro, 2 ed. Rio de Janeiro: IMPA, 2011 SANTOS, Jos Plnio de Oliveira. Introduo Teoria dos Nmeros. Rio de Janeiro, Instituto de Matemtica Pura e Aplicada, CNPq,1998.



SCHEINERMAN, Edward R. Matemtica discreta: uma introduo. Traduo da 2. Ed. Norte americana. So Paulo: Cengage learning, 2011

Documents

Aplicações Do Pequeno Teorema de Fermat