100% acharam este documento útil (1 voto)

24 visualizações137 páginas

Números Inteiros e Criptografia RSA

Este documento apresenta um resumo de um trabalho de conclusão de curso sobre números inteiros e criptografia RSA. O trabalho discute conceitos fundamentais de teoria dos números como algoritmos de divisão, fatoração, primos e aritmética modular, e como esses conceitos são aplicados no sistema criptográfico RSA.

Enviado por

Direitos autorais

Levamos muito a sério os direitos de conteúdo. Se você suspeita que este conteúdo é seu, reivindique-o aqui.

Formatos disponíveis

Baixe no formato PDF, TXT ou leia on-line no Scribd

100% acharam este documento útil (1 voto)

24 visualizações137 páginas

Números Inteiros e Criptografia RSA

Enviado por

Direitos autorais

Levamos muito a sério os direitos de conteúdo. Se você suspeita que este conteúdo é seu, reivindique-o aqui.

Formatos disponíveis

Baixe no formato PDF, TXT ou leia on-line no Scribd

Universidade Federal de São Carlos

Centro de Ciências Exatas e de Tecnologia

Departamento de Matemática

Números Inteiros e Criptografia RSA

Autor: Allan Roberto Fabossi

Orientador: Tomas Edson Barros

Disciplina: Trabalho de Conclusão do Curso B

Curso: Licenciatura em Matemática

Professores Responsáveis: Karina Schiabel Silva

Sadao Massago
Vera Lúcia Carbone

São Carlos, 30 de Janeiro de 2013.

Números Inteiros e Criptografia RSA

Autor: Allan Roberto Fabossi

Orientador: Tomas Edson Barros

Disciplina: Trabalho de Conclusão do Curso B

Curso: Licenciatura em Matemática

Professores Responsáveis: Karina Schiabel Silva

Sadao Massago
Vera Lúcia Carbone

Instituição: Universidade Federal de São Carlos

Centro de Ciências Exatas e de Tecnologia
Departamento de Matemática

São Carlos, 30 de Janeiro de 2013.

Allan Roberto Fabossi (aluno) Tomas Edson Barros (orientador)

“Sempre me pareceu estranho que todos aqueles que estudam
seriamente esta ciência acabam tomados de uma espécie de paixão
pela mesma. Em verdade, o que proporciona o máximo de prazer
não é o conhecimento e sim a aprendizagem, não é a posse, mas a
aquisição, não é a presença, mas o ato de atingir a meta.”

Carl Friedrich Gauss

Agradecimentos

Agradeço a meus pais, Marcos e Ester Fabossi, que sempre priorizaram minha educação e me
deram as condições necessárias para seguir minha vida escolar.
Também agradeço ao meu orientador, Prof. Dr. Tomas Edson Barros, que contribuiu de
maneira significativa para a realização deste trabalho e para minha formação, de modo geral.
Finalmente, agradeço a cada professor de Matemática que tive durante toda minha vida esco-
lar. Cada um deles me influenciou para que seguisse pelos caminhos da Matemática. Agradeço
de maneira especial a dois desses professores: Profa. Maria Ângela, que incentivou meu gosto
pela Matemática ao propiciar minha participação em olimpı́adas e maratonas de Matemática; e
Prof. Chico Nery, o qual foi e ainda é meu maior mestre, decisivo nas minhas escolhas por um
curso de Graduação em Matemática e pela carreira docente, e do qual hoje tenho o prazer de ser
amigo pessoal e de trabalho.
Resumo

Quando ouvimos falar de criptografia, associamos esse conceito a filmes policiais e de guerra,
onde mensagens secretas são codificadas e decodificadas. No entanto, a abrangência desse ramo
do conhecimento é muito maior que isso. Dentre as diversas aplicações da criptografia destaca-se
a proteção de informações bancárias e comerciais que transitam entre computadores numa rede.
Para a confecção deste texto, estudamos os principais conceitos de teoria dos números, neces-
sários para o entendimento de um dos métodos criptográficos mais populares atualmente, o RSA.
A bibliografia adotada se preocupa mais em focar certos algoritmos para determinação de primos
e outros elementos de teoria dos números, no entanto, buscamos demonstrar todos os resultados
relevantes de forma rigorosa.
Como recomendação da banca avaliadora do TCC A, estudamos o algoritmo AKS, tendo como
base [04]. Entretando, fizemos apenas alguns comentários, relacionando o AKS com o sistema
RSA, não descrevendo no presente texto os detalhes estudados.
Conteúdo

Introdução xi

1 Algoritmo da Divisão de Euclides e Divisibilidade 1

1.1 Divisão Euclidiana . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1
1.2 O Algoritmo de Euclides . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 3
1.3 Algoritmo Euclidiano Estendido . . . . . . . . . . . . . . . . . . . . . . . . . . . . 5

2 Fatoração Única 15
2.1 Teorema Fundamental da Aritmética . . . . . . . . . . . . . . . . . . . . . . . . . 15
2.2 Algoritmos de Fatoração . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 18

3 Números Primos 25
3.1 Fórmulas Polinomiais . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 25
3.2 Fórmulas Exponenciais: Mersenne e Fermat . . . . . . . . . . . . . . . . . . . . . 27
3.3 Fórmulas Fatoriais . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 33

4 Aritmética Modular 37
4.1 Relações de Equivalência . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 37
4.2 Inteiros Módulo n . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 39
4.3 Aplicações . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 43
4.3.1 Critérios de Divisibilidade . . . . . . . . . . . . . . . . . . . . . . . . . . . 43
4.3.2 Potências . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 43
4.3.3 Equações Diofantinas . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 45
4.4 Divisão Modular . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 46

5 Fermat e Primalidade 51
5.1 Pequeno Teorema de Fermat . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 51
5.2 Contando Raı́zes . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 54
5.3 Pseudoprimos . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 60
5.4 Números de Carmichael . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 62

ix
6 Sistemas de Congruências 69
6.1 Equações Lineares . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 69
6.2 Congruência Módulo Números Não Primos Entre Sı́ . . . . . . . . . . . . . . . . . 74
6.3 Potências . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 75
6.4 Partilha de Senhas . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 78

7 Um Pouco de Estruturas Algébricas 81

7.1 Grupos . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 81
7.2 Simetrias . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 82
7.3 Grupos Aritméticos . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 86
7.4 Subgrupos . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 89

8 De Volta à Mersenne e Fermat 95

8.1 Números de Mersenne . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 95
8.2 Números de Fermat . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 97
8.3 O método de Lucas-Lehmer . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 98

9 Raı́zes Primitivas 103

9.1 O teste de Lucas . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 103
9.2 Teorema da Raiz Primitiva . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 106

10 Criptografia RSA 113

10.1 Pré-codificação . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 113
10.2 Codificando e Decodificando . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 114
10.3 O RSA funciona? . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 115
10.4 Segurança do RSA . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 117
10.5 Comentários Finais . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 118
Introdução

O presente texto é resultado de trabalho durante o ano de 2012, referente às disciplinas Trabalho
de Conclusão de Curso A e Trabalho de Conclusão de Curso B.
Desde que entrei na Graduação em Matemática, eu já tinha a intenção de estudar de maneira
mais sistemática a Teoria dos Números. Logo no primeiro perı́odo do curso, tive a disciplina
“Introdução à Teoria dos Números”. Essa disciplina só aumentou meu interesse nessa área da
Matemática. Na hora de escolher o assunto para desenvolvimento do trabalho de conclusão de
curso, não tive dúvidas em escolher a Teoria dos Números como tema central do trabalho.
Neste trabalho, iremos apresentar a Matemática que fundamenta um dos métodos criptográficos
mais populares atualmente, o RSA.
No primeiro capı́tulo veremos o teorema da divisão euclidiana, que justifica o funcionamento
do algoritmo de Euclides, que por sua vez nos permite calcular o máximo divisor comum de dois
inteiros a e b; na sequência veremos o algoritmo euclidiano estendido, que além de calcular o
mdc(a, b) também nos fornece uma maneira de escrever este mdc como combinação linear de a e b.
Veremos também como este algoritmo nos auxilia na resolução de equações diofantinas lineares.
No capı́tulo 2, abordamos o Teorema Fundamental da Aritmética, ou Teorema da Fatoração
Única. Tendo demonstrado que um inteiro positivo n ≥ 2 admite uma única maneira de ser escrito
como produto de primos, veremos alguns algoritmos que nos permitem fatorar um inteiro a dado.
√
Em particular, estudaremos o algoritmo de Fermat, que procura fatores de a próximos à a.
Finalizaremos o capı́tulo vendo uma propriedade fundamental dos primos: se um primo p divide
o produto ab, então p divide a ou b. Tal propriedade será importante nos capı́tulos posteriores.
No Capı́tulo 3 nos voltaremos para os números primos, estudando algumas tentativas que tive-
mos na história de encontrar fórmulas que gerassem primos. Estudaremos rapidamente fórmulas
polinomiais e fórmulas fatoriais, mas vamos nos deter por mais tempo nas fórmulas exponenciais,
estudando os números de Fermat e, principalmente, os números de Mersenne. Em relação a estes
últimos, estudaremos sua relação com os números perfeitos, relação esta estudada desde a Grécia
com Euclides; veremos que todo número perfeito par é da forma 2n−1 (2n − 1), onde o número
2n − 1 é um primo de Mersenne. Finalmente, remontaremos a demonstração feita por Euclides da
existência de infinitos primos.
No capı́tulo 4 revisaremos rapidamente os conceitos básicos de relações de equivalência e estu-
daremos a relação de congruência módulo n nos inteiros, cujo conjunto quociente é denotado por
Zn . Veremos algumas aplicações do conceito de congruência, como demonstrar critérios de divisi-

xi
Capı́tulo 0 Introdução

bilidade, determinar o resto de divisão de potências e determinação da existência de soluções para

equações diofantinas não-lineares. Estudaremos, então, quais as condições para que um elemento
a ∈ Zn possua inverso multiplicativo, e introduziremos o conjunto U (n), conjunto das classes
invertı́veis em Zn . Finalizaremos o capı́tulo introduzindo de maneira sucinta o conceito de raı́zes
primitivas de U (n), conceito que, mais a frente, terá um capı́tulo especı́fico para ser explorado.
No capı́tulo 5 demonstraremos o Pequeno Teorema de Fermat e o usaremos na elaboração de
testes eficazes para detectar números compostos, mas que não funcionam bem para determinar
se um número é primo. Estudaremos rapidamente os números pseudoprimos e os números de
Carmichael, para os quais forneceremos uma caracterização.
No capı́tulo 6, estudaremos equações e sistemas de equações modulares, demonstrando o Al-
goritmo Chinês do Resto. Também veremos duas aplicações deste teorema, uma para o cálculo de
potências módulo n, e outra num método de partilha de senha de um cofre.
No capı́tulo 7 estudaremos de maneira mais detalhada os grupos, com o exemplo do grupo das
simetrias de um triângulo retângulo e os grupos aritméticos. Demonstraremos alguns resultados
gerais para grupos e subgrupos.
No capı́tulo 8 retomaremos o estudo sobre os números de Mersenne e de Fermat. Veremos
estratégias para procurar fatores destes números, e encerramemos o capı́tulo com um teste devido
à E. Lucas, e aperfeiçoado por D. H. Lehmer, para verificar a primalidade de números de Mersenne.
No capı́tulo 9 demonstraremos o teorema da raiz primitiva, veremos uma meneira de calcular
a ordem de um elemento em U (n), e demonstraremos um teste de primalidade que é inspirado no
principal teorema deste capı́tulo, o Teste de Lucas.
Finalmente, no capı́tulo 10, descreveremos o sistema de criptografia RSA, provaremos que
funciona e analisaremos questões sobre sua segurança. Finalizamos o texto com alguns comentários
sobre o algorı́tmo AKS e alguns aspectos de sua relação com o sistema RSA.
Durante o desenvolvimento do texto, admitiremos conhecidos:
• Princı́pio da Boa Ordenação dos Naturais: todo subconjunto não-vazio de N possui um
menor elemento.

• 1o e 2o Princı́pio de Indução Finita: lembramos que estes são equivalentes ao princı́pio da

boa ordenação dos naturais.

• Princı́pio Fundamental da Contagem: se um acontecimento é formado por k estágios su-

cessivos e independentes, com n1 , n2 , n3 , ..., nk possibilidades para cada, então o total de
maneiras distintas de ocorrer este acontecimento é n1 · n2 · n3 · ... · nk .
Também convencionamos as seguintes notações e definições:
• N o conjunto dos naturais; Z o conjunto dos inteiros; Z∗+ o conjunto dos inteiros positivos;
Z+ o conjunto dos inteiros não-negativos; R o conjunto dos números reais; C o conjunto dos
números complexos.

xii
Introdução Seção 0.0

• Sendo x ∈ R, denotamos por [[x ]] a parte inteira de x, ou seja, [[x ]] é o maior inteiro que é
menor ou igual a x.

• Uma partição de um conjunto X é qualquer subconjunto do conjunto das partes de X de

modo que: i) nenhum dos elementos da partição é o conjunto vazio; ii) a intersecção de
quaisquer dois elementos da partição é o conjunto vazio e iii) a união de todos os elementos
da partição de X é igual ao conjunto X.

xiii
Capı́tulo

1
Algoritmo da Divisão de Euclides e
Divisibilidade

É inegável a importância da Matemática em nossos dias, principalmente com os avanços na in-

formática. Atualmente, a troca de informações através de computadores é usada em praticamente
todos os setores: telecomunicações, comércio, indústria, etc. Mas em alguns casos, as informações
que estão sendo enviadas e recebidas não podem ser acessı́veis a qualquer um que interceptar os
dados, por exemplo, na troca de informações referentes à transações bancárias. É nesse ponto
que a criptografia tem sua importância. Do grego kryptós, “escondido”, e gráphein, “escrita”, a
criptografia tem por objetivo codificar uma mensagem que deve ser entendida apenas pelo seu
destinatário. É possı́vel encontrarmos registros a respeito da codificação de mensagens desde a
antiguidade, principalmente mensagens que eram trocadas durante guerras.
Hoje, como a troca de informações se dá via computadores, é natural que as maneiras de se
criptografar uma mensagem se fundamentem em números. Estudaremos a Matemática necessária
para compreender como funciona o método criptográfico chamado RSA, que tem por parâmetros
iniciais dois números primos p e q, mas vamos iniciar nossa discussão com algo anterior a números
primos: a divisão e algoritmo euclidianos.

1.1 Divisão Euclidiana

TEOREMA 1.1.1. Sejam a e b inteiros positivos. Existem inteiros q e r tais que

a=b·q+r e 0≤r<b (1.1)

Além disso os valores de q e r satisfazendo as relações acima são únicos.

DEMONSTRAÇÃO. Primeiramente vamos demonstrar a existência dos inteiros a e b. Faremos isso

por indução sobre o inteiro a.
Fixe b ∈ Z∗+ . Se a = 1, temos dois casos a considerar.

1
Capı́tulo 1 Algoritmo da Divisão de Euclides e Divisibilidade

1. Se b = 1, basta tomar q = 1 e r = 0.
2. Se b > 1, basta tomar q = 0 e r = 1.
Em ambos os casos as relações (1.1) estão satisfeitas.
Suponha agora, como hipótese de indução, que para a = k, k ≥ 1, existam inteiros q e r
satisfazendo
k =b·q+r e 0≤r<b

Então k + 1 = b · q + (r + 1). Como r < b, temos r + 1 < b + 1 ⇒ r + 1 ≤ b, e novamente temos

dois casos a considerar:
1. Se r + 1 < b, basta tomar q 0 = q e r0 = r + 1 e assim

a = k + 1 = b · q 0 + r0 , com 0 ≤ r0 < b

2. Se r + 1 = b, temos

k + 1 = b · q + b = b · (q + 1) = b · q 0 + r0

onde q 0 = q + 1 e r0 = 0, e desse modo as relações (1.1) estão satisfeitas novamente. Sendo

assim, pelo princı́pio de indução finita, para cada a ∈ Z, a ≥ 1, existem q e r satisfazendo (1.1).
Resta-nos agora demonstrar a unicidade de q e r.
Suponha que existam q1 , q2 , r1 e r2 satisfazendo

a = b · q 1 + r1 e 0 ≤ r1 < b

a = b · q 2 + r2 e 0 ≤ r2 < b

Se subtrairmos as igualdades acima, membro a membro, obteremos

(q2 − q1 ) · b = r1 − r2 ⇒ |q2 − q1 | · b = |r1 − r2 |

Das desigualdades acima temos que 0 ≤ r1 < b e −b < −r2 ≤ 0, e somando essas desigualdades
obtemos
−b < r1 − r2 < b ⇔ 0 ≤ |r1 − r2 | < b

e isso nos leva a 0 ≤ |q2 − q1 | · b < b, e como b 6= 0, podemos escrever 0 ≤ |q2 − q1 | < 1, o que só é
possı́vel se q1 = q2 . Esta última igualdade nos leva imediatamente a concluir também que r1 = r2 .
Portanto, q e r satisfazendo (1.1) são únicos.
Os números q e r, cuja existência foi garantida pelo teorema anterior, são chamados de quociente
e resto da divisão euclidiana de a por b, respectivamente.

DEFINIÇÃO 1.1.2. Um número inteiro b divide outro número inteiro a se existe um terceiro inteiro

2
O Algoritmo de Euclides Seção 1.2

c tal que
a = b · c.

O inteiro b é dito divisor ou fator de a, e a é múltiplo de b. Denotamos o fato de que b divide a

através do sı́mbolo b|a.
Em outras palavras, um inteiro a é divisı́vel por outro inteiro b se o resto da divisão euclidiana
de a por b for zero. Da definição acima já podemos tirar algumas conclusões:
1. O único número que divide 1 é o próprio 1 ou −1, pois se b 6= 1, não podemos encontrar um
inteiro c tal que b · c = 1;

2. O 1 é divisor de qualquer inteiro b, pois b = b · 1;

3. Todo inteiro b é divisor de 0, pois 0 = 0 · b;

4. 0 não é divisor de nenhum outro inteiro, a não ser do próprio zero, pois b 6= b · 0 = 0

1.2 O Algoritmo de Euclides

Iniciemos com a seguinte definição:
DEFINIÇÃO 1.2.1. Dados dois inteiros positivos a e b, chama-se máximo divisor comum de a e
b o inteiro não negativo d satisfazendo:
1. d = 0 se a = b = 0
2. Se a 6= 0 ou b 6= 0, d é caracterizado pelas duas seguintes propriedades:
(i) d|a e d|b
(ii) se x é um inteiro positivo tal que x|a e x|b, então x ≤ d
Denotamos o máximo divisor comum de a e b por d = mdc(a, b). Se a 6= 0 ou b 6= 0, a
maneira mais natural de encontrar o mdc(a, b) é a seguinte: primeiramente determinamos quais
inteiros pertencem ao conjunto D(a) = {x ∈ Z|x divide a}, e quais inteiros pertencem ao conjunto
D(b) = {x ∈ Z|x divide b}; em seguida fazemos a intersecção de tais conjuntos, D(a) ∩ D(b). Note
que, desde que a 6= 0 ou b 6= 0, D(a) e D(b) são finitos, e portanto D(a) ∩ D(b) também é finito, e
portanto possui um maior elemento d. Esse maior elemento é o máximo divisor comum de a e b.
É claro que esse método não é eficiente quando a e b são inteiros grandes, ou se estamos
interessados em determinar mdc(a, b) computacionalmente. O Algoritmo de Euclides nos permite
encontrar d = mdc(a, b) através de divisões sucessivas. Vamos começar demonstrando dois lemas
que nos ajudarão a demonstrar o teorema que justifica o funcionamento do Algoritmo de Euclides.
LEMA Sejam a e b números inteiros positivos. Suponha que existam inteiros g e s tais que
1.2.2.

a = bg + s. Então
mdc(a, b) = mdc(b, s) (1.2)

3
Capı́tulo 1 Algoritmo da Divisão de Euclides e Divisibilidade

DEMONSTRAÇÃO. Sejam d1 = mdc(a, b) e d2 = mdc(b, s).

1. Se d1 = mdc(a, b), então d1 |a e d1 |b, ou seja, existem m e n inteiros tais que a = md1 e
b = nd1 . Temos então
md1 = nd1 · g + s ⇒ (m − ng)d1 = s

ou seja, d2 |a. Desse modo, d2 |a e d2 |b, e portanto d2 ≤ d1 , já que d1 = mdc(a, b).
Sendo assim, se d1 ≤ d2 e d2 ≤ d1 , concluı́mos que d1 = d2 .

LEMA Sejam a e b inteiros positivos com a ≥ b, e definamos uma sequência de inteiros

1.2.3.

não-negativos da seguinte forma:

1. r1 = a;
2. r2 = b;
3. Para cada ı́ndice k, k ≥ 2, se rk 6= 0, então rk+1 é o resto da divisão euclidiana de rk−1 por
rk . Se rk = 0, então a sequência termina em rk .
Então a sequência {rk } é finita e termina em um zero, ou seja, existe um ı́ndice n tal que
r1 ≥ r2 > r3 > · · · > rn > 0 e rn+1 = 0.

DEMONSTRAÇÃO. Por hipótese, r1 ≥ r2 , e pela definição de rk+1 , para k ≥ 2 temos rk+1 < rk .
Seja S o conjunto formado pelos naturais r1 , r2 , · · · . Note que S ⊂ N e S 6= ∅. Pelo princı́pio da
boa ordenação dos Naturais, S possui um menor elemento, que denotaremos por rn+1 . Afirmamos
que rn+1 = 0. De fato, se tivessemos rn+1 6= 0, poderiamos definir um rn+2 , que seria o resto da
divisão de rn por rn+1 , o que nos leva à 0 ≤ rn+2 < rn+1 , o que contradiz o fato de rn+1 ser o
menor elemento de S.
Agora estamos em condições de demonstrar o seguinte

TEOREMA 1.2.4 (Algoritmo de Euclides). Sejam a e b inteiros positivos, com a ≥ b, e seja

r1 , r2 , r3 , · · ·

a sequência definida como no lema anterior. Então rn = mdc(a, d).

DEMONSTRAÇÃO. Cada rk , k ≥ 3, é o resto da divisão de rk−2 por rk−1 . Pelo Lema 1.2.2, temos

mdc(rk , rk−1 ) = mdc(rk−1 , rk−2 ).

4
Algoritmo Euclidiano Estendido Seção 1.3

Portanto

rn = mdc(0, rn ) (rn+1 = 0)
= mdc(rn , rn−1 ) (pelo Lema 1.2.3)
= mdc(rn−1 , rn−2 )
···
= mdc(r3 , r2 )
= mdc(r2 , r1 )
= mdc(a, b)

Assim, para encontrarmos o máximo divisor comum de dois inteiros a e b, iniciamos dividindo
a por b (1) . Essa primeira divisão nos dará um resto r1 . Agora dividimos b por r1 , o que nos
dará um resto r2 . Em seguida, dividimos r1 por r2 , o que nos dará um resto r3 . Continuamos
efetuando essas divisões até encontrarmos um resto nulo. O último resto não-nulo (que tabmém é
o quociente da divisão de resto nulo) é o máximo divisor comum de a e b.
Note que se a é um múltiplo de b, quando dividirmos a por b já encontraremos resto zero.
Logo, o mdc de a e b é o próprio b, que é o quociente da última (e única) divisão do processo.
O Algoritmo Euclidiano nos permite calcular o mdc de dois inteiros a e b, mas isso não é tudo,
ele nos diz mais.

1.3 Algoritmo Euclidiano Estendido

O mdc(a, b) pode ser caracterizado de outra maneira, que nos será útil na critografia RSA.

TEOREMA 1.3.1. O máximo divisor comum de dois inteiros a e b, a 6= 0 ou b 6= 0, é a menor

combinação linear positiva de a e b com coeficientes inteiros. Em outras palavras, mdc(a, b) é o
menor inteiro positivo da forma ma + nb com m e n inteiros.

DEMONSTRAÇÃO. Seja A = {x ∈ Z | x > 0 e x = ma + nb, com m, n ∈ Z}. Temos que

(i) A ⊂ N;
(ii)A 6= ∅, pois existe ao menos uma combinação linear positiva de a e b: como estamos
considerando a e b inteiros não negativos, se a 6= 0 então a + 0 · b pertence ao conjunto A; se b 6= 0
então 0 · a + b pertence ao conjunto A.
1
Podemos supor a ≥ b, mas isso nao é necessário: se tivermos a < b e começarmos o processo dividindo a por b,
nosso primeiro resto será o próprio a, e consequentemente a segunda divisão será de b por a, ou seja, se iniciarmos
o processo de maneira “errada”, tentando dividir um numero menor por outro maior, o próprio algoritmo inverterá
divisor e dividendo na segunda divisão.

5
Capı́tulo 1 Algoritmo da Divisão de Euclides e Divisibilidade

Pelo Princı́pio da Boa Ordenação dos Naturais, o conjunto A possui um elemento mı́nimo
d = ma + nb. Vamos mostrar que esse elemento mı́nimo d é o mdc(a, b).
Pelo algoritmo da divisão, existem inteiros q e r tais que

a=d·q+r e 0≤r<d

Podemos escrever r = a − dq = a − (ma + nb)q = a(1 − mq) − b(nq), logo r é uma combinação
linear de a e b, e 0 ≤ r < d. Como d é a menor combinação linear positiva de a e b, temos que
r = 0, ou seja, d|a.
De modo análogo concluı́mos que d|b. Agora, para que d seja o máximo divisor comum de a e
b, precisamos mostrar que para qualquer inteiro c tal que c|a e c|b temos que c ≤ d. Seja então c
um inteiro divisor de a e de b.
Se c ≤ 0 nada temos a demonstrar por d ∈ A, logo d > 0. Suponha então que c > 0. Como
c|a e c|b, existem inteiros p e q tais que a = pc e b = qc. Se tomarmos uma combinação linar de a
e b, teremos
ma + nb = mpc + nqc = (mp + nq) · c ⇒ c|(ma + nb)

ou seja, se c|a e c|b, então c divide qualquer combinação linear de a e b. Mas d é uma combinação
linear de a e b, logo c|d.
Como d > 0, temos que c ≤ d, logo

d = mdc(a, b)

Tendo demonstrado esta caracterização do mdc(a, b), o seguinte corolário imediato nos será
útil no estudo que se segue.

COROLÁRIO 1.3.2. Sejam a e b inteiros positivos e seja d o máximo divisor comum entre a e b.
Existem inteiros α e β tais que
α·a+β·b=d

Observamos que tais α e β não são únicos, pois se α e β são inteiros que satisfazem o corolário
anterior, então os inteiros α + kb e β − ka também satisfazem, sendo k um inteiro qualquer.

(α + kb) · a + (β − ka) · b = α · a + kab + β · b − kab = α · a + β · b = d

Vale também comentar que a recı́proca deste corolário não é verdadeira, exceto em um caso
particular. Sendo a e b dois inteiros, se existirem outros dois inteiros α e β tais que aα + bβ = c,
não podemos afirmar que c é o máximo divisor comum entre a e b, a não ser que tenhamos c = 1,
pois neste caso temos a menor combinação linear positiva possı́vel.

6
Algoritmo Euclidiano Estendido Seção 1.3

O algoritmo de Euclides pode ser reformulado para que calculemos simultaneamente d, α e β:

o algoritmo euclidiano estendido. Esta extensão do algoritmo de Euclides se baseia em escrever
os restos de cada divisão do algoritmo como combinação linear do divisor e dividendo. Vamos
mostrar como funciona com um exemplo: queremos encontrar o máximo divisor comum de 91 e
35, e escrevê-lo como combinação linear. Efetuando as divisões, encontramos

91 35 35 21 21 14 14 7
21 2 14 1 7 1 0 2
91 = 35 · 2 + 21 35 = 21 · 1 + 14 21 = 14 · 1 + 7 14 = 7 · 2 + 0

O último resto não nulo é 7, logo mdc(91, 35) = 7. Agora, para escrevermos 7 como combinação
linear de 91 e 35, isolamos os restos das primeiras e substinuindo nas subsequentes.

91 = 35 · 2 + 21 ⇒ 21 = 91 − 2 · 35 (1.3)
35 = 21 · 1 + 14 ⇒ 14 = 35 − 21 (1.4)
21 = 14 · 2 + 7 ⇒ 7 = 21 − 2 · 14 (1.5)

Primeiro usamos (1.3) em (1.4)

14 = 35 − 21 = 35 − (91 − 2 · 35) = 3 · 35 − 91 (1.6)

Agora usamos (1.4) e (1.6) na equação (1.5), obtendo

7 = 21 − 2 · 14 = (91 − 2 · 35) − 2 · (3 · 35 − 91) = −8 · 35 + 3 · 91

Assim,
7 = mdc(35, 91) = −8 · 35 + 3 · 91.

Pode parecer que para encontrarmos uma combinação linear de a e b que seja igual a mdc(a, b),
precisamos primeiramente efetuar todas as diviões, para depois utilizarmos os resto e quocientes
obtidos. Isso até pode ser feito, mas dependendo da quantidade de divisões pode ser muito
trabalho, ou impraticável do ponto de vista computacional. Mas há uma outra maneira de im-
plementarmos o algoritmo euclidiano estendido, inventada por D.E. Knuth. A implementação se
baseia em guardar cada um dos restos obtidos na sequência das divisões em termos de a e b sem
esperar chegar ao último resto. Dessa forma, precisamos armazenar apenas os dados referentes às
duas divisões imediatamente anteriores.
Se fizermos as divisões sucessivas até encontrarmos um resto nulo, teremos a seguinte sequência

7
Capı́tulo 1 Algoritmo da Divisão de Euclides e Divisibilidade

de divisões.

a = bq1 + r1 e 0 ≤ r1 < b
b = r1 q2 + r2 e 0 ≤ r2 < r1
r1 = r2 q3 + r3 e 0 ≤ r3 < r2
r2 = r3 q4 + r4 e 0 ≤ r4 < r3
.. ..
. .
rn−3 = rn−2 qn−1 + rn−1 e 0 ≤ rn−1 < rn−2
rn−2 = rn−1 qn e rn = 0

Neste momento as desigualdades não nos interessam. Reescrevemos as divisões da seguinte

maneira.

a = bq1 + r1 e r1 = ax1 + by1

b = r1 q2 + r2 e r2 = ax2 + by2
r1 = r2 q3 + r3 e r3 = ax3 + by3
r2 = r3 q4 + r4 e r4 = ax4 + by4 (1.7)
.. ..
. .
rn−3 = rn−2 qn−1 + rn−1 e rn−1 = axn−1 + byn−1
rn−2 = rn−1 qn e rn = 0

onde os números x1 , ..., xn−1 e y1 , ..., yn−1 são inteiros a determinar. Podemos resumir as infor-
mações de (1.7) em uma tabela.

restos quocientes x y
a * x−1 y−1
b * x0 y0
r1 q1 x1 y1
r2 q2 x2 y2
r3 q3 x3 y3
.. .. .. ..
. . . .
rn−2 qn−2 xn−2 yn−2
rn−1 qn−1 xn−1 yn−1

Note que acrescentamos duas linhas que não correspondem a nenhuma divisão; de fato, a e
b não são restos. Chamaremos essas duas primeiras linhas de −1 e 0. Logo veremos porque são

8
Algoritmo Euclidiano Estendido Seção 1.3

necessárias. Note que rn−1 = axn−1 + byn−1 . Mas rn−1 = mdc(a, b), portanto xn−1 e yn−1 são os
inteiros α e β que procuramos para escrever mdc(a, b) = αa + βb. Portanto, precisamos apenas
saber como preencher as colunas x e y.
Suponha que já tenhamos preenchido a tabela até certo ponto, por exemplo, até a
(j − 1)-ésima linha. Precisamos descobrir quais são os inteiros rj , qj , xj e yj . Para determinarmos
rj e qj , basta dividirmos rj−2 por rj−1 . Desse modo, teremos rj−2 = rj−1 qj + rj e 0 ≤ rj < rj−1 .
Estão determinados, então, rj e qj .
Para encontrarmos xj e yj , primeiro observe que

rj = rj−2 − rj−1 qj (1.8)

Mas as linhas j − 1 e j − 2 da tabela nos dizem que

rj−2 = axj−2 + byj−2 e rj−1 = axj−1 + byj−1

Substituindo esses valores em (1.8), obtemos

rj = (axj−2 + byj−2 ) − (axj−1 + byj−1 )qj

= a(xj−2 − qj xj−1 ) + b(yj−2 − qj yj−1 )

Veja que para calcularmos xj e yj , usamos apenas valores contidos nas duas linhas imediata-
mente anteriores à linha j, além do queociente qj . Portanto, sabemos preencher qualquer linha
da tabela se conhecermos as duas linhas anteriores. E mais, nosso processo de preenchimento é
recursivo, logo, só precisamos saber como iniciá-lo. É nesse ponto que as duas primeiras linhas
nos ajudam.
Interpretando estas linhas como as demais, devemos ter:

a = ax−1 + by−1 e b = ax0 + by0

e isto sugere escolhermos

x−1 = 1 , y−1 = 0 , x0 = 0 e y0 = 1

e com esses valores podemos iniciar o processo recursivo de preenchimento da tabela. Ao final do
processo, teremos encontrado d = mdc(a, b).

d = rn−1 = aα + bβ

onde α = xn−1 e β = yn−1 .

Para encerrar este primeiro capı́tulo, vamos ver como o estudo sobre o mdc desenvolvido até

9
Capı́tulo 1 Algoritmo da Divisão de Euclides e Divisibilidade

aqui nos auxilia na resolução de equações diofantinas lineares. Uma equação diofantina linear à n
incógnitas é uma sentença do tipo

a1 x 1 + a2 x 2 + · · · + an x n = b (1.9)

onde a1 , ..., an , b são números inteiros. Em se tratando de equações diofantinas, lineares ou não,
sempre estamos procurando soluções inteiras, ou seja, as incógnitas x1 , ..., xn só assumem valores
no conjunto Z. Vamos tratar apenas de equações diofantinas lineares à 2 incógnitas, pois qualquer
equação com mais incógnitas pode ser reduzida a este caso. A tı́tulo de exemplo, considere a
equação diofantina linear à 3 incógnitas

x + 10y + 25z = 99.

Fazemos 10y + 25z = 5k (escolhemos 5 porque 5 = mdc(10, 25)). Daı́, a equação original se reduz
à x + 5k = 99. Portanto, ao invés de resolvermos uma equação à 3 incógnitas, resolveremos 2
equações a 2 incógnitas. Para mais detalhes ver [10].
Primeiramente, vamos ver qual uma condição necessária e suficiente para que a equação
ax + by = c admita solução inteira.

PROPOSIÇÃO 1.3.3. A equação ax + by = c admite solução inteira se, e somente se, mdc(a, b)
dividir c.

DEMONSTRAÇÃO. (⇒) Seja (x0 , y0 ) uma solução inteira da equação ax + by = c, ou seja

ax0 + by0 = c.

Seja d = mdc(a, b). Como d|a e d|b, temos que d divide qualquer conbinação linear de a e b. Em
particular, d divide ax0 + by0 , ou seja, d|c.
(⇐) Sendo d = mdc(a, c), temos que d é a menor combinação linear positiva de a e b.

d = ax0 + by0 (1.10)

Temos por hipótese que d|c, isto é, existe um inteiro c0 tal que c = dc0 . Multiplicando a equação
(1.10) por c0 temos
c = dc0 = a(x0 c0 ) + b(yo c0 )

portanto (x0 c0 , y0 c0 ) é uma solução da equação ax + by = c.

Agora que sabemos como verificar se uma equação diofantina linear admite solução, vejamos
como encontrar tal solução. Considere a equação diofantina linear ax + by = c. Suponha que tal
equação admita solução, isto é, d = mdc(a, b)|c. Neste caso temos c = dc0 , para algum inteiro c0 .

10
Algoritmo Euclidiano Estendido Seção 1.3

a b
Seja a0 = e b0 = . Note que a0 e b0 são inteiros pois d|a e d|b. Considere, agora, a equação
d d
reduzida a0 x + b0 y = c0 .
Afirmamos qualquer solução da equação original é também solução da equação reduzida, e
vice-versa. De fato, se (x0 , y0 ) é uma solução da equação reduzida, temos

c0 = a0 x0 + b0 y0 ⇔ c0 d = a0 dx0 + b0 dy0 ⇔ c = ax0 + by0

Portanto, para achar as soluções da equação original, basta encontrarmos as soluções da

equação reduzida. Sendo d = mdc(a, b), temos que existen inteiros r e s tais que d = ar + bs.
Dividindo toda a equação por d, obtemos

a b
1 = r + s.
d d

a b
Mas = a0 e = b0 , ou seja, a0 e b0 são primos entre sı́, portanto existem inteiros α e β, que
d d
podem ser determinados usando-se o algoritmo euclidiano estendido, tais que

a0 α + b 0 β = 1

Agora, basta multiplicarmos esta equação por c0 , e chegaremos à

a0 c 0 α + b 0 c 0 β = c 0

ou seja, (c0 α, c0 β) é uma solução da equação reduzida, e portanto, é uma solução da equação
original
ax + by = c.

Como os inteiros α e β não são únicos, segue que a solução da equação diofantina linear também
não é única. De fato, se (x0 , y0 ) é uma solução particular de ax + by = c, então (x0 + bt, y0 − at)
também é uma solução, t ∈ Z, pois

a(x0 + bt) + b(y0 − at) = ax0 + abt + by0 − abt = ax0 + by0 = c

Com isso, também concluı́mos que quando ax + by = c admite soluções, estas são em quantidade
infinita, pois cada t inteiro gera uma solução diferente.
Vamos encerrar com um exemplo. Vamos resolver 4x + 6y = 10.
Como mdc(4, 6) = 2 divide 10, a equação admite solução. Primeiramente, encontremos a
equação reduzida, dividindo a original por 2.

2x + 3y = 5

11
Capı́tulo 1 Algoritmo da Divisão de Euclides e Divisibilidade

Agora, encontramos uma solução particular desta equação. Utilizando o algoritmo euclidiano
estendido, obtemos
2 · (−1) + 3 · (1) = 1

Multiplicando esta última por 5, a equação fica

2 · (−5) + 3 · (5) = 5

logo, (−5, 5) é uma solução particular da equação reduzida e também da equação original. Daı́,
as soluções de 4x + 6y = 10 são dadas por
(
x = −5 + 6t
(t ∈ Z)
y = 5 − 4t

Terminamos este primeiro capı́tulo com mais algumas propriedades relacionadas à divisibilidade
e ao mdc.

PROPOSIÇÃO 1.3.4. Se n, a, b são inteiros positivos, então mdc(na, nb) = n · mdc(a, b).

DEMONSTRAÇÃO. Seja d = mdc(a, b). Então d|a e d|b, ou seja, a = rd e b = sd, para certos inteiro
r e s. Multiplicando as últimas igualdades por n, obtemos na = r(nd) e nb = s(nd), ou seja nd|na
e nd|nb. Assim temos que nd é um divisor comum de na e nb. Resta mostrar que nd é o maior
deles.
Seja x ∈ Z+ tal que x|na e x|nb. Como d = mdc(a, b) existem inteiros α e β de modo que
d = aα + bβ, o que implica naα + nbβ = nd. Como x|na e x|nb, x divide qualquer combinação
linear de na e nb. Em particular, x|(naα + nbβ) = nd, portanto x ≤ nd. Assim temos que
nd = mdc(na, nb) ∴ mdc(na, nb) = n · mdc(a, b)

PROPOSIÇÃO 1.3.5. O mdc é associativo, isto é, dados três inteiros a, b, c, temos que

mdc(a, mdc(b, c)) = mdc(mdc(a, b), c) = mdc(a, b, c)

DEMONSTRAÇÃO. Seja Da o conjunto dos divisores de a, Db o conjunto dos divisores de b e Dc

o conjunto dos divisores de c. Sejam d1 = mdc(a, mdc(b, c)), d2 = mdc(mdc(a, b), c) e d3 =
mdc(a, b, c). De outra maneira:

• d1 = max(Da ∩ (Db ∩ Dc ))

• d2 = max((Da ∩ Db ) ∩ Dc )

• d3 = max(Da ∩ Db ∩ Dc )

12
Algoritmo Euclidiano Estendido Seção 1.3

Como a operação de interseção de conjuntos é associativa, temos

Da ∩ (Db ∩ Dc ) = (Da ∩ Db ) ∩ Dc = Da ∩ Db ∩ Dc

e portanto d1 = d2 = d3 .

PROPOSIÇÃO 1.3.6. Sejam b1 e b2 inteiros primos entre sı́, isto é, mdc(b1 , b2 ) = 1. Então d é
um divisor de b1 b2 se, e somente se, d = d1 d2 , onde d1 = mdc(d, b1 ) e d2 = mdc(d, b2 ).

DEMONSTRAÇÃO. (⇐) Se d1 = mdc(d, b1 ), então d1 |b1 ⇔ b1 = m · d1 para algum m ∈ Z. De

modo análogo, se d2 = mdc(d, b2 ), então d2 |b2 ⇔ b2 = n · d2 para algum n ∈ Z. Multiplicando as
equações, obtemos

b1 b2 = m · d1 · n · d2 = (mn) · (d1 d2 ) = mn · d ⇒ d|b1 b2

(⇒) Para demonstrarmos que se d|b1 b2 , então d = mdc(d, b1 ) mdc(d, b2 ), faremos uso das
duas proposições anteriores. Sendo d1 = mdc(d, b1 ), d2 = mdc(d, b2 ), d um divisor de b1 b2 e
mdc(b1 , b2 ) = 1, temos

P rop.1.3.4
d1 d2 = d1 · mdc(d, b2 ) = mdc(d · d1 , b2 · d1 )
= mdc(d · d1 , b2 · mdc(d, b1 ))
P rop.1.3.4
= mdc(d · d1 , mdc(db2 , b1 b2 ))
d|b1 b2
= mdc(d · d1 , mdc(db2 , dm)) para algum m ∈ Z.
P rop.1.3.4
= mdc(d · d1 , d · mdc(b2 , m))
P rop.1.3.4
= d · mdc(d1 , mdc(b2 , m))
= d · mdc(mdc(d, b1 ), mdc(b2 , m))
P rop.1.3.5
= d · mdc(d, b1 , b2 , m)
P rop.1.3.5
= d · mdc(d, m, mdc(b1 , b2 ))
= d · mdc(d, m, 1) = d · 1
= d

como querı́amos mostrar.

13
Capı́tulo 1 Algoritmo da Divisão de Euclides e Divisibilidade

14
Capı́tulo

2
Fatoração Única

Por que os números primos se chamam números primos? Com certeza não é por que seus
pais são irmãos. Na verdade, os gregos dividiam os números em primeiros (ou indecomponı́veis)
e secundários (ou compostos). Os números compostos são assim chamados por serem formados
a partir dos primeiros. Os romanos traduziram literalmente a palavra grega para primeiro, que
em latim é primus. Daı́ a origem dos nossos números primos. Neste capı́tulo vamos ver como os
números primos funcionam como partı́cula elementar na construção de qualquer inteiro.

2.1 Teorema Fundamental da Aritmética

DEFINIÇÃO 2.1.1. Um número inteiro p 6= ±1 é primo se seus únicos divisores são ±p e ±1. Se
p 6= ±1 não é primo, ele é dito composto.

Uma primeira pergunta que nos vem quando nos deparamos com essa definição é: por que 1
e −1 não são classificados nem como primos nem como compostos? Antes de respondermos tal
pergunta, vejamos o enunciado do Teorema Fundamental da Aritmética.

TEOREMA 2.1.2 (Teorema Fundamental da Aritmética). Todo inteiro positivo n ≥ 2 pode ser
escrito na forma
n = p1 · p2 · ... · pk

para certos primos p1 , p2 , ..., pk com k ≥ 1 e p1 ≤ p2 ≤ ... ≤ pk . Além disso, os fatores primos
satisfazendo essas condições são únicos, isto é, se q1 , q2 , ..., qj são também primos positivos com
q1 ≤ q2 ≤ ... ≤ pj e n = q1 · q2 · ... · qj , então j = k e p1 = q1 , p2 = q2 , ..., pk = qk .

A exclusão de ±1 na definição de número primo é necessária para garantir a unicidade da

fatoração no teorema anterior, pois caso 1 ou −1 fossem primos, por exemplo, 2, 13 · 2 e (−1)4 · 2
seriam fatorações distintas do número 2.
Vamos demonstrar primeiramente a existência da fatoração.
Existência. Vamos usar o segundo principio da indução. Primeiramente, se n = 2, então n
é primo, pois os únicos divisores de 2 são ±1 e ±2.

15
Capı́tulo 2 Fatoração Única

Agora, seja k ≥ 2 e suponha como hipótese de indução que todo inteiro n, 2 ≤ n ≤ k, seja
primo ou possa ser escrito como produto de fatores primos. vamos mostrar que k + 1 é primo ou
se escreve como produto de primos.
Considere, então, o inteiro k + 1.
i) se k + 1 é primo, nada mais temos a demonstrar.
ii) se k + 1 não é primo, então possui um fator (divisor) a, diferente de ±1 e de ±(k + 1), ou
seja,
k+1=a·b

e além disso temos 2 ≤ a, b < k + 1 ⇒ 2 ≤ a, b ≤ k, e portanto, pela hipótese de indução, a e b

ou são primos ou se decompõe como produto de primos. Portanto, como k + 1 = a · b, k + 1 se
decompõe como um produto de fatores primos positivos.
Antes de demonstrarmos a unicidade da fatoração, vamos demonstrar algumas proposições
envolvendo números primos e divisibilidade que serão úteis.

PROPOSIÇÃO 2.1.3. Dados inteiros a, b e c, se a e b são primos entre sı́, então

(1) se a divide o produto bc então a divide c.
(2) se a e b dividem c, então o produto ab divide c.

DEMONSTRAÇÃO. (1) Se a e b são primos entre sı́, existem inteiros r e s tais que

ra + sb = 1

logo
rac + sbc = c.

Como, por hipótese, a|bc então a|sbc também. É claro que a|rac. Mas se a divide dois inteiros,
ele também divide qualquer conbinação linear desses dois inteiros. Portanto a|(rac + scb), ou seja

a|c.

(2) Se a divide c, existe um inteiro r tal que c = ar. Mas b também divide c. Como a e b são
primos entre sı́, segue da primeira parte deste lema que b divide r, ou seja, existe um inteiro s tal
que r = bs. Portanto
c = ar = a(bs) = (ab)s

ou seja, ab divide c.

PROPOSIÇÃO 2.1.4. Sejam a e p inteiros, sendo p um números primo positivo. Então, a não é
divisı́vel por p se, e somente se, a e p forem primos entre sı́.

DEMONSTRAÇÃO. (⇒) Por hipótese, p 6 |a. Seja d = mdc(a, p).

16
Teorema Fundamental da Aritmética Seção 2.1

Como d|p, temos que d = 1 ou d = p.

Mas p 6 |a e d|a, portanto p 6= d. Logo d = 1 e então a e p são primos entre sı́.
(⇐) Suponhamos agora que a e p são primos entre sı́, ou seja, mdc(a, p) = 1. Como p|p,
se também tivermos que p|a, então p seria um divisor comum de a e p, logo necessariamente
deveriamos ter p ≤ mdc(a, p) = 1. Mas p é primo, ou seja, p ≥ 2, e temos assim uma contradição.
Portanto obrigatoriamente p 6 |a.

PROPOSIÇÃO 2.1.5. Sejam a, b e p inteiros, com p primo. Se p|ab, então p|a ou p|b (nada impede
que p divida tanto a quanto b).

PROPOSIÇÃO 2.1.6. Seja p um número primo e a1 , ..., an números inteiros, com n ≥ 2. Se

p|(a1 · a2 · ... · an ) então p|ai para algum ı́ndice i, i ∈ {1, 2, ..., n}.

DEMONSTRAÇÃO. Faremos uma indução sobre n. Para n = 2 já está feito na Proposição 2.1.5.
Hipótese de indução: Se p é primo e p divide um produto de k fatores inteiros, então p divide
ao menos um dos fatores.
Considere agora um produto de k + 1 inteiros e suponha que p|a1 · ... · ak · ak+1 . O número
s = a1 · ... · ak é um inteiro, e temos que p|s · ak+1 . Pela Proposição 2.1.5, p|s ou p|ak+1 . Logo p|aj
para algum j ∈ {1, 2, ..., k} ou p|ak+1 . Portanto p|aj para algum j ∈ {1, 2, ..., k, k + 1}.
Pelo primeiro princı́pio de indução finita, a proposição está demonstrada.
Agora vamos demonstrar a unicidade da fatoração do Teorema Fundamental da Aritmética.
Unicidade Suponha que exista um inteiro n, n ≥ 2, que possa ser escrito como produto de
fatores primos de duas maneiras distintas, isto é

n = p1 · p2 · ... · pr = q1 · q2 · ... · qs (2.1)

sendo p1 , p2 , ..., pr , q1 , q2 , ..., qs primos positivos e p1 ≤ p2 ≤ ... ≤ pr e q1 ≤ q2 ≤ ... ≤ qs .

Cancelando os fatores primos que aparecem em ambos os lados da igualdade 2.1, como as duas
fatorações são supostamentes distintas, chegaremos a uma igualdade

pi1 · pi2 · ... · piu = qj1 · qj2 · ... · qjv (2.2)

com u ≥ 1 e v ≥ 1, em que cada um dos primos do lado esquerdo é diferente de cada um dos
primos do lado direito, ou seja, os membros à esquerda e à direita não tem mais fatores primos

17
Capı́tulo 2 Fatoração Única

em comum. Agora observe que

pi1 · (pi2 · pi3 ... · piu ) = qj1 · qj2 · ... · qjv

o que significa que pi1 divide qj1 · qj2 · ... · qjv . Pela Proposição 2.1.6, pi1 divide algum dos fatores
qj1 , qj2 , ..., qjv , o que é impossı́vel, pois esses fatores são primos e diferentes de pi1 .
Portanto não podemos ter duas fatorações distintas para um mesmo inteiro n, logo está provada
a unicidade da fatoração em números primos.
Agora que sabemos que todo inteiro pode ser escrito como um produto de inteiros, veremos
algumas maneiras de encontrarmos fatores de um inteiro n dado.

2.2 Algoritmos de Fatoração

A maneira mais imediata para determinarmos um fator do inteiro n é verificar se algum inteiro k,
2 ≤ k ≤ n − 1, divide n. Se algum destes k dividir n, encontramos um fator de n; e mais, o menor
fator que encontrarmos dessa maneira deve ser primo: seja f um inteiro tal que 2 ≤ f ≤ n − 1.
Suponha que f seja o menor fator de n e que f 0 > 1 seja um fator de f . Pela definição de
divisibilidade
n=f ·a e f = f0 · b

para certos inteiros a e b. Assim temos

n = f 0 · (ab).

Então f 0 também é fator de n. Como supusemos que f era o menor fator de n, temos que f ≤ f 0 .
Mas f 0 é fator de f , logo f 0 ≤ f , e portanto f = f 0 . Concluimos que o único fator de f , maior
que 1, é o próprio f , ou seja, f é primo.
Com um pouco mais de atenção veremos que não precisamos procurar fatores até n − 1. De
√
fato, não precisamos procurar fatores maiores que n.

PROPOSIÇÃO 2.2.1. Se n é um inteiro positivo composto, então n tem um fator primo p satis-
√
fazendo 2 ≤ p ≤ n.

DEMONSTRAÇÃO. Sendo n composto, temos n ≥ 2, e pelo Teorema Fundamental da Aritmética

n = p1 · ... · ps

para certos fatores primos p1 ≤ ... ≤ ps , com s ≥ 2 (se s = 1 então n é primo). Afirmamos que

18
Algoritmos de Fatoração Seção 2.2

√ √
AFIRMAÇÃO: p1 ≤ n. De fato, se tivermos p1 > n, então
√ √
n = p1 · p2 · ... · ps ≥ p1 · p1 · ... · ps ≥ p1 · p1 > n· n=n

o que é uma contradição.

Na verdade, com raciocı́nio similar, podemos concluir que se n ≥ 2 é um inteiro composto, n
√
não pode ter dois fatores primos maiores que n, isto é, todos os fatores primos de n, com possı́vel
√
excessão de apenas um, são menores do que n.
Uma pergunta que nos vem a mente neste ponto é: quais números possuem um fator primo
maior que sua raiz quadrada? É claro que todo número primo é maior que sua raiz quadrada,
logo nossa busca será por números composto que possuam um fator maior que sua raiz quadrada.
Alguns exemplos:
√
• 6=2·3⇒3> 6
√
• 15 = 3 · 5 ⇒ 5 > 15
√
• 30 = 2 · 3 · 5 ⇒ nenhum fator primo maior que 30
√
• 180 = 22 · 32 · 5 ⇒ nenhum fator primo maior que 180

A impressão que temos é que quando n cresce, fica mais difı́cil ele possuir um fator primo
√
> n. Será que é possı́vel encontrarmos um n0 , de modo que, se n > n0 e n é composto, então n
√
não possui fator primo p > n ? O seguinte lema nos garante que não.
√
LEMA Seja n = m · p, m ≥ 2 e p primo. Então p é um fator primo de n maior que
2.2.2. n se,
e somente se, p > m.

DEMONSTRAÇÃO. O inteiro p já é primo e fator de n. Basta verificarmos que a equivalência

√
p> n ⇔ p > m é verdadeira. Como n = mp temos

√
p> mp ⇔ p2 > mp ⇔ p > m

Esse lema nos permite construir inteiros tão grande quanto se queira de forma que tal inteiro
possua um fator primo maior que sua raiz quadrada, pois dado m ∈ Z+ , sempre conseguimos
um primo p > m (já que existem infinitos primos, como veremos no próximo capı́tulo), logo para
√
qualquer inteiro N , existe n > N de modo que n possua um fator primo p > n. Em outras
palavras, o conjunto
√
X = {x ∈ Z+ |x possui um fator primo p > x}

19
Capı́tulo 2 Fatoração Única

é infinito.
Uma pergunta que imediatamente pode ser feita é: o conjunto
√
A = {x ∈ Z+ | todos os fatores primos de x são menores que x}

é finito ou infinito?
Se procurarmos exemplos, notaremos que se escolhermos aleatoriamente inteiros grandes, é
muito mais “fácil” escolhermos um inteiro que pertença ao conjunto A do que ao conjunto X,
mas isso não nos garante que A seja infinito (lembre-se de alguns fatos intrigantes com respeito a
cardinalidade, como Q vs. (R − Q), números algébricos vs. números transcendentes). Antes de
provarmos que A é mesmo infinito, vejamos uma maneira equivalente de enunciar o lema acima.

LEMA 2.2.3. Seja n = m · p, m ≥ 2 e p primo. Então p é um fator primo de n menor ou igual que
√
n se, e somente se, p ≤ m.
√
AFIRMAÇÃO: O conjunto A = {x ∈ Z+ | todos os fatores primos de x são menores que x} é
infinito.

Demonstração. Suponhamos, como hipótese de absurdo, que A seja finito. Então podemos escre-
ver A = {x1 , x2 , x3 , ..., xn } com x1 < x2 < x3 < ... < xn . Como A ⊂ Z e A é finito, A possui um
maior elemento, que no caso é xn .
√
Note que os elementos de A são todos compostos, pois se x é primo temos x > x. Em
particular, xn é composto.
xn = p1 · p2 · ... · ps

onde p1 , p2 , ..., ps são primos e 1 < p1 ≤ p2 ≤ ... ≤ ps .

Para dizermos que um inteiro x pertence a A, temos que verificar para cada fator primo p de
x x
x que p ≤ (no caso, é o inteiro m que aparece no lema). Entretanto, basta fazermos tal
p p
verificação somente para o maior inteiro fator primo de x: se x = p1 · ... · pk , 1 < p1 ≤ ... ≤ pk e
pj é um fator de x menor do que pk , temos

1 < p1
1 < p2
..
.
1 < pj−1
1 < pj+1
..
.
1 < pk−1
pj < p k

20
Algoritmos de Fatoração Seção 2.2

x
Multiplicando essas desigualdades membro a membro, concluı́mos que pj < , ou seja, o lema se
pj
verifica para qualquer fator pj < pk , sendo pk o maior fator primo de x.
Outra observação: xn possui todos os primos menores que ps como fatores. De fato: se p é um
primo menor do que ps que não é fator de xn , construı́mos o inteiro x = xn · p. Tal x é maior que
xn , e o maior fator primo de x é ps . Sendo assim, x ∈ A, pois

xn xn x
ps < < ·p=
ps ps ps

e isso contradiz o fato de xn ser o maior elemento de A. Portanto xn tem como fatores todos os
primos p ≤ ps .
Finalmente, construı́mos agora o inteiro y = xn · ps
Notoriamente temos y > xn . Se y ∈ A, teremos uma contradição e concluiremos que A não
pode ser finito.
Ora, o maior fator primo de y é ps , sendo assim

xn xn y
ps < < · ps = ⇒y∈A
ps ps ps

o que novamente contradiz o fato de xn ser o máximo de A, e portanto, A é infinito.

Note que A, X e {1} constituem uma partição dos inteiros positivos.

O algoritmo justificado pela Proposição 2.2.1 é eficiente quando o inteiro n que vamos fatorar é
divisı́vel por um primo pequeno (o tamanho deste primo depende do computador que usaremos).
Vamos ver agora um outro algoritmo que é eficiente quando n possui um fator primo próximo
√
à n. Tal algoritmo foi inventado por Fermat, e leva seu nome.
Vamos supor n ı́mpar (se n for par, 2 é um de seus fatores).
Queremos encontrar inteiros x e y tais que

n = x2 − y 2 = (x + y)(x − y)

Dessa forma x + y e x − y são fatores de n.

Algoritmo 2.2.4 (Algoritmo de Fermat).

Entrada Um inteiro positivo ı́mpar n.

Saı́da Um fator de n ou uma mensagem dizendo que n é primo.
√
Etapa 1 Faça x = [[ n ]]; se n = x2 , x é fator de n.
√
Etapa 2 Caso contrário, incremente x de uma unidade e calcule y = x2 − n.
n+1
Etapa 3 Repita a Etapa 2 até encontrar um valor inteiro para y ou até que x seja igual a .
2
No primeiro caso n tem fatores x + y e x − y, e no segundo caso n é primo.

21
Capı́tulo 2 Fatoração Única

Antes de demonstrarmos porque o algoritmo funciona, vejamos um exemplo.

n+1 √
Seja n = 731021. Neste caso, = 365511 e n ≈ 854, 997. Sendo assim, iniciamos com
2
x = 854 ⇒ x2 = 729316 < 731021 = n.
√
Agora incrementamos x de um em um, até que x2 − n seja inteiro ou até que x = 365511.
Para nossa “sorte”, quanto fazemos o primeiro incremento em x encontramos
√ √
x = 855 ⇒ y = 8552 − 731021 = 731025 − 731021 = 2

e temos y inteiro. Portanto, dois fatores de 731021 são x + y = 857 e x − y = 853. Por acaso, 853
e 857 são primos.
731021 = 853 × 857

Diferente do primeiro algoritmo, que se resumia a verificar se números eram fatores de n

simplesmente através da divisão, não é claro porque o Algoritmo de Fermat funciona nem porque
ele pára. Vamos ver o teorema que nos dará tais respostas.

√
TEOREMA 2.2.5. Seja n um inteiro ı́mpar, n > 2. Existe um inteiro x ≥ n tal que
√
y = x2 − n é um inteiro e x + y e x − y são fatores de n. Além disso, n é composto se, e
n+1
somente se, x < .
2

DEMONSTRAÇÃO. Suponha que n possa ser fatorado na forma n = ab, com a ≤ b. Queremos
encontrar x e y tais que n = x2 − y 2 , ou seja,

n = ab = (x + y)(x − y)

Como x − y ≤ x + y, basta tomarmos

a+b b−a
x= ey=
2 2

De fato 2 2
a+b b−a
− = ab = n
2 2

Por hipótese, n é ı́mpar, logo a e b são ı́mpares, e portanto x e y tomados como acima são
inteiros.
Se n for primo, só podemos ter a = 1 e b = n, e assim está demonstrado a existência do inteiro
n+1
x. Vamos supor, então, que n seja composto. Precisamos apenas garantir que x < .
2
Nestas condições, temos dois casos a considerar. Primeiro, se n for um quadrado perfeito.

22
Algoritmos de Fatoração Seção 2.2

√ n+1
Neste caso, escolhemos x = n. Desse modo, temos x < , pois
2

n > 2 ⇒ (n − 1)2 > 0

⇒ n2 − 2n + 1 > 0
⇒ n2 + 2n + 1 > 4n
(n + 1)2
⇒ >n>0
4
n+1 √
⇒ > n=x
2

Agora, se n é composto e não é um quadrado perfeito, ou seja, n = ab com 1 < a < b < n,
a+b
escolhemos x = . Por hipótese, temos b > 1 e a > 1 ⇔ a − 1 > 0, portanto
2

1 < b ⇔ a − 1 < b(a − 1)

⇔ a − 1 < ab − b
⇔ a − 1 + (b + 1) < ab − b + (b + 1)
⇔ a + b < ab + 1 = n + 1
a+b n+1
⇔ <
2 2
n+1
⇔ x<
2

e assim está demonstrado o teorema.

Já demonstramos uma propriedade fundamental dos números primos: a Proposição 2.1.5.
Propriedade Fundamental dos Primos: Seja p um número primo e a e b inteiros positivos.
Se p divide o produto ab, então p divide a ou p divide b.
Vamos encerrar este capı́tulo fazendo uso dessa propriedade para mostrar um resultado inte-
ressante.

√
PROPOSIÇÃO 2.2.6. Se p é um inteiro primo, então p é irracional.

√
DEMONSTRAÇÃO. Suponha que p seja racional, isto é, existem inteiros a e b, b 6= 0, tais que

√ a
p= .
b
a
Podemos supor, ainda, que a fraçãoestá reduzida, ou seja, mdc(a, b) = 1 (se não estiver basta
b
√ a
cancelarmos o máximo divisor comum entre o numerador e o denominador). Se p = , temos
b
a2
que p = 2 , ou ainda
b
b 2 · p = a2 (2.3)

23
Capı́tulo 2 Fatoração Única

Isto significa que p divide a2 . Mas se p|a2 , então p|a, ou seja, existe um inteiro c tal que a = p · c.
Substituindo na equação (2.3), obtemos

b 2 · p = a2 = p 2 · c 2 ⇒ b 2 = p · c 2

Disto concluı́mos que p divide b2 , e portanto p divide b. Mas então p|a e p|b, com p ≥ 2 primo,
√ √
e isto é impossı́vel, pois mdc(a, b) = 1. Portanto p não pode ser racional, logo p é irracional.

24
Capı́tulo

3
Números Primos

Estamos estudando a teoria necessária para compreender o método de criptografia RSA. Tal
método faz uso de números primos grandes. Desse modo, é interessante conseguirmos gerar tais
primos. Mas o interesse em encontrar números primos não nasceu devido à criptografia. Os
números primos são conhecidos desde a antiguidade, e desde então eles encantam os matemáticos.
Estes sempre os estudaram buscando descobrir suas propriedades, e uma das coisas que sempre se
buscou foi uma fórmula que gerasse números primos.

3.1 Fórmulas Polinomiais

Sem dúvida, as funções polinomiais são as funções mais simples para se entender e manipular, prin-
cipalmente se o interessado no estudo não está familiarizado com uma Matemática mais robusta.
As primeiras funções estudadas no ensino médio, por exemplo, são as funções afim e quadrática,
isto é, funções de 1◦ e 2◦ graus, respectivamente.
A simplicidade das funções polinomiais pode ser explicada pelo seguinte fato: uma função
polinomial nada mais é do que um “amontoado” de multiplicações e adições.
Se estamos interessados em uma fórmula que gere números primos, é claro que iniciarı́amos
nossa busca nas funções polinomiais, isto é, queremos um polinômio

p(x) = an xn + an−1 xn−1 + · · · + a1 x + a0

onde cada coeficiente ai é um inteiro, e que satisfaz

p(m) é primo para todo inteiro positivo m

Achar um polinômio que satisfaça tais condições parace ser pedante, mas alguns casos partic-
ulares podem, inicialmente, incentivar tal busca. Por exemplo, o polinômio p(x) = x2 + x + 41
quando avaliado nos inteiros de 1 a 39, só atinge valores primos. Entretanto, não é possı́vel en-
contrarmos um polinômio p(x) de modo que a imagem seja um número primo para todo inteiro
x.

25
Capı́tulo 3 Números Primos

TEOREMA 3.1.1. Dado um polinômio f (x) com coeficientes inteiros, existe uma infinidade de
inteiros m tais que f (m) é composto.

DEMONSTRAÇÃO. Seja f (x) um polinômio de grau n.

n
X
n n−1
f (x) = an x + an−1 x + · · · + a1 x + a0 = ai x i
i=0

com f (m) = p primo positivo, m inteiro positivo. Vamos supor, sem perda de generalidade, que
an > 0. Seja h um inteiro positivo. Temos
n
X
f (m + hp) = ai (m + hp)i
i=0
n i
!
X X i i−j j
= ai · m · (hp)
i=0 j=0
j
n i
!
X X i
= ai m i + ai · mi−j hj pj
i=0 j=1
j
n n i
!
X
i
X X i i−j j j−1
= ai m + ai p m hp
i=0 i=0 j=1
j
n i
!
X X i
= f (m) + p · ai mi−j hj pj−1
i=0 j=1
j
n i
!!
X X i
i−j j j−1
= p· 1+ ai m hp
i=0 j=1
j

Para que f (m + hp) seja composto, precisamos garantir que

n i
!
X X i
1+ ai mi−j hj pj−1 6= 1
i=0 j=1
j

Para tanto, é suficiente termos

n i
!
X X i
ai mi−j hj pj−1 >0
i=0 j=1
j

Mas o que temos no lado esquerdo da desigualdade acima é um polinômio g(h) em h, visto que
a0 , a1 , ..., an , m, p são valores fixados. Além disso, o grau deste polinômio é n e seu coeficiente lı́der
é an pn−1 > 0. Sendo assim, temos que

lim g(h) = +∞
h7→∞

26
Fórmulas Exponenciais: Mersenne e Fermat Seção 3.2

ou seja, para h suficientemente grande temos g(h) positivo, exatamente como precisavamos.
Num primeiro momento, a demonstração anterior pode parecer um pouco confusa. Vamos ver
o caso particular em que o polinômio f (x) tem grau 2 para que fique mais claro o que foi feito no
caso geral.
Se f (x) tem grau 2, ele se escreve como f (x) = ax2 + bx + c. Seja m um inteiro positivo tal
que f (m) = p é um número primo (positivo). Calculemos agora f (m + hp), onde h é um inteiro
positivo qualquer.

f (m + hp) = a(m + hp)2 + b(m + hp) + c

= am2 + 2amhp + ah2 p2 + bm + bhp + c
= (am2 + bm + c) + p · (2amh + aph2 + bh)
= p + p · (2amh + aph2 + bh)
= p · (1 + 2amh + aph2 + bh).

Para que f (m + hp) seja composto, precisamos que

1 + 2amh + aph2 + bh > 1 ⇒ 2amh + aph2 + bh > 0

h>0
⇒ 2am + aph + b > 0
−b − 2am
⇒ h>
ap

Portanto, se f (x) = ax2 + bx + c é um polinômio de coeficientes inteiros, a > 0, e f (m) = p é

−b − 2am
primo, então f (m + hp) é composto sempre que h > . Em particular, existem infinitos
ap
valores inteiros para x de modo que f (x) é composto.
Neste caso do polinômio de grau 2, conseguimos determinar uma cota inferior para o inteiro h
a partir da qual conseguimos garantir a existência de infinitos inteiros compostos que são atingidos
pelo polinômio f . No caso geral, não encontramos esta cota inferior, apenas usamos sua existência,
que é garantida pelo limite no infinito do polinômio em h.
Enfim, nossa busca por um polinômio cujos valores positivos são sempre primos é inútil, pelo
menos quando nos referimos a polinômios de um variável. Sabe-se que existe um polinômio de grau
25, à 26 variáveis, de modo que todos os seus valores positivos são primos
(c.f. [09], pg. 11-12). Surpreendente, não?

3.2 Fórmulas Exponenciais: Mersenne e Fermat

Duas são as fórmulas exponenciais de grande importância histórica

27
Capı́tulo 3 Números Primos

n
M (n) = 2n − 1 F (n) = 22 + 1

onde n é um inteiro não negativo.

Os números da forma M (n) são chamados números de Mersenne, e os da fomra F (n), números
de Fermat.
Os números de Mersenne estão relacionados com os chamados números perfeitos.

DEFINIÇÃO 3.2.1. Um número inteiro positivo é dito perfeito se é igual a metade da soma de
seus divisores positivos (incluindo n).

Por exemplo, 6 é perfeito, pois D(6) = {1, 2, 3, 6} ⇒ S(6) = 12 = 2 · 6.(1)

Observe que nenhum número primo é perfeito, pois se p é primo, seus divisores positivos são
1 e p. Para termos 1 + p = 2p, necessariamente devemos ter p = 1, que não é primo.
Euclides já sabia que os números da forma

2n−1 · (2n − 1)

são perfeitos quando 2n − 1 é primo. Na verdade, todo número perfeito par é da forma 2n−1 ·(2n −1).
Isso foi demonstrado pela primeira vez por Euler, e o resultado foi publicado postumametne em
1849. Antes de fazermos tal demonstração, vejamos uma proposição que será necessária.

PROPOSIÇÃO 3.2.2. Se b1 e b2 são inteiros positivos primos entre sı́, então

S(b1 b2 ) = S(b1 )S(b2 )

onde S(n) denota a soma dos divisores positivos de n.

β β β
DEMONSTRAÇÃO. Se b1 = pα1 1 pα2 2 pα3 3 · · · pαr r e b2 = q1 1 q2 2 q3 3 · · · qsβs , com pi0 s e qj 0 s primos, como
mdc(b1 , b2 ) = 1, temos que cada pi é distinto de cada qj .
A quantidade de divisores positivos de b1 é (α1 + 1)(α2 + 1) · · · (αr + 1) e a quantidade de
divisores positivos de b2 é (β1 + 1)(β2 + 1) · · · (βs + 1). Tal fato é facilmente demonstrado usando-
se o Princı́pio Fundamental da Contagem.
Temos que b1 b2 = pα1 1 pα2 2 · · · pαr r q1β1 q2β2 · · · qsβs , logo a quantidade de divisores de b1 b2 é igual a
(α1 + 1)(α2 + 1) · · · (αr + 1)(β1 + 1)(β2 + 1) · · · (βs + 1), ou seja, se b1 e b2 possuem x e y divisores
positivos, respectivamente, e mdc(b1 , b2 ) = 1, então b1 b2 possui xy divisores positivos. Digamos

1
D(n) denota o conjunto do divisores positivos de n e S(n) denota a soma dos divisores positivos de n

28
Fórmulas Exponenciais: Mersenne e Fermat Seção 3.2

que b1 tenha n divisores e b2 possua m divisores. Sendo assim

S(b1 )S(b2 ) = (r1 + r2 + · · · + rn )(s1 + s2 + · · · + sm )

X X
= ri sj
n X
X m
= ri sj
i=1 j=1

Note que a soma acima possui n · m parcelas, e além disso as parcelas são duas a duas distintas.
De fato, qualquer uma das parcelas é da forma ri sj , onde ri é um divisor de b1 e sj é um
divisor de b2 . Seja a = ri1 sj1 e b = ri2 sj2 duas parcelas da soma acima. Não podemos ter ri1 = ri2
e sj1 = sj2 simultaneamente, por motivos combinatórios. Suponha que ri1 = ri2 . Então a e b
são diferentes pois sj1 6= sj2 , o que faz com que a e b tenham decomposições primas diferentes, e
portanto não podem ser iguais. Algo análogo acontece se tivermos sj1 = sj2 . Agora, e se ri1 6= ri2
e sj1 6= sj2 ? Neste caso, como qualquer ri não possui fatores comuns com qualquer sj , também é
impossı́vel termos a = b, pois nesse caso terı́amos dois inteiros iguais com fatoração prima distinta,
absurdo. Portanto, as parcelas são de fato duas a duas distintas.
Se provarmos que qualquer parcela desta soma é um divisor de b1 b2 , concluiremos que essa
soma é igual e S(b1 b2 )
Seja rp sq uma parcela qualquer. Temos que rp |b1 ⇒ b1 = xrp , para algum x ∈ Z, e
sq |b2 ⇒ b2 = ysq , para algum y ∈ Z, logo b1 b2 = xrp usq = (xy)(rp sq ), ou seja, rp sq |b1 b2 . Como
cada parcela é um divisor de b1 b2 , e nesta soma temos n · m parcelas, essa é a soma dos n · m
divisores de b1 b2 . Portanto
S(b1 )S(b2 ) = S(b1 b2 )

Agora vamos mostrar esta caracterização dos números perfeitos.

PROPOSIÇÃO 3.2.3. Seja n um inteiro par. O inteiro n é um número perfeito se, e somente se,
n se escreve como 2s (2s+1 − 1), com s ∈ N e 2s+1 − 1 primo.

DEMONSTRAÇÃO. (⇐) Vamos mostrar que se s é um inteiro tal que 2s+1 − 1 é primo, então
n = 2s (2s+1 − 1) é perfeito. Para tanto, precisamos somar todos os seus divisores positivos e
concluir que tal soma é igual a 2n.
Seja n = 2s (2s+1 − 1). Se 2s+1 − 1 = p é primo, ele é um primo ı́mpar e é o único fator ı́mpar
de n. Observe as seguintes igualdades:

29
Capı́tulo 3 Números Primos

n = 1 × 2s p
= 21 × 2s−1 p
= 22 × 2s−2 p
= 23 × 2s−3 p
..
.
= 2s × 20 p

Note que n possui dois tipos de divisores:

(1) Divisores que são potências de 2.

(2) Divisores que são potências de 2 multiplicadas por p = 2s+1 − 1.

Os divisores que são do tipo (1) são 20 , 21 , 22 , ..., 2s e são em quantidade de s + 1.

Para obter os divisores do tipo (2), basta multiplicar cada divisor do tipo (1) por p:
2 p, 21 p, 22 p, ..., 2s p, logo estes também são em quantidade de s + 1.
0

Os divisores do tipo (1) formam uma PG com primeiro termo igual a 1 e razão 2. Os divisores
do tipo (2) formam outra PG com primeiro termo igual a p e razão 2. Para obter S(n), devemos
somar2 duas PG’s. Lembrando que a soma dos n primeiros termos numa PG de primeiro termo a
a(q n − 1)
e razão q é Sn = , temos:
q−1

S(n) = S(2s (2s+1 − 1)) = |20 + 21 + s 0 1

+ · · · + 2s p
{z· · · + 2} + |2 p + 2 p {z }
0 s+1 0 s+1
2 (2 − 1) 2 p(2 − 1)
= +
2−1 2−1
s+1 s+1
= (2 − 1) + p(2 − 1)
= (2s+1 − 1)(1 + p) = (2s+1 − 1)(1 + 2s+1 − 1)
= 2 · 2s (2s+1 − 1)
= 2n

Portanto, se s é um inteiro tal que 2s+1 − 1 é primo, então 2s (2s+1 − 1) é perfeito.

Os números perfeitos da forma 2s (2s+1 − 1) são chamados euclidianos. Vamos mostrar agora
que todos os números perfeitos pares são euclidianos.
(⇒) Primeiramente, observemos que um inteiro r é primo se, e somente se, S(r) = r + 1. De
fato, se r é primo, seus divisores positivos são r e 1, logo S(r) = r + 1.
2
A estratégia que usamos para somar os divisores de 2s (2s+1 − 1) pode ser estendida para encontrar a soma dos
divisores positivos de qualquer inteiro. Para ver esta e outras propriedades dos números inteiros, consulte [08].

30
Fórmulas Exponenciais: Mersenne e Fermat Seção 3.2

Agora, seja r um inteiro tal que S(r) = r + 1. O inteiro r tem pelo menos dois divisores: 1 e
r. Seja S(r) a soma dos divisores positivos de r diferentes de r e 1. Temos

S(r) = r + 1 + S(r)

ou seja, S(r) = 0 ⇒ r não possui divisores positivos diferentes de 1 e r, logo r é primo.

Seja n um número perfeito par. Tal inteiro n pode ser escrito como n = 2s t, com t ı́mpar e
s ≥ 1. Como n é perfeito, temos S(n) = 2n. Como t é ı́mpar, 2s e t são primos entre sı́. Por um
lado temos
P rop.3.2.2
S(n) = S(2s t) = S(2s )S(t)

Por outro lado, sendo n perfeito, também podemos escrever S(n) = 2n = 2 · 2s t = 2s+1 t.
Portanto temos
2s+1 t = S(2s )S(t) (3.1)

Os divisores de 2s são todas as potências de 2 com expoente de 0 até s, logo

20 (2s+1 − 1)
S(2s ) = 20 + 21 + 22 + · · · + 2s = = 2s+1 − 1
2−1

Substituindo em (3.1), obtemos

2s+1 t = (2s+1 − 1)S(t) (3.2)

Desta última equação, tiramos que 2s+1 divide (2s+1 − 1)S(t). Mas 2s+1 só possui fatores iguais a
2, e o inteiro 2s+1 − 1 é ı́mpar, logo 2s+1 e 2s+1 − 1 são primos entre sı́. Portanto, pela Proposição
2.1.3, temos que 2s+1 divide S(t), isto é, existe um inteiro q tal que

S(t) = 2s+1 q

Substituindo em (3.2), obtemos

2s+1 t = (2s+1 − 1)2s+1 q ⇒ t = (2s+1 − 1)q (3.3)

Sendo q um inteiro positivo, ou q = 1 ou q > 1. Se tivessemos q > 1, por (3.3) t teria

pelo menos 3 fatores distintos, a saber, 1, t e q. Daı́ teriamos S(t) ≥ 1 + t + q. Já sabemos que
S(t) = 2s+1 q. Também é de nosso conhecimento que t = (2s+1 − 1)q ⇔ t + q = 2s+1 q. Comparando
as duas últimas equações, chegamos em

S(t) = t + q

o que contradiz S(t) ≥ 1 + t + q. De onde veio tal contradição? Da suposição q > 1. Portanto,

31
Capı́tulo 3 Números Primos

necessariamente devemos ter q = 1.

Como temos q = 1, segue que t = 2s+1 − 1 e S(t) = t + 1. Portanto t é primo e concluı́mos que
se n é um número perfeito par, então se escreve como

n = 2s t = 2s (2s+1 − 1) (3.4)

onde 2s+1 − 1 é primo.

Mostramos assim que todo número perfeito par é da forma

2n−1 (2n − 1)

logo, para encontrarmos os números perfeitos pares, basta encontrarmos os primos de Mersenne.
O estudo dos números perfeitos ainda está em aberto: não se sabe ainda se existem ou não
números perfeitos ı́mpares. Sabe-se apenas que se existir um número perfeito ı́mpar, seguramente
ele tem mais de 200 digitos ([05], p. 99). Em [07] é verificado que determinados números ı́mpares
não podem ser perfeitos.
Um número de Mersenne M (n) = 2n − 1 só pode ser primo se n for primo. De fato, se n é
composto temos que n = rs. Daı́

2n − 1 = 2rs − 1 = (2r )s − 1s = (2r − 1)(2r(s−1) + · · · + sr + 1)

Temos então que se r divide n, então M (r) divide M (n), logo M (n) é composto.

Se n é composto, então M (n) é composto.

Observe, entretanto, que a recı́prova é falsa.

Se n é primo, M (n) pode ser primo ou composto

M (11) = 2047 = 23 · 89

Mais adiante veremos um método que permite encontrar fatores primos de M (p) quando
p é primo. Os números de Mersenne recebem esse nome devido a uma afirmação de Marin
Mersenne, frade e matemático amador do século XVII, que repercurtiu nos secúlos seguintes entre
os matemáticos. Segundo Mersenne, os números da forma M (n) = 2n − 1 seriam primos quando

n = 2, 3, 5, 7, 13, 17, 19, 31, 67, 127 e 257

e compostos para os outros 44 valores primos de n menores que 257. Nessa época, era comum os
matemáticos trocarem cartas, e era muito comum também não serem apresentadas justificativas
para resultados apresentados nessas cartas, e isso aconteceu com essa afirmação de Mersenne. Nos

32
Fórmulas Fatoriais Seção 3.3

séculos seguintes, outros matemáticos sugeriram correções na lista de Mersenne: alguns estavam
corretos, outros não.
Mas com certeza, o rei dos Teoremas sem demonstração era Fermat. Sendo um matemático
amador (era jurista de profissão), nunca se preocupou em escrever com rigor os resultados que
obtinha, e sempre desafiava outros matemáticos a demonstrar suas conjecturas, numa espécie de
competição (ou seria uma provocação da parte de Fermat?). O exemplo mais famoso é O Último
Teorema de Fermat, sobre o qual hoje sabemos que é verdade, mas que dificilmente teria sido
provado por Fermat no século XVII.
n
Sobre os números de Fertmat, ele afirmou que todos os números F (n) = 22 + 1 seriam primos.

0
F (0) = 22 + 1 = 3
1
F (1) = 22 + 1 = 5
2
F (2) = 22 + 1 = 17
3
F (3) = 22 + 1 = 257
4
F (4) = 22 + 1 = 65537
5
F (5) = 22 + 1 = 4294967297

Ele verificou somente até F (4), e estava errado. F (5) é composto, e isto foi provado por Euler
100 anos mais tarde. O curioso é que Fermat tinha um método para encontrar fatores primos
de M (n), e um método muito semelhante lhe daria um fator de F (5), mas isso não foi feito por
Fermat, mas sim por Euler. Esse caso dos números de Fermat é interessante para vermos que a
intuição não vale como argumento matemático.

3.3 Fórmulas Fatoriais

Vamos definir uma função semelhante ao fatorial

p# = “produto de todos os primos menores ou iguais a p”

Por exemplo

2# = 2
3# = 2 · 3 = 6
4# = 2 · 3 = 6
5# = 2 · 3 · 5 = 30
6# = 2 · 3 · 5 = 30

33
Capı́tulo 3 Números Primos

Note que se q < p são primos consecutivos, então

p# = q # p

Estamos interessados nos números da forma p# + 1. Observe a seguinte tabela

p p# p# + 1
2 2 3
3 6 7
5 30 31
7 210 211
11 2310 2311

Todos os valores da terceira coluna são primos. Será, então, que p# + 1 é primo para todo p?
Infelizmente não, pois
13# + 1 = 30031 = 59 · 509

Apesar da nossa frustração ainda podemos provar um resultado interessante sobre o número
#
p + 1.

PROPOSIÇÃO 3.3.1. O inteiro p# + 1 não possui nenhum fator primo menor ou igual a p.

DEMONSTRAÇÃO. Suponha, por absurdo, que p# + 1 tenha um fator primo q ≤ p. Isto significa
que q|(p# + 1), ou seja, existe r inteiro tal que qr = p# + 1. De modo equivalente, podemos
escrever
qr − p# = 1

Como q ≤ p, q é necessariamente fator de p# . Temos então que q|qr e q|p# , portanto q|(qr−p# ),
ou seja, q|1, o que implica q = 1. Mas q é primo, absurdo.
Esta proposição no diz que, mesmo quando p# + 1 é composto, seu menor fator primo é maior
do que p. Isto poderia nos levar a pensar num método para encontrar primos: se conhecemos
todos os primos até p, calculamos p# + 1 e tentamos fatorá-lo. Mas tal fatoração é impraticável,
pois mesmo para valores pequenos de p, p# + 1 é muito grande.
Na realidade, esta fórmula fatorial é um verdadeiro desastre se nossa intenção é construir
primos. Atualmente só se conhecem 16 primos da forma p# + 1, o maior deles para p = 24029.
Entretanto, a fórmula fatorial é interessante pois recupera o argumento usado por Euclides
para mostrar que existem infinitos primos.

TEOREMA 3.3.2. Existem infinitos números primos.

DEMONSTRAÇÃO. Se supusermos que há apenas uma quantidade finita de primos, teremos um que
é o maior de todos, digamos p. Consideramos agora o inteiro p# + 1. É claro que p# + 1 é maior

34
Fórmulas Fatoriais Seção 3.3

que p, e portanto maior que todos os primos. Se p# + 1 for primo, já chegamos a um absurdo, pois
temos um primo que é maior que p, que seria o maior primo existente. Se p# + 1 for composto,
já vimos que este mesmo inteiro possui um fator primo maior do que p, e novamente temos uma
contradição. Portanto não pode existir uma quantidade finita de números primos.

35
Capı́tulo 3 Números Primos

36
Capı́tulo

4
Aritmética Modular

Dado um conjunto X, uma relação “∼” no conjunto X pode ser entendida como uma maneira de
comparar dois elementos do conjunto X. Por exemplo, se considerarmos o conjunto dos membros
de uma famı́lia onde temos pais, mães, filhos, filhas, tios, sobrinhos, etc., podemos definir algumas
relações. Uma relação poderia ser a seguinte: Dados dois elementos x e y, dizemos que x está
relacionado com y, indicado por x ∼ y, se x for filho(a) de y. É claro que não estamos interessados
nesse tipo de relação, mas sim em relações definidas sobre conjunto numéricos. Neste capı́tulo
veremos uma importante relação definida no conjunto dos inteiros.

4.1 Relações de Equivalência

Formalmente, uma relação de um conjunto A para um conjunto B é um subconjunto do produto
cartesiano A × B. Se a ∈ A, b ∈ B, R ⊂ A × B e (a, b) ∈ R dizemos que a está relacionado
a b segundo a relação R, e indicamos isso com aRb. Quando definimos uma relação R de um
conjunto X para o próprio conjunto X, dizemos simplesmente que a relação R está definida sobre
o conjunto X. Este tipo de relação pode apresentar certas propriedades.
Seja X um conjunto não vazio e ∼ uma relação definida sobre X. Se para qualquer elemento
x ∈ X tivermos que x ∼ x, a relação ∼ é uma relação reflexiva. Uma relação ∼ é dita simétrica se
sempre que x ∼ y também tivermos y ∼ x. Finalmente, uma relação ∼ é dita transitiva se x ∼ y
e y ∼ z implicar em x ∼ z.
Temos exemplos de relações que satisfazem algumas ou todas as propriedades acima. A Relação
“<”, por exemplo, definida sobre R, é transitiva, mas não é simétrica nem reflexiva. A relação de
igualdade “=” é reflexiva, simétrica e transitiva. Vale lembrar que nenhuma das três propriedades
pode ser deduzida das outras: trabalhando com conjuntos finitos conseguimos facilmente definir
relações que atendam nenhuma, apenas uma ou apenas duas das propriedades reflexiva, simétrica
e transitiva.
As relações que são reflexivas, simétricas e transitivas, como a relação de igualdade, são
chamadas de Relações de Equivalência. Mas o que uma relação ∼ de equivalencia faz com o con-

37
Capı́tulo 4 Aritmética Modular

junto X sobre o qual está definida? Ela classifica os elementos de X, que possuem propriedades
semelhantes, em subconjuntos de X. Esses subconjuntos de X, determinados por uma relação de
equivalência, são chamados Classes de Equivalência.

DEFINIÇÃO 4.1.1. Seja X um conjunto e ∼ uma relação de equivalência definida em X. Se

x ∈ X então a classe de equivalência de x é o conjunto dos elementos de X que são equivalentes
a x por ∼. Em sı́mbolos, se x denota a classe de equivalência de x, temos:

x = {y ∈ X : y ∼ x}

Dizemos que x é um representante da classe x.

Um princı́pio básico sobre as classes de equivalência é o seguinte: qualquer elemento de

uma classe é um representante da classe toda.
Este princı́pio, juntamente com as propriedades de relações de equivalência, nos permite
demonstrar algumas proposições.

PROPOSIÇÃO 4.1.2. Se y é um elemento da classe de x, então as classes de x e y são iguais.

Em sı́mbolos: se x ∈ X e y ∈ x então x = y.

DEMONSTRAÇÃO. Lembre-se que x e y são classes de equvalência, ou seja, são subconjuntos de X.

Se queremos mostrar que x = y, devemos mostrar que x ⊆ y e y ⊆ x.
1) Se y ∈ x, por definição de classe de equivalência temos y ∼ x; pela propriedade simétrica
x ∼ y. Seja z um elemento qualquer de x. Temos que z ∼ x. Como x ∼ y, segue da transitividade
que z ∼ y, e portanto z ∈ y. Logo, x ⊆ y.
2) Se z ∈ y, temos z ∼ y. Como y ∈ x, temos y ∼ x. Pela propriedade transitiva, concluı́mos
que z ∼ x, logo z ∈ x, e portanto y ⊆ x.
De 1) e 2) concluı́mos que x = y.

PROPOSIÇÃO 4.1.3. Seja X um conjunto não vazio e ∼ uma relação de equivalência definida
sobre X.
(1) X é a união de todas as classes de equivalência.
(2) Duas classes de equivalência distintas são disjuntas.

DEMONSTRAÇÃO. (1) Como todo elemento de x pertence a sua própria classe, devido a propriedade
simétrica, temos que
[
x=X
x∈X
.
(2) Sejam x e y duas classes distintas de X, ou seja, existe um elemento que pertence a uma
delas e que não pertence à outra. Suponha que exista um elemento z ∈ X tal que z ∈ x ∩ y.

38
Inteiros Módulo n Seção 4.2

Isto significa que z ∈ x e z ∈ y. Pela proposição anterior, temos z = x z = y, o que nos leva a
x = y, o que contradiz a hipótese de x e y serem classes distintas.
Portanto x ∩ y = ∅.
Os dois itens da proposição anterior nos dizem que as classes de equivalência de um conjunto
X por uma relação ∼ formam uma partição de X.
O conjunto das classes de equivalência de ∼ em X é chamado conjunto quociente de X por ∼.
Os elementos do conjunto quociente são subconjuntos de X - as classes de equivalência. Ou
seja, o conjunto quociente não é subconjunto de X, mas subconjunto do conjunto das partes de X.
Lembre-se que o conjunto das partes de X é o conjunto cujos elementos são todos os subconjuntos
de X.

4.2 Inteiros Módulo n

Usamos congruências diariamente: na contagem das horas, dos minutos, dos segundos, na con-
tagem dos dias, semanas, meses, na medição de ângulos, etc.
Vamos definir uma relação em Z muito útil na Teoria dos Números: a relação de congruência
módulo n.

DEFINIÇÃO 4.2.1. Dados três inteiros a, b, e n, dizemos que a é congruente a b módulo n,

denotando por a ≡ b (mod n), se n divide b − a. Em sı́mbolos

a ≡ b (mod n) ⇔ n|(b − a). (4.1)

Primeiramente vamos mostrar que a congruência módulo n é uma relação de equivalência.

PROPOSIÇÃO 4.2.2. Sendo n um inteiro, a relação de congruência módulo n em Z, segundo a

definição acima, é uma relação de equivalência em Z, ou seja, satisfaz as seguintes propriedades:

(1) ∀a ∈ Z, a ≡ a (mod n);

(2) ∀a, b ∈ Z, se a ≡ b (mod n), então b ≡ a (mod n);

(3) ∀a, b, c ∈ Z, se a ≡ b (mod n) e b ≡ c (mod n), então a ≡ c (mod n).

DEMONSTRAÇÃO. Para demonstrarmos a validade das propiedades acima, basta manipularmos a

definição de congruência.

(1) 0 = n · 0 ⇔ n|0 ⇔ n|(a − a) ⇔ a ≡ a (mod n).

(2) a ≡ b (mod n) ⇔ n|(b − a) ⇔ b − a = nr ⇔ a − b = n(−r) ⇔ n|(a − b) ⇔ b ≡ a (mod n)

39
Capı́tulo 4 Aritmética Modular

(3)
a ≡ b (mod n) ⇔ n|(b − a) ⇔ b − a = nr, para algum r ∈ Z. (4.2)

b ≡ c (mod n) ⇔ n|(c − b) ⇔ c − b = ns, para algum s ∈ Z. (4.3)

Somando as equações (4.2) e (4.3) obtemos

c − a = n(r + s) ⇔ n|(c − a) ⇔ a ≡ c (mod n).

O conjunto que desejamos estudar de maneira mais aprofundada é o conjunto quociente de Z

pela relação de congruência módulo n. Denotaremos tal conjunto por Zn , o conjunto do inteiros
módulo n.
Quais são os elementos de Zn ? Por definição, são subconjuntos de Z: as classes de equivalência
da congruência módulo n.
Seja a ∈ Z. A classe de a é formada pelos elementos b ∈ Z tais que a ≡ b (mod n), isto é,
n|(b − a), ou seja, existe um inteiro k tal que b − a = nk. Portanto os elementos de a são da forma
b = a + nk.
a = {a + nk, k ∈ Z}

Se a é um inteiro, podemos dividı́-lo por n, e encontraremos q e r inteiros tais que

a = nq + r e 0 ≤ r < n.

Temos que a − r = nq, ou seja, a ≡ r (mod n). Portanto, qualquer inteiro é congruente
módulo n a algum inteiro no intervalo de 0 a n − 1.
Portanto, Zn é formado pelas classes 0, 1, ..., n − 1.

Zn = {0, 1, 2, , , , n − 1}.

Podemos ainda nos perguntar se não é possı́vel reduzir ainda mais a quantidade de classes que
constituem Zn . Será que ao tomarmos as classes 0, 1, ..., n − 1 não estamos tomando alguma classe
duas vezes, ou seja, será que se a e b são dois inteiros com 0 < a, b < n e a 6= b, podemos ter
a=b?
A resposta é não. Sejam a e b dois inteiros com 0 < a, b < n e a 6= b. Podemos escrever as
seguintes desigualdades:
0<a<n

−n < −b < 0

40
Inteiros Módulo n Seção 4.2

Somando as desigualdades acima obtemos −n < a − b < n ou, de maneira equivalente,

0 ≤ |a − b| < n. (4.4)

Suponhamos sem perda de generalidade, que a > b. Então, (4.4) fica

0 ≤ a − b < n. (4.5)

Temos como hipótese inicial que a 6= b, ambos positivos e menores do que n, e queremos
concluir que ā 6= b. Se tivessemos a = b, teriamos a ≡ b (mod n), ou seja, existiria um inteiro r
tal que
a − b = nr (4.6)

Substituindo em (4.5), obtemos

0 ≤ nr < n ⇒ 0 ≤ r < 1 ⇒ r = 0 (4.7)

Mas se r = 0, a equação (4.6) nos leva a a = b, uma contradição. Portanto, se a 6= b e

0 < a, b < n devemos ter a 6= b.
Portanto, o número mı́nimo de classes que compõem Zn é n classes, a saber,

Zn = {0, 1, 2, , , , n − 1}

Quando uma classe estiver representada na forma a com 0 ≤ a ≤ n − 1, diremos que está na
forma reduzida.
Vamos agora definir operações em Zn .

DEFINIÇÃO 4.2.3. Considere o conjunto Zn . Dadas duas classes a e b em Zn , definimos

i) a + b = a + b

i) a · b = a · b

Note que para efetuarmos a + b (soma de classes) teremos de escolher um representante a da

classe a e outro representante b da classe b. Em seguida somamos a e b (soma de inteiros). Final-
mente, determinamos a classe de a + b. A multiplicação acontece de forma análoga. Precisamos
garantir que a escolha dos representantes de classe a e b não interfere no resultado final.

LEMA Quaisquer que sejam os representantes escolhidos para efetuar a soma ou o produto
4.2.4.

de duas classes de Zn , o resultado é sempre a mesma classe.

DEMONSTRAÇÃO. Sejam a e b duas classes de Zn . Suponha que a = a0 e b = b0 , ou seja, a e a0 são

representantes da classe a, e b e b0 sejam representantes da classe b.

41
Capı́tulo 4 Aritmética Modular

Queremos mostrar que a + b = a0 + b0 e a · b = a0 · b0 .

(1) Se a = a0 , temos que a − a0 é múltiplo de n. De modo análogo, b − b0 é múltiplo de n. Se
somarmos múltiplos de n, ainda obtemos um multiplo de n, ou seja,

(a − a0 ) + (b − b0 ) = nk ⇔ (a + b) − (a0 + b0 ) = nk
⇔ a + b ≡ a0 + b0 (mod n)
⇔ a + b = a0 + b 0

(2) No caso da multiplicação, o raciocı́nio é parecido.

a = a0 ⇒ a − a0 = nr, para algum r ∈ Z ⇒ a = a0 + nr

b = b0 ⇒ b − b0 = ns, para algum s ∈ Z ⇒ b = b0 + ns

Dai,
a · b = (a0 + nr)(b0 + ns) = a0 · b0 + (a0 s + b0 r + nrs)n

ou seja, ab − a0 b0 é múltiplo de n, portanto ab ≡ a0 b0 (mod n), o que nos leva a a · b = a0 · b0

Mostramos assim que as operações de adição e multiplicação estão bem definidas em Zn . Essas
operações gozam das seguintes propriedades.

Adição: (a + b) + c = a + (b + c)
a+b=b+a
a+0=a
a + −a = 0
Múltiplicação: (a · b) · c = a · (b · c)
a·b=b·a
a·1=a
Distributiva: a · (b + c) = a · b + a · c
As demonstrações destas propriedades decorrem diretamente das definições de + e · em Zn e
das propriedades análogas em Z para + e ·. A tı́tulo de exemplo, vamos demonstrar a distributiva:

a · (b + c) = a · (b + c) = a · (b + c) = ab + ac = ab + ac = a · b + a · c

Até aqui, parece que Zn se comporta como Z, no que se refere as operações. Vamos dar um
exemplo que mostra que Zn não é tão familiar quanto parece.
Considere Z6 . As classes 2 e 3 são diferentes de 0. Mas

2·3=6=0

42
Aplicações Seção 4.3

O produto de duas classes não nulas pode ser a classe 0. Isso não acontece em Z.
Antes de discutirmos melhor essa anomalia, vamos ver algumas aplicações das ideias discutidas
até aqui.

4.3 Aplicações

4.3.1 Critérios de Divisibilidade

Podemos usar congruências para demonstrar os critérios de divisibilidade.
(1) Um número é divı́sivel por 3 se a soma de seus algarismos é divisı́vel por 3.
Seja a um número inteiro, e sua expansão decimal

a = an an−1 ...a1 a0 , ai ∈ {0, 1, 2, ..., 9}

Podemos escrever
a = 10n an + 10n−1 an−1 + · · · + 10a1 + a0

Como 10 ≡ 1 (mod 3), qualquer potência de 10 é congruente a 1 módulo 3. Portanto

a ≡ an + an−1 + · · · + a1 + a0 (mod 3).

Logo a é divisı́vel por 3, isto é, a ≡ 0 (mod 3), se, e somente se, an + an−1 + · · · + a1 + a0 também
o for.
Como 10 ≡ 1 (mod 9), os resultados acima se repetem para a divisão por 9.

(2) Um número é divisı́vel por 11 se a soma alternada de seus algarismos for divisı́vel por 11.

Novamente, vamos olhar para as potências de 10, mas agora usando módulo 11.

10 ≡ −1 (mod 11) ⇒ 10k ≡ (−1)k (mod 11)

ou seja, 10k é congruente 1 ou −1, dependendo da paridade de k. Portanto

a ≡ (−1)n an + (−1)n−1 an−1 + · · · + a2 − a1 + a0 (mod 11)

Obtivemos, assim, a soma alternada dos algarismo de a.

4.3.2 Potências
Outra aplicação do conceito de congruência é o cálculo dos restos da divisão de uma potência por
um número qualquer. Vejamos alguns exemplos.

43
Capı́tulo 4 Aritmética Modular

(1) Qual o resto da divisão de 10135 por 7 ?

Primeiramente procuramos alguma regularidade nas potências de 10.

10 ≡ 3 (mod 7) 104 ≡ 4 (mod 7)

102 ≡ 2 (mod 7) 105 ≡ 5 (mod 7)
103 ≡ 6 (mod 7) 106 ≡ 1 (mod 7)

Como 106 ≡ 1 (mod 7), e 135 = 6 · 22 + 3, temos

10135 ≡ 106·22+3 ≡ (106 )22 · 103 ≡ 122 · 103 ≡ 6 (mod 7)

portanto, o resto da divisão de 10135 por 7 é 6.

(2) Qual o resto da divisão de 364 por 31 ?

Vamos analisar as potências de 3 módulo 31

3 ≡ 3 (mod 31)
32 ≡ 9 (mod 31)
33 ≡ 27 ≡ −4 (mod 31)
34 ≡ 19 ≡ −12 (mod 31)

Vamos fazer uso da congruência 33 ≡ −4 (mod 31). Como 64 = 3 · 21 + 1 temos

364 ≡ (33 )21 · 3 ≡ (−4)21 · 3 ≡ (−1) · 242 · 3 (mod 31)

Note que 25 ≡ 32 ≡ 1 (mod 31) e 42 = 5 · 8 + 2. Daı́

364 ≡ (−1) · 242 · 3

≡ (−1) · (25 )8 · 22 · 3
≡ (−1) · 18 · 12
≡ −12 ≡ 19 (mod 31)

Portanto o resto da divisão de 364 por 31 é 19.

Neste caso, não procuramos r de modo que 3r ≡ 1 (mod 31). Usamos de outro artifı́cio. Será
que tal r existe?

44
Aplicações Seção 4.3

Seja r um inteiro. Temos apenas 3 possibilidades: r = 3k ou r = 3k + 1 ou r = 3k + 2. No

primeiro caso podemos escrever:

3r ≡ (33 )k ≡ (−4)k ≡ (−1)k · 22k (mod 31)

Seria ideal se k fosse par e 2k fosse múltiplo de 5 (o que só acontece se k já for múltiplo de 5),
pois isso acarretaria
3r ≡ (25 )q ≡ 1 (mod 31)

O menor inteiro k múltiplo de 2 e de 5 ao mesmo tempo é 10, o que nos leva a r = 30. Assim
temos:
330 ≡ (33 )10 ≡ (−4)10 ≡ 220 ≡ (25 )4 ≡ 14 ≡ 1 (mod 31)

Um último exemplo.

(3) Qual o resto da divisão de 635 por 16 ?

Não adianta procurarmos uma potência de 6 cujo resto da divisão por 16 é 1, pois
4
6 ≡ 0 (mod 16), portanto

635 ≡ 64 · 631 ≡ 0 · 631 ≡ 0 (mod 16)

4.3.3 Equações Diofantinas

O conceito de congruência ajuda a determinar a existência (ou não) de soluções de equações
diofantinas. Equações diofantinas são equações em várias incógnitas, com coeficientes inteiros, e
estamos interessados em determinar soluções inteiras destas equações.
Exemplo: 3x − 2y = 1
x3 + y 3 = z 3
x3 − 117y 3 = 5
Determinar se existem ou não soluções de equações diofantinas lineares, e encontrá-las caso
existam, é relativamente fácil com o auxı́lio do mdc e do algoritmo euclidiano estendido, como já
vimos no capı́tulo 1.
Mas e se a equação for não-linear? Alguns casos podem ser resolvidos com o auxı́lio de con-
gruência.
Considere a equação x3 − 117y 3 = 5. Suponhamos que tal equação admite solução inteira
(x0 , y0 ). Então
x30 − 117y03 = 5.

Como x0 e y0 são inteiros, a igualdade acima é uma relação entre inteiros, logo podemos reduzı́-la

45
Capı́tulo 4 Aritmética Modular

a módulo 9. Sendo assim

x30 − 117y03 ≡ 5 (mod 9)

Mas 117 = 9 · 13, ou seja, 117 ≡ 0 (mod 9), portanto a equação se reduz a

x30 ≡ 5 (mod 9)

Mas não existe x inteiro que satisfaça essa congruência. As classes distintas módulo 9 são
representadas pelos números de 0 a 8. Vejamos o que acontece com seus cubos.
Classe 0 1 2 3 4 5 6 7 8
Cubo 0 1 8 0 1 8 0 1 8
Como o cubo de qualquer inteiro é congruente a 0, 1 ou 8, módulo 9, a equação x30 ≡ 5 (mod 9)
não tem solução. Portanto
x3 − 117y 3 = 5

também não tem solução inteira.

Vejamos mais um exemplo: vamos mostrar que a equação x2 − 7y 2 = 3 não tem solução inteira.
Suponha, por absurdo, que exista uma solução inteira

x20 − 7y02 = 3

Reduzindo a equação a módulo 7, obtemos

x20 − 7yo2 ≡ x20 ≡ 3 (mod 7)

Agora, vejamos o que acontece com um elemento de Z7 quando o elevamos ao quadrado.

Classe 0 1 2 3 4 5 6
Cubo 0 1 4 2 2 4 1
Se a equação admitisse solução inteira (x0 , y0 ) terı́amos x20 ≡ 3 (mod 7). Mas isso é impossı́vel,
pois o quadrado de um inteiro qualquer só pode ser congruente a 0, 1, 2 ou 4, módulo 7.
Portanto x2 − 7y 2 = 3 não adimite solução inteira.
O que vimos até aqui foram aplicações modestas dos Inteiros Módulo n. Nos próximos capı́tulos
vamos ver que esse conjunto pode nos render resultados muito mais surpreendentes. Antes, vamos
voltar a primeira diferença que percebemos existir entre Z e Zn .

4.4 Divisão Modular

O primeiro fato que diferenciou Z de Zn (além de um ser infinito e o outro finito) foi o fato de
que, em Z, o produto de dois elementos não nulos é sempre não nulo, mas em Zn isso pode não

46
Divisão Modular Seção 4.4

acontecer. Como vimos, em Z6 ,

2·3=6=0

Admita por um instante, que a e b sejam números reais. Podemos definir a divisão da seguinte
1 1
maneira: dividir a por b significa multiplicar a por . O número real é o inverso de b e é
b b
caracterizado pela equação
1
b· =1
b
Note que se adotarmos essa definição, nos inteiros só conseguimos dividir por 1 ou por −1,
pois são os únicos inteiros que possuem inverso também inteiro. Já em R qualquer elemento não
nulo possui inverso. Vamos transpor essa definição para Zn .

DEFINIÇÃO 4.4.1. Seja a ∈ Zn . A classe α ∈ Zn é o inverso de a se a equação a · α = 1 é

verificada em Zn .

Segundo essa definição, a classe nula não possui inverso, pois

0 · α = 0 · α = 0 6= 1, ∀ α ∈ Zn

O que ocorre de diferente em Zn é que outros elementos diferentes de 0 podem não possuir
inverso também.
Suponha que a ∈ Zn possua inverso α. Isso significa que a · α = 1, e essa equação equivale a
dizer que aα − 1 é divisı́vel por n, ou seja, existe um inteiro k tal que aα − 1 = kn, ou ainda

aα − kn = 1.

Esta última equação nos leva a concluir que mdc(a, n) = 1. Portanto, se a possui inverso em Zn
então mdc(a, n) = 1. Será que a reciproca é verdadeira?
Seja a um inteiro e suponha que mdc(a, n) = 1. Sabemos que existem inteiros α e β tais que

aα + nβ = 1

e tais α e β são calculados usando-se o algoritmo euclidiano estendido. Mas

aα + nβ = 1 ⇔ aα − 1 = n(−β) ⇔ a · α = 1

Portanto a classe α calculada pelo algoritmo euclidiano estendido é o inverso de a em Zn .

Concluimos que se mdc(a, n) = 1, então a classe a possui inverso em Zn . Isso demonstra o
seguinte teorema.

TEOREMA 4.4.2 (Teorema da Inversão). A classe a possui inverso em Zn se, e somente se, a e
n são primos entre sı́.

47
Capı́tulo 4 Aritmética Modular

Observemos que a demonstração feita também nos diz como calcular o inverso quando ele
existe: basta usarmos o algoritmo euclidiano estendido.
Por exemplo, qual o inverso de 5 em Z27 ? Vamos aplicar o algoritmo euclidiano estendido.

restos quocientes x y
27 - 1 0
5 - 0 1
2 5 1 -5
1 2 -2 11

Temos então que mdc(5, 27) = 1, logo 5 possui inverso em Z27 . E mais

5 · 11 − 27 · 2 = 1 ⇔ 5 · 11 = 1

ou seja, 11 é o inverso de 5 em Z27 .

Vamos nos ater mais aos elementos inversı́veis de Zn . O conjunto do elementos de Zn que
possuem inverso será denotato por U (n).

U (n) = {a ∈ Zn : mdc(a, n) = 1} (4.8)

É simples determinar quais são os elementos de U (p) quando p é primo. Nessa situação,
mdc(a, p) = 1 significa que p não divide a. Se p divide a, então a = 0. Sendo assim, quando p é
primo, todas as classes diferentes de 0 possuem inverso.

U (p) = Zp \{0}

Mas isso só vale quando p é primo. Em Z4 = {0, 1, 2, 3} os únicos primos com 4 são 1 e 3,
portanto
U (4) = {1, 3}

Em Z8 = {0, 1, 2, 3, 4, 5, 6, 7} temos U (8) = {1, 3, 5, 7}.

Uma caracterı́stica importante de U (n) é que o produto de dois elementos de U (n) ainda é um
elemento de U (n).(1)
Se a e b são elementos de U (n), eles possuem inversos α e β, respectivamente. Vejamos que a · b
também possui inverso, e portanto está em U (n). Lembremos que a operação · de Zn é associativa
e comutativa, daı́
(a · b) · (α · β) = (a · α) · (b · β) = 1 · 1 = 1

Portanto α · β é o inverso de a · b.
1
Essa é uma caracterı́stica necessária para U (n) ser grupo. Mais adiante veremos que U (n) munido da
operação · é um grupo; mais ainda, é um grupo abeliano.

48
Divisão Modular Seção 4.4

O conjunto U (n) será alvo de nossas atenções nos próximos capı́tulos. Duas coisas que faremos:

• Determinar o número de elementos de U (n) em função de n;

• Descobrir quando U (n) tem uma raiz primitiva.

Vamos definir o que é raiz primitiva e ver exemplos.

DEFINIÇÃO 4.4.3. Uma classe a de U (n) é uma raiz primitiva se todo elemento de U (n) é igual
a uma potência de a.

Por exemplo, 3 é uma raiz primitiva de U (7)

1

3 =3 


2 
3 =2 



3 
3 =6 
4 U (7)
3 =4 


5 
3 =5 



6 
3 =1 

Ainda em U (7), vemos que 2 não é uma raiz primitiva. De fato, como 23 ≡ 1 (mod 7), se r é
um inteiro temos que r = 3k + s, com s = 0, 1, 2. Daı́,


 23k ≡ (23 )k ≡ 1
2r ≡ 23k+1 ≡ (23 )k · 2 ≡ 2 (mod 7)

 3k+2
2 ≡ (23 )k · 4 ≡ 4

Portanto, como qualquer potência de 2 é congruente a 1, 2 ou 4, módulo 7, 2 não é uma raiz

primitiva de U (7)
Agora que definimos o que são elementos inversı́veis em Zn , podemos falar de “divisões” em
Zn .
Se queremos dividir a por b, é necessário saber se b está em U (n). Se b ∈
/ U (n), a divisão é
impossı́vel. Se b ∈ U (n), calculamos o inverso de b, digamos β. Daı́, a ÷ b = a · β.
O teorema da inversão nos ajuda a resolver congruências lineares. Uma congruência linear é
uma equação como a seguinte:
ax ≡ b (mod n)

com a, b ∈ Z.
Para encontrarmos quais valores de x são soluções da congruência, precisamos “dividir” ambos
os membros por a, para que possamos isolar x. Se a for inversı́vel módulo n, isto é, a ∈ U (n),
então a congruência tem uma única solução em Zn : se α é o inverso de a em Zn , temos

a·x=b⇒α·a·x=α·b⇒x=α·b

49
Capı́tulo 4 Aritmética Modular

Por exemplo, considere a congruência 3x ≡ 12 (mod 7). Note que estamos trabalhando em
Z7 . Como 3 é primo com 7, ele possui inverso módulo 7, a saber

3 · 5 = 15 = 1

ou seja, 5 é o inverso de 3 em Z7 . Portanto temos

3x ≡ 12 (mod 7) ⇒ x ≡ 5 · 12 ≡ 60 ≡ 4 (mod 7)

Agora, se na congruência ax ≡ b (mod n) tivermos mdc(a, n) 6= 1, pode ou não existir solução

em Zn . Vejamos dois exemplos.
A equação 2x ≡ 1 (mod 8) não tem solução. De fato, se existisse uma solução inteira x0 , isso
significaria que 2x0 − 1 é divisı́vel por 8, ou seja, existiria um inteiro k tal que

2x0 − 1 = 8k

mas na equação acima temos um inteiro ı́mpar no lado esquerdo e um inteiro par no lado direito,
o que é impossı́vel. Portanto realmente 2x ≡ 1 (mod 8) não tem solução. Nesse caso tı́nhamos
mdc(2, 8) 6= 1.
Considere agora, ainda em Z8 , a equação 6x ≡ 2 (mod 8). Nesse caso, mesmo com
mdc(6, 8) 6= 1, a equação apresenta solução, mas não única. De fato

6 · 3 ≡ 18 ≡ 2 (mod 8) ∴ 3 é solução.

6 · 7 ≡ 42 ≡ 2 (mod 8) ∴ 7 é solução.

e portanto a equação tem duas soluções distintas em Z8 . Portanto, quando na equação

ax ≡ b (mod n) tivermos mdc(a, n) 6= 1, precisamos analisar com calma a equação, pois tudo
pode acontecer.
O que fizemos até agora foi estudar as ferramentas básicas que nos permitirão entender e
demonstrar teoremas que fundamentam o funcionamento da criptografia RSA. Começaremos no
próximo capı́tulo com o Pequeno Teorema de Fermat.

50
Capı́tulo

5
Fermat e Primalidade

O pequeno teorema de Fermat afirma que se p é um número primo e a é um inteiro qualquer,

então p divide ap − a. Casos particulares já eram conhecidos antes de Fermat obter este resultado
geral. Os chineses sabiam que se p é primo, então p divide 2p − 2. Usaremos o teorema de Fermat
na busca por testes de primalidade.

5.1 Pequeno Teorema de Fermat

TEOREMA 5.1.1 (Pequeno Teorema de Fermat). Seja p um número primo e a um número inteiro
qualquer. Então
ap ≡ a (mod p) (5.1)
A demonstração deste teorema se dá por indução sobre a, mas antes precisamos demonstrar
um lema auxiliar.
LEMA 5.1.2. Seja p um número primo e a e b inteiros quaisquer. Então

(a + b)p ≡ ap + bp (mod p)

DEMONSTRAÇÃO. Usando o binômio de Newton para expandir o lado esquerdo da equação acima,
obtemos.
p−1
p
X
p pp p−i i
(a + b) = a + b + a b
i=1
i

Para que o lema esteja provado, basta mostrarmos que

p−1
X p
ap−i bi ≡ 0 (mod p)
i=1
i

Observe o número binomial

p p(p − 1)(p − 2) · · · (p − i + 1)
=
i i!

51
Capı́tulo 5 Fermat e Primalidade

Sabemos que este número é inteiro, ou seja, o demoninador i! é totalmente cancelado por termos
do numerador. Como 1 ≤ i ≤ p − 1 e p é primo, o fator p que aparece no numerador não é
cancelado por nenhum fator do denominador. Logo pi é múltiplo de p quando 1 ≤ i ≤ p − 1, e

portanto
p−1
X p p−i i
a b ≡ 0 (mod p)
i=1
i

finalizando a demonstração do lema.

Agora vamos demonstrar o Pequeno Teorema de Fermat, que chamaremos daqui em diante
apenas de Teorema de Fermat.
DEMONSTRAÇÃO. (Teorema de Fermat) Seja p um inteiro primo. Inicialmente, vamos demonstrar
por indução que a afirmação vale para os naturais. É evidente que 0p ≡ 0 (mod p).
Suponhamos, então, que k p ≡ k (mod p). Queremos mostrar que (k + 1)p ≡ k + 1 (mod p).
Usando o lema anterior
(k + 1)p ≡ k p + 1p ≡ k p + 1 (mod p)

Mas pela hipotese de indução temos k p ≡ k (mod p), logo

(k + 1)p ≡ k + 1 (mod p)

Portanto ap ≡ a (mod p) para a ≥ 0. Vamos agora estender o resultado para os inteiros negativos.
Seja a um inteiro negativo. Então −a é positivo, logo podemos aplicar o que já provamos para
o inteiro −a.
(−a)p ≡ −a (mod p)

Agora temos dois casos a considerar: ou p é ı́mpar ou p = 2.

No primeiro caso, temos

(−a)p ≡ (−1)p ap ≡ −ap (mod p)

Substituindo na equação anterior obtemos −ap ≡ −a. Multiplicando esta por −1, chegamos à

ap ≡ a (mod p)

Agora, se p = 2, devemos verificar que a2 ≡ a (mod 2), o que equivale a mostrar que
a(a − 1) ≡ 0 (mod 2). Como a e a − 1 são números consecutivos, um deles é par, portanto
a(a − 1) é múltiplo de dois, ou seja,

a2 − a ≡ 0 (mod 2)

52
Pequeno Teorema de Fermat Seção 5.1

o que equivale a
a2 ≡ a (mod 2).

Portanto, o teorema é válido para qualquer inteiro a.

Demonstramos assim, o Teorema de Fermat. Vamos começar vendo algumas aplicações in-
gênuas do teorema. Nas póximas seções veremos aplicações mais interessantes. Primeiramente
vamos reformular o enunciado.
O teorema que demonstramos diz que se p é primo e a é um inteiro qualquer, então
ap ≡ a (mod p). Se p divide a, temos que a ≡ 0 (mod p), e daı́ ap ≡ 0 (mod p), e neste
caso o teorema não nos diz muito. Vamos supor então que p não divide a, ou seja, mdc(a, p) = 1.
Pelo teorema da inversão, a é invesı́vel módulo p. Seja a0 um inteiro tal que a · a0 ≡ 1 (mod p).
Agora, multiplicamos ambos os membros de ap ≡ a (mod p) por a0 e obtemos

a0 · a · ap−1 ≡ a0 · a (mod p) ⇒ ap−1 ≡ 1 (mod p)

Esta é a nova versão do Teorema de Fermat.

TEOREMA 5.1.3 (Teorema de Fermat II). Seja p um número primo e a um inteiro que não é
divisı́vel por p. Então
ap−1 ≡ 1 (mod p)

Esta versão do teorema é útil para o cálculo de potências módulo p primo. Expliquemos melhor.
Considere três inteiros positivos a, k e p, suponha que p seja primo e também que p 6 |a. Vamos
supor que k seja grande (pois é isso que torna os cálculos trabalhosos). O problema é encontrar a
forma reduzida de ak módulo p, ou seja, encontrar o resto da divisão de ak por p. O teorema de
Fermat nos ajuda neste ponto.
Estamos supondo k grande, logo podemos supor k ≥ p − 1. Dividimos, agora, k por p − 1, e
obtemos k = (p − 1)q + r, onde o resto r satisfaz 0 ≤ r ≤ p − 2. Temos

ak ≡ a(p−1)q+r ≡ (ap−1 )q · ar (mod p)

Pelo teorema de Fermat, ap−1 ≡ 1 (mod p), e portanto

ak ≡ ar (mod p).

Vamos a um exemplo numérico para mostrar a utilidade deste resultado. Vamos calcular
1684948
3 módulo 17. Neste caso, temos a = 3, p = 17 e k = 1684948. Primeiramente, dividimos k
por p − 1.
1684948 = 16 · 105309 + 4

53
Capı́tulo 5 Fermat e Primalidade

Portanto
31684948 ≡ 316·105309+4 ≡ (316 )105309 · 34 (mod 16)

Pelo teorema de Fermat, 316 ≡ 1 (mod 17), logo

31684948 ≡ 34 ≡ 81 ≡ 13 (mod 17).

5.2 Contando Raı́zes

O teorema de Fermat diz que
ap−1 ≡ 1 (mod p)

quando p é primo e p 6 |a. Será que é possı́vel encontrar um expoente k menor do que p − 1 de
modo que ak ≡ 1 (mod p) para todo inteiro a não divisı́vel por p?
O Teorema Fundamental da Álgebra nos diz que todo polinômio de grau n,

p = X n + an−1 X n−1 + · · · + a1 X + a0

pode ser fatorado como produto de exatamente n fatores

p = (X − α1 )(X − α2 ) · · · (X − αn−1 )(X − αn )

onde α1 , α2 , ..., αn são números complexos. Os coeficientes a0 , a1 , ..., an−1 também são complexos.
Como consequência de tudo isso, temos que a equação f (x) = 0 possui exatamente n raı́zes
(distintas ou não) em C, que são exatamente os complexos α1 , ..., αn .
Se restringirmos os coeficientes a0 , a1 , ..., an−1 ao conjunto dos inteiros Z, o teorema continua
valendo, pois Z ⊂ C. Se perguntarmos sobre a quantidade de raı́zes da equação f (x) = 0 que
pertençam a Z, é claro que podemos afirmar que estas são, no máximo, n raı́zes (distintas ou não),
e o motivo é novamente o fato de Z ser subconjunto de C.
Sendo assim, um corolário do Teorema Fundamental da Álgebra que podemos enunciar é: um
polinomio de grau k com coeficientes inteiros e coeficiente lı́der 1 tem no máximo k raı́zes distintas
em Z.
Para respondermos à pergunta que iniciamos a seção, precisarı́amos de algo análogo, mas
enuciado para Zp .

Um polinômio de grau k com coeficientes inteiros e

coeficiente lı́der 1 tem no máximo k raı́zes distintas em Zp .

Se de fato tal resultado for válido em Zp , poderı́amos argumentar da seguinte maneira: se

a ≡ 1 (mod p) para todo a, 1 ≤ a ≤ p − 1, então o polinômio X k − 1 tem p − 1 raı́zes distintas
k

54
Contando Raı́zes Seção 5.2

em Zp . Como X k − 1 tem no máximo k raı́zes em Zp e o número de raı́zes é menor que ou igual

a k, temos que
1 − p ≤ k.

Portanto a resposta à nossa pergunta é não se o resultado citado valer em Zp . Vamos demonstrar
a validade do resultado quando p é primo, e dar um exemplo de que é falso quando p é composto.
Vamos primeiro dar o exemplo para p composto. Em Z385 , o polinômio X 2 − 170 possui como
raı́zes 95, 150, 235, 290, pois

952 − 170 ≡ 8855 ≡ 385 · 23 ≡ 0 (mod 385)

1502 − 170 ≡ 22330 ≡ 385 · 58 ≡ 0 (mod 385)
2352 − 170 ≡ 55055 ≡ 385 · 143 ≡ 0 (mod 385)
2902 − 170 ≡ 83930 ≡ 385 · 218 ≡ 0 (mod 385)

logo temos uma equação com grau 2, e que possui (no mı́nimo) 4 raı́zes em Z385 . Portanto,
quando n é composto não podemos garantir que um polinômio de grau k, com coeficientes inteiros
e coeficiente lı́der 1, tem no máximo k raı́zes.
A seguir veremos que, para p primo, o resultado de que necessitamos é válido, mas antes de
demonstrarmos este teorema, vamos demonstrar um lema que será útil.

LEMA Seja h um polinômio com coeficientes inteiros de grau m. Dado um inteiro α, existe
5.2.1.

um polinômio q de grau m − 1 tal que

h = (X − α) · q + h(α) (5.2)

sendo h(α) o valor da função polinomial associada a h, evaluada em α.

DEMONSTRAÇÃO. Vamos demonstrar usando o segundo princı́pio de indução finita sobre o grau
m do polinômio h.
Se m = 1, então h = aX + b para certo inteiros a e b. Daı́,

h = aX + b = aX + b + aα − aα = a(X − α) + aα + b = a(X − α) + h(α)

Neste caso, tomamos q = a.

Agora, suponhamos que o resultado vale para qualquer polinômio com coeficientes inteiros de
grau ≤ m − 1. Queremos mostrar que o resultado vale também para um polinômio h de grau m.
Seja
h = am X m + am−1 X m−1 + · · · + a1 X + a0

Defina
g = h − am X m−1 (X − α)

55
Capı́tulo 5 Fermat e Primalidade

ou seja

g = a0 + a1 X + · · · + am−1 X m−1 + am X m − am X m + am X m−1 α

= (am−1 + am α)X m−1 + am−2 X m−2 + · · · + a1 X + a0

Sendo assim, g tem grau ≤ m−1. Pela hipótese de indução, existe um polinômio j com coeficientes
inteiros e grau ≤ m − 2 tal que
g = j · (X − α) + g(α)

Mas g(α) = h(α), logo g = j · (X − α) + h(α). Da definição de g temos

h = g + am X m−1 (X − α)

Portanto

h = j · (X − α) + h(α) + am X m−1 (X − α)
= (j + am X m−1 )(X − α) + h(α)

Como j tem grau ≤ m − 2, segue que (j − am X m−1 ) tem grau m − 1, provando assim o lema.

Agora estamos em condições de demonstrar o teorema seguinte.

TEOREMA 5.2.2. Seja f um polinômio de grau k com coeficientes inteiros e coeficiente lı́der 1.
Se p é um número primo, então f tem no máximo k raı́zes distintas em Zp .

Obs: se f = a0 +a1 X +· · ·+an X n ∈ Z[X], identificamos f com f = a0 +a1 X +· · ·+an X n ∈ Zp [X].

DEMONSTRAÇÃO. Novamente vamos usar indução sobre o grau do polinômio f .
Se n = 1, temos que f = X + b, para algum inteiro b, e a única raiz possı́vel em Zp é −b.
Portanto, um polinômio de grau 1 tem exatamente uma raiz em Zp .

x + b = 0 ⇒ x = −b

Suponha agora que todo polinômio de grau k − 1, com coeficientes inteiros e coeficiente lı́der
1, tenha no máximo k − 1 raı́zes distintas em Zp . Seja f um polinômio de grau k com coeficientes
inteiros e coeficiente lı́der 1. Se f não tem raiz em Zp , o teorema está demonstrado. Suponhamos
então que α é uma raiz de f em Zp , ou seja, f (α) ≡ 0 (mod p)
Pelo lema anterior,
f = (X − α)q + f (α)

56
Contando Raı́zes Seção 5.2

e o grau de q é k − 1. Reduzindo esta equação a módulo p, obtemos

f ≡ (X − α)q (mod p) (5.3)

Seja β uma raiz de f em Zp , diferente de α.

f (β) ≡ 0 (mod p) mas α − β 6= 0

Fazendo x = β em (5.3), chegamos à

0 ≡ f (β) ≡ (β − α)q(β) (mod p)

Como β − α 6≡ 0 (mod p), e p é primo, então β − α possui inverso em Zp , portanto

q(β) · (β − α) ≡ 0 (mod p) ⇒ q(β) ≡ 0 (mod p)

Logo, se β é um raiz de f distinta de α, necessariamente β também é raiz de q em Zp , ou seja,

f só pode ter uma raiz em Zp a mais do que aquelas que também são raı́zes de q em Zp . Pela
hipótese de indução, q tem no máximo k − 1 raı́zes distintas em Zp . Portanto, f tem no máximo
k raı́zes distintas em Zp .

Portanto a resposta à questão inicial da seção é: se p é primo e a é um inteiro qualquer, o

menor inteiro k tal que ak ≡ 1 (mod p) é k = p − 1.

Devemos destacar algo sutil nesta última demonstração: primeiramente, a hipótese de p ser
primo foi fundamental para concluirmos que q(β) ≡ 0 (mod p). Mas há algo muito mais tênue,
que quase passa despercebido: a hipótese de comutatividade. Discorramos um pouco sobre isso.

Podemos definir polinômio da seguinte maneira: um polinômio p sobre um anel (A, +, ·) com
unidade 1A é uma sequência quase nula, isto é, uma sequência (a0 , a1 , a2 , · · · , an , 0, 0, 0, ...), onde
cada entrada ai ∈ A, e a partir de um certo ı́ndice n todos os termos da sequência são iguais ao
elemento neutro (1) da adição de A. Podemos definir o conjunto dos polinômios sobre o anel A
por A[X].

A[X] = {(a0 , a1 , a2 , · · · , aj , ...)| aj ∈ A ∀j ∈ N e ∃n ∈ N tal que ai = 0 ∀i > n}

Definido o conjunto A[X], podemos definir operações em A[X] da seguinte maneira: Sejam
p = (a0 , a1 , a2 , · · · , an , 0, 0, 0, ...) e q = (b0 , b1 , b2 , · · · , bm , 0, 0, 0, ...) dois polinômios de A[X], k ∈ A

1
Denotaremos esse elemento simplesmente por 0. Em livros a notação 0A também é usada.

57
Capı́tulo 5 Fermat e Primalidade

e suponha m ≤ n. Definimos

.
p + q = (a0 + b0 , a1 + b1 , a2 + b2 , · · · , an + bn , 0, 0, 0, ...)
.
k · p = (ka0 , ka1 , ka2 , · · · , kan , 0, 0, 0, ...)
.
p · q = (c0 , c1 , c2 , · · · , cn+m , 0, 0, 0, ...)
Pk
onde ck = a0 bk + a1 bk−1 + a2 bk−2 + a3 bk−3 + · · · + ak−1 b1 + ak b0 = i=0 ai bk−i .
Observamos que a notação usada para o produto de um elemento de A por um elemento
de A[X] é a mesma empregada para o produto de dois elementos de A[X]. Isso não acarreta
ambiguidade, uma vez que sua distinção é notada facilmente pelo contexto, além do mais essa
prática é utilizada na grande maioria dos textos que abordam esse assunto.
As propriedades que as operações + e · (produto de polinômios) possuem dependem direta-
mente das propriedades das operações + e · do anel A.
Denotamos por:
1 = 1A[X] = (1A , 0, 0, ...) e X = (0, 1A , 0, 0, ...)

Obsevamos que 1A[X] é a unidade de A[X] e

X 2 = X · X = (0, 0, 1A , 0, 0, 0, ...)

X 3 = X 2 · X = (0, 0, 0, 1A , 0, 0, ...)

e em geral
X n = X n−1 · X = (a0 , a1 , a2 , ..., aj , ...)

sendo que ai = 0 ∀i 6= n e an = 1A . Desta forma, todo polinômio p ∈ A[X] pode ser escrito na
forma
p = (a0 , a1 , ..., an , 0, 0, 0, ...) = a0 + a1 X + · · · + an X n

A cada polinômio p = (a0 , a1 , a2 , · · · , an , 0, 0, ...) ∈ A[X] podemos associar a função polinomial

p : A −→ A, definida por p(x) = a0 + a1 x + a2 x2 + · · · + an xn .
Mas o que tudo isso tem haver com a demonstração anterior?
Na equação (5.3), temos uma igualdade de polinômios. No caso, estamos trabalhando com
Z[X]. Os polinômios envolvidos são f , X − α e q. Logo na sequência, avaliamos a função
polinomial f (x) no ponto β. O que se passa no lado direito dessa equação? A rigor, deveriamos
primeiramente multiplicar os polinômios X − α e q para depois avaliarmos a função polinomial
resultante em β, mas o que fazemos é avaliar as funções polinomiais x − α e q(x) cada uma
separadamente e depois multiplicar os resultados. Quem garante que o resultado é o mesmo? A
comutatividade do anel sobre o qual definimos nossos polinômios e nossas funções polinômiais. Se
o anel não for comutativo, isso pode não ser verdade.

58
Contando Raı́zes Seção 5.2

Vejamos o que acontece, por exemplo, quando definimos o conjunto dos polinômios sobre o anel
M (2, R) das matrizes quadradas 2 × 2 de números reais. Sabemos que esse anel não é comutativo.
Sejam p = A + BX + CX 2 e q = D + EX + F X 2 elementos de M (2, R)[X]. Para sabermos
qual é a função polinomial (p · q)(x), devemos multiplicar os polinômios p e q segundo as operações
que definimos em M (2, R)[X]. Sendo assim temos

p = (A, B, C, 0, 0, 0, ...)

q = (D, E, F, 0, 0, 0, ...)

logo
p · q = (AD, AE + BD, AF + BE + CD, BF + CE, CF, 0, 0, ...).

Daı́, (p · q)(x) = AD + (AE + BD)x + (AF + BE + CD)x2 + (BF + CE)x3 + CF x4

Sejam, por exemplo, as matrizes A, B, C, D, E e F dadas por:
! ! !
7 9 5 4 1 0
A= B= C=
1 5 0 9 0 9
! ! !
1 0 7 5 4 2
D= E= F =
1 1 0 8 2 3

!
1 2
Agora, vamos avaliar p(x), q(x) e (p · q)(x) em α = . Neste caso, temos
−3 −4

!! ! ! ! ! !2 !
1 2 7 9 5 4 1 2 1 0 1 2 −5 −3
p = + + =
−3 −4 1 5 0 9 −3 −4 0 9 −3 −4 55 59

!! ! ! ! ! !2 !
1 2 1 0 7 5 1 2 4 2 1 2 −9 −10
q = + + =
−3 −4 1 1 0 8 −3 −4 2 3 −3 −4 −6 −13

!! !! !
1 2 1 2 63 89
Portanto temos p ·q = , enquanto que
−3 −4 −3 −4 −849 −1317

!! ! ! " ! ! ! !# !
1 2 7 9 1 0 7 9 7 5 5 4 1 0 1 2
(p · q) = + + +
−3 −4 1 5 1 1 1 5 0 8 0 9 1 1 −3 −4
" ! ! ! ! ! !# !2
7 9 4 2 5 4 7 5 1 0 1 0 1 2
+ + + +
1 5 2 3 0 9 0 8 0 9 1 1 −3 −4
" ! ! ! !# !3
5 4 4 2 1 0 7 5 1 2
+ + +
0 9 2 3 0 9 0 8 −3 −4
! ! !4
1 0 4 2 1 2
+
0 9 2 3 −3 −4
!
75 37
=
−525 −561

59
Capı́tulo 5 Fermat e Primalidade

Portanto, em M (2, R)[X] nem sempre é verdade que p(α) · q(α) = (p · q)(α). Felizmente, no
caso do teorema que demonstramos, como Z é comutativo, é verdade que p(α) · q(α) = (p · q)(α)
para quaisquer polinômios p, q e qualquer inteiro α.

5.3 Pseudoprimos
O teorema de Fermat nos deu uma importante relação entre números inteiros e primos. É natural
a busca por testes de primalidade usando este resultado. O que veremos nesta seção são testes
que foram descobertos usando-se o teorema de Fermat, direta ou indiretamente. Como veremos,
nenhum deles é o que se estava procurando, pois não revelam se o é número primo, apenas detectam
se ele é composto. Mas isso, de certa forma, já é um avanço.
O teorema de Fermat diz que se p é primo e a é um inteiro, então

ap ≡ a (mod p)

Considere um inteiro n ı́mpar. Queremos saber se n é composto ou primo. Se encontrarmos

em inteiro b tal que
bn 6≡ b (mod n)

o que podemos concluir? Se n fosse primo, terı́amos bn ≡ b (mod n), portanto n é obrigatoria-
mente composto.
Conseguimos um teste que nos diz que um número n é composto sem encontrarmos nenhum
fator de n. Mas onde procurar o inteiro b? Segundo o teorema de Fermat, b pode ser qual-
quer inteiro. Mas podemos restringir nossa busca a inteiros satisfazendo 1 < b < n − 1, pois
0n ≡ 0 (mod n), 1n ≡ 1 (mod n) e (n − 1)n ≡ n − 1 (mod n). As duas primeiras congruências
são óbvias. Para justificar a terceira congruência, observe que n − 1 ≡ −1 (mod n). Como n é
ı́mpar, temos
(n − 1)n ≡ (−1)n ≡ −1 ≡ n − 1 (mod n)

Além disso, não precisamos procurar inteiros b ≥ n, pois qualquer inteiro maior do que n é côngruo
a algum outro inteiro no itervalo 0 ≤ b ≤ n − 1.
Portanto, se queremos encontrar um inteiro b de modo que

bn 6≡ b (mod n)

basta testarmos inteiros no intervalo 1 < b < n − 1.

Como vamos testar inteiros entre 1 e n − 1, qualquer inteiro nesse intervalo não é divisı́vel por
n, portanto podemos usar a segunda versão do teorema de Fermat.
TESTE 5.3.1. Se n > 0 e 1 < b < n − 1 são números inteiros e bn−1 6≡ 1 (mod n) então n é um

60
Pseudoprimos Seção 5.4

número composto. O número b é conhecido como uma testemunha do fato de n ser composto.

Conseguimos um teste para dizer se n é composto. Mas gostarı́amos de algo para afirmar se n
é primo. Alguém poderia dizer: se um número n ı́mpar satisfaz bn−1 ≡ 1 (mod n) para algum b,
1 < b < n − 1, então n é primo.
Infelizmente, tal teste é falso. O teorema de Fermat vale para qualquer inteiro b, logo a validade
da equação do teorema para um b particular não garante a primalidade de n. Mesmo assim, Leibniz
usava isso como teste de primalidade, tomando b = 2 para “facilitar” os cálculos. Por exemplo

2340 ≡ 29·37+7 ≡ (29 )3 7 · 27 ≡ 17136 · 171 · 27

≡ 25618 · 64 ≡ (2562 )9 · 64 ≡ 649 · 64
≡ (642 )5 ≡ 45 ≡ 1024 ≡ 1 (mod 341)

e pelo teste que Leibniz usava, 341 seria primo, mas

341 = 11 · 31.

Deste raciocı́nio tiramos a seguinte definição.

DEFINIÇÃO 5.3.2. Um inteiro n, ı́mpar e composto, é um pseudoprimo para a base b,

1 < b < n − 1, se bn−1 ≡ 1 (mod n).

Segundo essa definição, 341 é um pseudoprimo para a base 2.

Apesar do teste falhar em alguns casos, como para 341 na base 2, ele é muito útil. Para números
pequenos, a margem de acerto é grande. Por exemplo, entre 1 e 109 existem 50.847.534 primos,
e apenas 5.597 pseudoprimos para base 2. Se testarmos outras bases, aumentamos a eficiência do
teste. Por exemplo

3340 ≡ 36·56+4 ≡ (36 )5 6 · 34 ≡ 4756 · 34

≡ (472 )28 · 34 ≡ (1632 )14 · 34 ≡ (3122 )7 · 34
≡ (1592 )3 · 159 · 34 ≡ 473 · 262 ≡ 56 (mod 341)

logo 3 é uma testemunha de que 341 é composto. Entre 1 e 109 existem apenas 1272 pseudoprimos
para as bases 2 e 3.
Poderı́amos pensar em testar todas as bases de 1 à n − 1, mas se n é grande isto é impraticável,
mas essa discussão nos leva a questões interessantes.

61
Capı́tulo 5 Fermat e Primalidade

5.4 Números de Carmichael

Primeiramente observamos que nenhum número composto n pode ser pseudoprimo para todas as
bases 1 < b < n − 1. De fato, se n é composto, então tem um fator b, logo

mdc(b, n) 6= 1 ⇒ mdc(bn−1 , n) 6= 1.

Se bn−1 ≡ 1 (mod n), terı́amos que n|(bn−1 − 1), ou seja, bn−1 − 1 = nr ⇔ bn−1 − nr = 1. Mas
isto nos permitiria concluir que mdc(bn−1 , n) = 1, absurdo. Portanto bn−1 6≡ 1 (mod n), ou seja,
n não é um pseudoprimo para a base b, ou seja, provamos que:

n composto ⇒ ∃b de modo que bn−1 6≡ 1 (mod n).

Equivalentemente temos:

TEOREMA 5.4.1. Seja n um número inteiro. Se bn−1 ≡ 1 (mod n) para todo 1 < b < n − 1,
então n é primo.

Esse é um teste de primalidade que nos dá certeza de que n é primo, mas é impraticável devido
à quantidade de bases que deverı́amos testar.
O que devemos destacar é que só podemos dizer que n é primo se usarmos a equação da segunda
versão do teorema de Fermat. Se bn ≡ b (mod n) para qualquer b, não podemos afirmar que n
é primo, pois existem números compostos que satisfazem bn ≡ b (mod n) para todo b entre 1 e
n − 1. São os chamados números de Carmichael.

DEFINIÇÃO 5.4.2. Um número composto ı́mpar n > 0 é um número de Carmichael se

bn ≡ b (mod n) para todo b, 1 < b < n − 1.

É dificil acreditarmos na existência de tais números antes de ver um. Sendo assim, vejamos
um exemplo.
Afirmamos que 561 é um número de Carmichael. Precisamos mostrar que b561 ≡ b (mod 561)
para b = 2, 3, 4, · · · , 559, um total de 558 bases. Não parece ser um bom caminho.
Primeiramente, observe que 561 é composto (qualquer número primo p satisfaz bp ≡ p (mod p),
mas p não é um número de Carmichael).

561 = 3 · 11 · 17

Agora, considere b um inteiro entre 2 e 559. Se mostrarmos que b561 − b é divisı́vel por 3, por 11 e
por 17, como estes são primos distintos, segue da segunda parte da proposição 2.1.3 que o produto
destes primos divide b561 − b. Mas este produto é 561, e dizer que 561 divide b561 − b é equivalente
a
b561 ≡ b (mod 561).

62
Números de Carmichael Seção 5.4

Comecemos pelo fator 3

(1) Se 3 divide b, seque imediatamente que 3 divide b561 − b. Agora, se 3 não divide b, segue
do teorema de Fermat que b3−1 ≡ 1 (mod 3). Daı́

b561 ≡ b2·280+1 ≡ (b2 )280 · b ≡ b (mod 3)

onde a última congruência segue do teorema de Fermat. Portanto b561 − b é divisı́vel por 3.
(2) Se 11 divide b, seque imediatamente que 11 divide b561 − b. Agora, se 11 não divide b, segue
do teorema de Fermat que b11−1 ≡ 1 (mod 11). Daı́

b561 ≡ b10·56+1 ≡ (b10 )56 · b ≡ b (mod 11)

onde a última congruência segue do teorema de Fermat. Portanto b561 − b é divisı́vel por 11.
(3) Se 17 divide b, seque imediatamente que 17 divide b561 − b. Agora, se 17 não divide b, segue
do teorema de Fermat que b17−1 ≡ 1 (mod 17). Daı́

b561 ≡ b16·35+1 ≡ (b16 )35 · b ≡ b (mod 17)

onde a última congruência segue do teorema de Fermat. Portanto b561 − b é divisı́vel por 17.
Se b561 − b é divisı́vel por 3, 11 e 17, e estes são primos entre sı́, temos que b561 − b é divisı́vel
por 3 · 11 · 17 = 561, ou seja
b561 ≡ b (mod 561).

Como b é qualquer inteiro entre 2 e 559, segue que 561 é um número de Carmichael.
Tivemos um pouco de “sorte”. Como usamos o teorema de Fermat, tivemos que dividir 561
por p − 1, para p = 3, 11, 17. Felizmente, todas estas divisões tiveram resto igual a 1, o que nos
permitiu concluir o raciocı́nio facilmente. Além disso, os fatores primos de 561 apareceram apenas
uma vez em sua decomposição, o que nos permitiu utilizar a proposição 2.1.3.
Mas será que sempre teremos tanta sorte ao tentarmos provar que um número é de Carmichael?
Na verdade, as propriedades destacadas no paragrafo anterior não são exclusivas ou acidentais para
561. Elas constituem uma caracterização do números de Carmichael.

TEOREMA 5.4.3 (Teorema de Korselt). Um inteiro positivo composto ı́mpar n é um número de

Carmichael se, e somente se, cada fator primo p de n satisfaz as duas condições seguintes:
(1) p2 não divide n;
(2) p − 1 divide n − 1.

Para mostrarmos que se um número satisfaz (1) e (2) então ele é um número de Carmichael,
usaremos apenas conceitos que já foram discutidos. Da mesma forma, para mostrar que um
número de Carmichael satisfaz (1), também usaremos apenas ideias já apresentadas até aqui.

63
Capı́tulo 5 Fermat e Primalidade

Entretanto, para mostrar que qualquer número de Carmichael satisfaz (2), precisamos do auxı́lio
da teoria dos grupos, que estudaremos num capı́tulo posterior. Por hora, apenas enunciaremos
definições e resultados necessários, sem demonstrá-los aqui. As justificativas destes resultados
virão em momento oportuno.

• Teorema da Raiz Primitiva: Se p é primo, então (U (p), ·) é um grupo cı́clico, ou seja, é

gerado por um único elemento.

• Dado um grupo (G, ·), a ordem de a ∈ G é o menor inteiro positivo k tal que ak = e, onde
e é o elemento neutro do grupo G. Se ak =
6 e para qualquer inteiro k, dizemos que a tem
ordem infinita.

• A ordem de um grupo cı́clico finito (G, ·) gerado por a é igual a ordem do seu gerador a.

• Lema Chave: Sejam G um grupo e a ∈ G. Um inteiro positivo t satisfaz at = e se, e somente,

se, t é divisı́vel pela ordem de a.

Vamos à demonstração do teorema.

DEMONSTRAÇÃO. (Teorema de Korselt) Primeiramente, vamos ver que se n é um número que
satisfaz (1) e (2), então n é um número de Carmichael.
Seja p um fator primo de n. Vamos mostrar que para qualquer b ∈ Z tem-se

bn ≡ b (mod p)

Se b for divisı́vel por p, então a congruência é imediatamente verificada. Se b não for divisı́vel
por p, o teorema de Fermat nos diz que

bp−1 ≡ 1 (mod p)

Para usarmos isso, precisamos dividir n por p − 1. Mas a condição (2) nos diz que p − 1 divide
n − 1, ou seja, existe q tal que

n − 1 = (p − 1)q ⇒ n = (p − 1)q + 1

Daı́,
bn ≡ b(p−1)q+1 ≡ (bp−1 )q · b ≡ b (mod p)

Portanto se p é um fator primo de n então bn ≡ b (mod p) para qualquer inteiro b.

Voltando às hipóteses do teorema, de (1) temos que n = p1 p2 ...pk onde p1 < p2 < · · · < pk
são primos distintos, já que p2i não é fator de n, i = 1, 2, .., k. Sendo primos distintos, segue da

64
Números de Carmichael Seção 5.4

proposição 2.1.3 que bn − b é divisı́vel pelo produto p1 p2 ...pk = n, ou seja,

bn ≡ b (mod n)

para qualquer b. Logo n é um número de Carmichael.

Mostramos que se n satisfaz (1) e (2) então n é um número de Carmichael. Vamos provar a
recı́proca.
Primeiramente, queremos verificar que se n é um número de Carmichael, então a condição (1)
é satisfeita. É mais fácil (e equivalente) provarmos a contrapositiva disto: se existe um primo p,
fator de n, tal que p2 divide n, então n não pode ser um número de Carmichael.
Para que n não seja um número de Carmichael, precisamos encontrar um inteiro b tal que

bn 6≡ b (mod n)

Escolha b = p. Temos que

pn − p = p(pn−1 − 1)

Como p não divide pn−1 − 1, p2 não pode dividir pn − p. Se n dividisse pn − p, como estamos
supondo que p2 |n, teriamos que p2 |pn − p, o que já vimos que é impossı́vel. Portanto n 6 |pn − p,
ou seja,
pn 6≡ p (mod n)

e n não é um número de Carmichael.

Finalmente, mostremos que um número de Carmichael satisfaz (2). Seja n um número de
Carmichael, ou seja, bn ≡ b (mod n) para todo b, 1 < b < n − 1. Seja p um fator primo de n.
Queremos mostrar que p − 1 divide n − 1.
Como p é primo, pelo teorema da raiz primitiva temos que U (p) é cı́clico, e portanto possui
um gerador a.
Temos que an − a é divisı́vel por n, já que n é um número de Carmichael. Sendo assim, temos
que
p|n e n|an − a ⇒ p|an − a
ou seja,
an ≡ a (mod p).

Como a ∈ U (p), a é inversı́vel módulo p, e então a equação acima fica

an−1 ≡ 1 (mod p)

Pelo lema chave, n − 1 é divisı́vel pela ordem de a. Mas a é um gerador de U (p), cuja ordem é
p − 1, logo a ordem de a é p − 1, e concluı́mos que p − 1 divide n − 1.

65
Capı́tulo 5 Fermat e Primalidade

Vimos que o teorema de Fermat nos fornece um teste que verifica com certa eficiência se um
número é composto, mas que já não é tão eficiente se nosso desejo é verificar a primalidade de um
número n, prova disso é a existência dos números de Carmichael, que caracterizamos anteriormente.
Acrescentamos aqui uma informação: já demonstrou-se que os números de Carmichael são infinitos,
e a certeza dessa afirmação é relativamente recente, um artigo de 1994. (informações em [01]).
Neste mesmo artigo é apresentado um resultado de grande importância no que se refere a testes de
primalidade usados por computação algébrica. Discutiremos rapidamente a ideia desse resultado,
que se trata de uma modificação do teste que estudamos anteriormente.

O novo teste, o teste de Miller, inicia-se observando que se o inteiro positivo n > 2 é ı́mpar
(pois se n é par já sabemos que é composto) então n − 1 é par, logo podemos escrever

n − 1 = 2k q

onde q é um inteiro ı́mpar e k ≥ 1. Seja b um inteiro, 1 < b < n − 1. O teste consiste em calcular
as seguintes potências módulo n:

2 3 k−1 q kq
bq , b2q , b2 q , b2 q, ..., b2 , b2

Se n for um número primo, ao menos uma dessas potências será congruente a 1 módulo n, pois
pelo teorema de Fermat
k
b2 q ≡ bn−1 ≡ 1 (mod n)

j
Sendo assim, seja j o menor expoente tal que b2 q ≡ 1 (mod n). Temos duas possibilidades:
j
ou j = 0 ou j ≥ 1. Se j ≥ 1, podemos usar diferença de quadrados para fatorar b2 q − 1.

j j−1 q j−1 q
b2 q − 1 = (b2 − 1)(b2 + 1)

j j−1 j−1
Estamos supondo n primo e divisor de b2 q −1. Logo, n divide b2 q −1 ou n divide b2 q +1. Mas
j j−1
j é o menor expoente tal que b2 q − 1 é divisı́vel por n, portanto b2 q − 1 não pode ser divisı́vel
j−1
por n, e portanto n obrigatoriamente divide b2 q + 1, ou seja

j−1 q
b2 ≡ −1 (mod n)

Resumindo, se n é primo, então uma das potências da sequência

2 3 k−1 q
bq , b2q , b2 q , b2 q, ..., b2

66
Números de Carmichael Seção 5.4

é congruente a −1 módulo n. Mas isso só acontece se j ≥ 1, para podermos usar o produto notável
como fizemos. No caso em que j = 0 temos

bq ≡ 1 (mod n)

Portanto, se n é primo, então uma das potências da sequência é congruente −1 ou

bq ≡ 1 (mod n). Se nada disso acontecer, então n é composto.
Temos, assim, um novo teste que detecta números compostos. A vantagem que obtemos é que
mesmo entre os pseudoprimos esse novo teste é eficiente.
Para encerrar, vejamos exemplos. Como já vimos, 341 é um pseudoprimo para a base 2. O
que o teste de Miller nos diz a respeito do 341? Nesse caso temos n − 1 = 340 = 22 · 85, e portanto
q = 85. As potências que devemos calcular módulo 341 são 285 e 2170 .

285 ≡ 32 (mod 341)

2170 ≡ 322 ≡ 1 (mod 341)

Portanto 341 é composto pelo teste de Miller, pois 2q = 85 não é côngruo a 1 módulo 341 e
nenhuma das outras potências (que nesse caso é só mais uma) é congruente a −1 módulo 341.
O raciocı́nio que desenvolvemos nos permite apenas detectar se um número inteiro é composto.
j
Se ao aplicarmos o teste de Miller e encontrarmos bq ≡ 1 (mod n) ou b2 q ≡ −1 (mod n),
0 < j < k, não podemos concluir nada a respeito do inteiro n. Neste caso, dizemos que o teste é
inconclusivo. Por exemplo, apliquemos o teste para o inteiro 25 usando base 7. Como 25−1 = 23 ·3,
2
as potências que devemos testar são 73 , 72·3 e 72 ·3 .
2
potências 73 72·3 72 ·3
restos 18 24 1

Como 72·3 ≡ 24 ≡ −1 (mod 25), o teste de Miller é inclonclusivo para 25. Neste caso dizemos
que 25 é um pseudoprimo forte para a base 7.
É facil verificar que se um inteiro n é um pseudoprimo forte para uma base b, então n é um
pseudoprimo para a base b: sejam k e q inteiros, q ı́mpar, tais que n − 1 = 2k q. Se n é um
pseudoprimo forte para uma base b temos que

j
bq ≡ 1 (mod n) ou b2 q ≡ −1 (mod n) para algum j , 0 < j ≤ n − 1

k k k
No primeiro caso, bn−1 ≡ b2 q ≡ (bq )2 ≡ (1)2 ≡ 1 (mod n). No segundo caso,
j j+(n−j) q j n−j j n−j n−j
bn−1 ≡ b2 q ≡ b2 ≡ b2 ·2 q ≡ (b2 q )2 ≡ (−1)2 ≡ 1 (mod n). Em ambos os casos
temos que n é um pseudoprimo para a base b.

67
Capı́tulo 5 Fermat e Primalidade

68
Capı́tulo

6
Sistemas de Congruências

Neste capı́tulo veremos como resolver um sistema de congruências, utilizando o Teorema Chinês
do Resto, e encerraremos com uma aplicação deste resultado com um método de criptografia para
partilhar senhas.

6.1 Equações Lineares

Uma equação de congruência linear a uma incógnita é uma sentença do tipo

ax ≡ b (mod n)

Para resolver esta equação, devemos analisar duas possibilidades:

• a ∈ U (n)

• a∈
/ U (n)

Quando a ∈ U (n), sendo α = a−1 em Zn , temos

ax ≡ b (mod n) ⇒ x ≡ αb (mod n)

Se n é primo e a 6≡ 0 (mod n), a equação ax ≡ b (mod n) sempre tem uma única solução em
Zn . Estudemos, então, o caso em que a não é inversı́vel em Zn . Neste caso estamos considerando
n composto.
ax ≡ b (mod n) (6.1)

Dizer que a não é inversı́vel em Zn equivale dizer que mdc(a, n) 6= 1. Se a equação (6.1) possui
solução, significa que b − ax é divisı́vel por n para algum inteiro x, ou seja, existem inteiros x e y
tais que
ax − b = ny ⇔ ax − ny = b (6.2)

69
Capı́tulo 6 Sistemas de Congruências

ou seja, a equação diofantina linear em x e y

ax − ny = b

possui solução. Mas isto só é possı́vel se mdc(a, n) dividir b. Suponhamos que d = mdc(a, n)
divida b.
Sendo d um divisor de a, temos que a = d · a0 para algum inteiro a0 . Analogamente, b = d · b0
e n = d · n0 , para certos inteiros b0 e n0 . Substituindo isso em (6.2)

ax − ny = b ⇒ d · a0 x − d · n0 y = d · b0 ⇒ a0 x − n0 y = b0

Esta última equação é equivalente à seguinte congruência:

a0 x ≡ b0 (mod n0 )

Chegamos, portanto, a uma nova equação congruência módulo n0 , um divisor de n. Note que
mdc(a0 , n0 ) = 1, pois

aα + nβ = d ⇒ a0 dα + n0 dβ = d ⇒ a0 α + n0 β = 1

o que nos leva a concluir que esta nova congruência sempre tem solução. Parece que simplificamos
o problema, mas é preciso ter mais cautela. Vejamos um exemplo.
Considere a congruência 6x ≡ 4 (mod 8). Como mdc(6, 8) = 2 6= 1, 6 não possui inverso em
Z8 ; entretanto, podemos substituir a congruência original por outra equivalente.

6x ≡ 4 (mod 8) ⇔ 6x − 4 = 8y ⇔ 3x − 2 = 4y ⇔ 3x ≡ 2 (mod 4)

Em Z4 , 3 é seu próprio inverso, portanto

3x ≡ 2 (mod 4) ⇒ x ≡ 3 · 2 ≡ 6 ≡ 2 (mod 4) (6.3)

Não há nada de errado com o que fizemos até aqui. Como vimos anteriormente, a nova
congruência admite solução. Entretanto estávamos interessados em soluções de uma equação
módulo 8, e acabamos com uma solução de uma equação módulo 4. O que fazer, então? Basta
transformar (6.3) em uma expressão entre inteiros, ou seja, sem congruências, e analisar como
estas soluções se comportam módulo 8.

x ≡ 2 (mod 4) ⇔ x = 2 + 4k

onde k é um inteiro qualquer. Temos dois casos a considerar:

70
Equações Lineares Seção 6.1

i) k par. Neste caso, temos k = 2m, para algum inteiro m. Daı́,

x = 2 + 8m ⇔ x ≡ 2 (mod 8)

Portanto x = 2 é uma solução para 6x ≡ 4 (mod 8).

ii) k ı́mpar. Neste caso, escrevemos k = 2m + 1, e chegamos à x = 6 + 8m. Portanto

x ≡ 6 (mod 8) é outra solução de 6x ≡ 4 (mod 8).

Portanto a congruência 6x ≡ 4 (mod 8) possui duas soluções em Z8 . Note que a equação é

linear, mas possui duas soluções. Como vimos no capı́tulo anterior, uma equação de grau k possui
no máximo k soluções distintas se a congruência é módulo um primo; também destacamos que
isto pode não acontecer quando a congruência é módulo um composto, como neste exemplo.
Vejamos como resolver um sistema de congruências. Para isso, resolveremos um problema cuja
solução passa pela resolução de um sistema de congruência.

Três satélites passarão sobre uma certa cidade esta noite. O primeiro satélite
passará à 1h, o segundo às 4h, e o terceiro às 8h. Os perı́odos respectivos são de
13, 15 e 19 horas. Determine quantas horas decorrerão, a partir da meia-noite,
até que os três satélites passem juntos sobre a cidade.

Seja x o número de horas, contadas a partir da meia noite, quando os três satélites passarão
juntos sobre a cidade. O primeiro satélite passa a cada 13 horas a partir da 1h da madrugada.
Portanto, precisamos ter x = 13t + 1, para algum t positivo. Essa equação equivale à:

x ≡ 1 (mod 13)

Correspondentes aos outros dois satélites, temos as seguintes equações.

x ≡ 4 (mod 15)

x ≡ 8 (mod 19)

Os três satélites passarão juntos sobre a cidade para valores de x que satisfaçam as três equações
simultaneamente. Portanto, precisamos resolver o seguinte sistema.

 x ≡ 1 (mod 13)

x ≡ 4 (mod 15)

x ≡ 8 (mod 19)


As três equações possuem módulos diferentes, logo não podemos somá-las ou subtraı́-las entre
sı́. Transformaremos, como anteriormente, estas equações de congruências em relações entre in-

71
Capı́tulo 6 Sistemas de Congruências

teiros. x ≡ 1 (mod 13) equivale à x = 1+13t. Mas x é um inteiro, e portanto podemos subtituı́-lo
na segunda equação.

x ≡ 4 (mod 15) ⇒ 1 + 13t ≡ 4 (mod 15) ⇒ 13t ≡ 3 (mod 15)

Como 13 é inversı́vel módulo 15, com inverso igual à 7, temos

13t ≡ 3 (mod 15) ⇒ t ≡ 21 (mod 15) ⇒ t ≡ 6 (mod 15)

Portanto t = 6 + 15u, u ∈ Z. Daı́

x = 1 + 13t = 1 + 13 · (6 + 15u) = 79 + 195u.

Note que qualquer inteiro da forma 79 + 195u satisfaz às duas primeiras equações do sistema.
Substituindo x = 79 + 195u na última equação do sistema chegamos à

79 + 195u ≡ 8 (mod 19) ⇔ 5u ≡ 5 (mod 19)

Sendo 5 inversı́vel módulo 19, temos u ≡ 1 (mod 19), ou seja,

u = 1 + 19v

para algum inteiro v. Daı́,

x = 79 + 195u = 79 + 195(1 + 19v) = 274 + 3705v

Assim, qualquer valor de x da forma 274 + 3705v satisfaz as 3 equações. É claro que o menor
inteiro positivo de x que satisfaz o sistema é 274, ou seja, os 3 satélites passarão juntos sobre a
cidade 274 horas depois da meia-noite. E mais, esse fenômeno se repete a cada 3705 horas.

O que fizemos foi dividir o sistema original em outros sistemas de duas equações. Resolvendo
as duas primeiras equações obtivemos x = 79 + 195u, que corresponde a uma nova equação
x ≡ 79 (mod 195). Passamos, então, a resolver o sistema
(
x ≡ 79 (mod 195)
x ≡ 8 (mod 19)

De modo geral, um sistema de várias equações é resolvido utilizando-se vários sistemas de duas
equações. Por este motivo, é suficiente entendermos o algoritmo para resolver sistemas de duas
equações.

72
Equações Lineares Seção 6.1

Considere o sistema (
x ≡ a (mod m)
x ≡ b (mod n)
A primeira equação nos permite escrever

x = a + my , y ∈ Z

Substituindo na segunda equação temos

my ≡ b − a (mod n)

Já vimos que esta equação só tem solução se mdc(m, n) dividir b − a. Assumindo que
mdc(m, n) = 1, temos que m tem inverso em Zn . Seja α o inverso de m em Zn . Chegamos
a seguinte solução
y ≡ α(b − a) (mod n)

ou seja, y = α(b − a) + nk, para algum inteiro k. Daı́,

x = a + my = a + m(α(b − a) + nk) = a + mα(b − a) + mnk

Como αm = 1 em Zn , existe inteiro β tal que 1 − αm = βn. Daı́,

x = a − amα + mαb + mnk = a(1 − mα) + mαb + mnk

= aβn + mαb + mnk

Qual a vantagem de escrever a solução desta maneira? Os inteiros α e β são fáceis de se

obter. Temos 1 = αm + βn. Como estamos supondo mdc(m, n) = 1, basta aplicarmos o algoritmo
euclidiano estendido.
Portanto, se mdc(m, n) = 1, o sistema tem como solução inteiros da forma aβn + bαm + kmn,
onde k é um inteiro qualquer.
Mas quantas são as soluções deste sistema? É claro que são infinitas, pois para cada inteiro k
temos uma solução distinta xk . Digamos que x e y sejam dois inteiros que são soluções do sistema
(
x ≡ a (mod m)
(6.4)
x ≡ b (mod n)

Se x e y são soluções, temos que x ≡ a (mod m) e y ≡ a (mod m). Como essas duas
congruências tem mesmo módulo, podemos subtrair uma da outra, de modo que obtemos

x − y ≡ 0 (mod m)

73
Capı́tulo 6 Sistemas de Congruências

ou seja, m divide x − y. Repetindo esse raciocı́nio, mas usando a segunda equação do sis-
tema, concluı́mos que n divide x − y. Se tivermos mdc(m, n) = 1, segue da segunda parte da
Proposição 2.1.3, do capı́tulo 2, que mn divide x − y, ou seja, se x e y são soluções de (6.4), então
x ≡ y (mod mn). O sistema (6.4) admite infinitas soluções inteiras, mas uma única solução em
Zmn . Este resultado é conhecido como

TEOREMA 6.1.1 (Teorema Chinês do Resto). Sejam m e n inteiros positivos, primos entre sı́. O
sistema (
x ≡ a (mod m)
x ≡ b (mod n)
sempre tem uma única solução em Zmn .

6.2 Congruência Módulo Números Não Primos Entre Sı́

Vimos que o sistema de congruências
(
x ≡ a (mod m)
x ≡ b (mod n)

sempre admite uma única solução em Zmn se mdc(m, n) = 1. Mas o que acontece se não tivermos
a hipótese mdc(m, n) = 1? Vejamos alguns exemplos.
Considere o sistema
x ≡ 3 (mod 12)

x ≡ 19 (mod 8)

Vamos proceder da mesma maneira como anteriormente. A equação x ≡ 3 (mod 12) nos leva à
x = 3 + 12t. Substituindo na segunda equação, temos

x ≡ 19 (mod 8) ⇒ 3 + 12t ≡ 19 (mod 8)

⇒ 12t ≡ 16 (mod 8)

Esta última equação nos permite escrever

12t = 16 + 8u.

Dividindo a equação por 4, chegamos à

3t = 4 + 2u

74
Potências Seção 6.3

que equivale à
3t ≡ 4 (mod 2).

Como 3 ≡ 1 (mod 2) e 4 ≡ 0 (mod 2), temos

t ≡ 0 (mod 2)

ou seja, t = 2k para algum inteiro k. Voltando à expressão que nos dá o valor de x, obtemos

x = 3 + 12t ⇔ x = 3 + 24k ⇔ x ≡ 3 (mod 24)

Chegamos à uma única solução, mas módulo 24, e não módulo 8 · 12 = 96. Neste exemplo, o
sistema tinha solução. Vejamos o que acontece quando tentamos resolver o sistema

x ≡ 4 (mod 9)
x ≡ 3 (mod 6)

Da primeira equação temos x = 4 + 9t. Substituindo na segunda equação, chegamos à

4 + 9t ≡ 3 (mod 6)
9t ≡ −1 ≡ 5 (mod 6)

Sabemos que a congruência ax ≡ b (mod m) possui solução se, e somente se, mdc(a, n) dividir
b. Como mdc(9, 6) = 3 e 3 6 |5, então 9t ≡ 5 (mod 6) não possui solução, e portanto o sistema

x ≡ 4 (mod 9)
x ≡ 3 (mod 6)

também não.

6.3 Potências
O Teorema Chinês do Resto pode ser enunciado para mais de duas equações.

TEOREMA 6.3.1. Sejam n1 , n2 , ..., nk inteiros positivos dois a dois primos entre sı́. Então o
sistema

x ≡ a1 (mod n1 )
x ≡ a2 (mod n2 )
..
.
x ≡ ak (mod nk )

tem uma única solução em Zn1 ···nk .

75
Capı́tulo 6 Sistemas de Congruências

DEMONSTRAÇÃO. A demonstração é feita usando-se indução finita sobre k. Já vimos que o teorema
vale para k = 2. Suponhamos que o teorema valha para o inteiro k − 1, ou seja, o sistema

x ≡ a1 (mod n1 )
x ≡ a2 (mod n2 )
..
.
x ≡ ak−1 (mod nk−1 )

admite uma única solução bk−1 em Zn1 ···nk−1 . Resolver o sistema de k congruências é equivalente
a resolver o sistema

x ≡ bk (mod n1 · · · nk−1 )
x ≡ ak (mod nk )

Como ni e nj são primos entre sı́, sempre que i 6= j, temos que os dois inteiros n1 ...nk−1 e nk
também são primos entre sı́. Logo, o sistema acima admite uma única solução em Zn1 ···nk−1 ·nk ,
como querı́amos demonstrar.
Esta versão do Teorema Chinês do Resto simplifica o cálculo de potências módulo n em alguns
casos. Suponhamos que n = p1 p2 · · · pk , onde p1 < · · · < pk são primos. Dessa forma, temos que
cada fator primo pi aparece na decomposição de n com multiplicidade 1.
Para encontrarmos a forma reduzida de am módulo n, iniciamos com o teorema de Fermat para
calcular a forma reduzida de am módulo pi , para cada um dos fatores primos de n. Digamos que

am ≡ r1 (mod p1 ) e 0 ≤ r1 < p1
m
a ≡ r2 (mod p2 ) e 0 ≤ r2 < p2
..
.
am ≡ rk (mod pk ) e 0 ≤ rk < pk

Finalmente, para encontrarmos a forma reduzida de am módulo n, basta resolvermos o sistema



 x ≡ r1 (mod p1 )

 x ≡ r2

(mod p2 )
..


 .

x ≡ rk (mod pk )


Como todos os módulos são primos, temos que o máximo divisor comum entre dois quaisquer

76
Potências Seção 6.3

deles é 1, portanto o sistema sempre tem solução. E mais, o teorema nos garante que existe uma
única solução r módulo p1 p2 · · · pk = n. Portanto

am ≡ r (mod n)

e chegamos assim a forma reduzida de am módulo n. Vejamos um exemplo.

Qual a forma reduzida de 26754 módulo 1155? Primeiramente observamos que 1155 = 3·5·7·11,
fatores primos com multiplicidade 1. Calculemos a forma reduzida de 26754 a cada um destes
primos, usando o teorema de Fermat.
Módulo 3: 22 ≡ 1 (mod 3)

6754 = 2 · 3377 ⇒ 26754 ≡ (22 )3377 ≡ 13377 ≡ 1 (mod 3)

Módulo 5: 24 ≡ 1 (mod 5)

6754 = 4 · 1688 + 2 ⇒ 26754 ≡ (24 )1688 · 22 ≡ 11688 · 4 ≡ 4 (mod 5)

Módulo 7: 26 ≡ 1 (mod 7)

6754 = 6 · 1125 + 4 ⇒ 26754 ≡ (26 )1125 · 24 ≡ 11125 · 16 ≡ 2 (mod 7)

Módulo 11: 210 ≡ 1 (mod 11)

6754 = 10 · 675 + 4 ⇒ 26754 ≡ (210 )675 · 24 ≡ 1675 · 16 ≡ 5 (mod 11)

Agora, basta resolvermos o sistema




 x≡1 (mod 3)

 x≡4 (mod 5)


 x≡2 (mod 7)

 x≡5 (mod 11)

Para tanto, usaremos o Algoritmo Chinês do Resto. A primeira equação nos dá x = 1 + 3t.
Substituindo na segunda equação, temos

1 + 3t ≡ 4 (mod 5) ⇒ 3t ≡ 3 (mod 5) ⇒ t ≡ 1 (mod 5)

donde concluı́mos que t = 1 + 5u, e portanto

x = 1 + 3(1 + 5u) = 4 + 15u.

77
Capı́tulo 6 Sistemas de Congruências

Substituindo esta informação na terceira equação do sistema, temos

4 + 15u ≡ 2 (mod 7) ⇒ 15u ≡ −2 (mod 7) ⇒ u ≡ 5 (mod 7)

e portanto u = 5 + 7v, ou seja

x = 4 + 15(5 + 7v) = 79 + 105v.

Finalmente, usando a quarta equação, chegamos à

79 + 105v ≡ 5 (mod 11) ⇒ 105v ≡ −74 (mod 11) ⇒ 6v ≡ 3 (mod 11) ⇒ v ≡ 6 (mod 11)

e então v = 6 + 11w, e concluı́mos que

x = 79 + 105(6 + 11w) = 709 + 1155w

o que equivale à
x ≡ 709 (mod 1155)

ou seja
26754 ≡ 709 (mod 1155)

6.4 Partilha de Senhas

Vamos encerrar o capı́tulo vendo uma aplicação do Teorema Chinês do Resto num método que
permite compartilhar uma senha de um cofre entre várias pessoas. Digamos que o cofre de um
banco é aberto por uma senha, e um certo número de funcionários tem acesso ao cofre. A ideia
consiste em “partilhar” a senha entre os funcionários, de modo que não seja possı́vel abrir o cofre
sem a presença de um número mı́nimo de funcionários.
Para abrir o cofre, é necessário uma senha, que é um número s. Digamos que o banco tenha
n funcionários que tenham acesso ao cofre, e que k > 1 é o número mı́nimo de funcionários que
devem estar presentes para que seja possı́vel a abertura do cofre. A cada funcionário será dada
sua ‘parte’ da senha, que é um elemento de um conjunto S de n pares de inteiros positivos, de
modo que:

(1) qualquer subconjunto de S com k elementos permite determinar s facilmente;

(2) é muito difı́cil determinar s conhecendo menos do que k elementos de S.

Primeiramente, escolhemos um conjunto L de n inteiros positivos, dois a dois primos entre si.
Escolhidos tais inteiros, tomamos N igual ao produto dos k menores números de L e M igual ao

78
Partilha de Senhas Seção 6.4

produto dos k − 1 maiores números de L. Dizemos que este conjunto tem limiar k se

N >M

Note que o modo como construı́mos N e M nos garante que o produto de k ou mais elementos
de L é sempre maior do que N e o produto de menos que k elementos é sempre menor do que
M . Depois que construı́mos o conjunto L e os números N e M , escolhemos a senha s, de modo
que N > s > M . O conjunto S será composto pelos pares da forma (m, sm ), onde m ∈ L e sm é
a forma reduzida de s módulo m. Como s > M , segue que s > m para todo m ∈ L, e portanto
também temos que sm < s.
Suponha que mais de k funcionários estejam no banco. Isto significa que são conhecidos t
dentre os pares de S, com t ≥ k. Denotemos tais pares por (m1 , s1 ), ..., (mt , st ). Resolvendo o
sistema de congruências

x ≡ s1 (mod m1 )
x ≡ s2 (mod m2 )
..
.
x ≡ st (mod mt )

encontraremos uma solução x0 . Pelo Teorema Chinês do Resto, temos

x0 ≡ s (mod m1 ...mt ).

Mas será que podemos afirmar que x0 = s? É neste momento que usamos o fato do conjunto L
ter limiar k. Como t ≥ k, segue que

m1 ...mt ≥ N > s.

Pelo Teorema Chinês do Resto, o sistema tem uma única solução menor que m1 ...mt . Mas s
também é solução do sistema e s < m1 ...mt , portanto s = x0 .
Nada nos impede de resolver o sistema no caso em que t < k. Entretanto, como o produto
de menos do que k módulos de L é sempre menor do que s, a solução que encontraremos será
congruente a s, mas pode não ser igual a s.
Façamos um exemplo numérico simples, apenas para fixarmos as ideias. Digamos que há 5
funcionários e que pelo menos 3 devem estar presentes para que o cofre possa ser aberto. Portanto,
o conjunto L deve ter 5 elementos, e seu limiar deve ser 3. Uma escolha simples para L, usando
primos pequenos é
L = {11, 13, 17, 19, 23}

79
Capı́tulo 6 Sistemas de Congruências

Neste caso, o produto dos k = 3 menores números de L é N = 11 · 13 · 17 = 2431, enquanto que

o produto dos k − 1 = 2 maiores números de L é M = 19 · 23 = 437. Como N > M , o conjunto
L realmente tem limiar 3. O valor da senha s pode ser escolhido como sendo qualquer inteiro no
intervalo que vai de 437 a 2431. Escolhamos, por exemplo, s = 953. Para determinarmos os pares
do conjunto S que serão distribuı́dos aos funcionários, temos que calcular 953 módulo m, para
cada m ∈ L.

953 ≡ 7 (mod 11)

953 ≡ 4 (mod 13)
953 ≡ 1 (mod 17)
953 ≡ 3 (mod 19)
953 ≡ 10 (mod 23)

Dessa forma, temos

S = {(11, 7); (13, 4); (17, 1); (19, 3); (23, 10)}

Finalmente, o que acontece se os funcionários que têm senhas (11, 7), (17, 1) e (23, 10) estão
no banco? Para recuperar a senha s devemos resolver o sistema

x ≡ 7 (mod 11)
x ≡ 1 (mod 17)
x ≡ 10 (mod 23)

Usando o algoritmo que discutimos nas primeiras seções deste capı́tulo, obtemos como solução geral
x = 953 + 4301k, onde k é um inteiro positivo. Portanto, x ≡ 953 (mod 4301), e recuperamos o
valor da senha s, a saber, s = 953.

80
Capı́tulo

7
Um Pouco de Estruturas Algébricas

7.1 Grupos
Seja G um conjunto não vazio e ∗ uma operação fechada em G. A estrutura (G, ∗) é um grupo se
a operação satisfaz as seguintes propriedades:

(1) Associatividade: dados a, b ∈ G, temos

a ∗ (b ∗ c) = (a ∗ b) ∗ c

(2) Elementro Neutro: existe um elemento e ∈ G tal que

a∗e=e∗a=a

(3) Elemento Inverso: dado um elemento qualquer a ∈ G, existe um elemento a0 ∈ G tal que

a ∗ a0 = a0 ∗ a = e

Observe que não exigimos que a operação do grupo seja comutativa: a ∗ b = b ∗ a, ∀a, b ∈ G. Isto se
dá devido a existência de grupos interessantes que não satisfazem tal propriedades. Um exemplo
é o grupos das matrizes quadradas de ordem n inversı́veis com a operação de produto usual de
matrizes.
Há também associações “conjunto-operação” que não satisfazem alguma das operações acima, e
portanto, não são grupos. Por exemplo, o conjunto dos vetores no espaço com a operação produto
vetorial não satisfaz a propriedade associativa.
O número de elementos de um grupo é chamado de ordem desse grupo. Os primeiros grupos
que temos contato são de ordem infinita

• Z, Q, R e C com operação +.

81
Capı́tulo 7 Um Pouco de Estruturas Algébricas

• Q\{0}, R\{0} e C\{0} com operação ·.

• Mn×m , o conjunto das matrizes de ordem n × m com entradas reais (resp. complexas) com
operação +, soma usual de matrizes.

• O conjunto das matrizes reais (resp. complexas) inversı́veis com operação · produto usual
de matrizes.

• O conjunto de matrizes reais (resp. complexas) com determinante igual a 1 com operação ·
produto usual de matrizes.

O único grupo de ordem finita que vimos até o momento foi Zn com a soma. Este grupo tem
ordem n. Vamos ver outro grupo, de ordem também finita.

7.2 Simetrias
Os grupos podem ser utilizados no estudo das simetrias. A noção de simetria é relativamente
difı́cil de descrever com precisão. Para exemplificar, uma simetria de uma figura geométrica pode
ser entendida como uma “transformação que, quando aplicada à figura, não altera seu aspecto”.
Vamos descrever as simetrias de um triângulo equilátero. As primeiras transformações que
podemos imaginar são as rotações. Numerando os vértices do triângulo, temos as seguintes ro-
tações:

82
Simetrias Seção 7.2

Além das rotações, temos as reflexões em torno das mediatrizes. São três mediatrizes, que
demonimaremos por ma , mb e mc .

Dessa forma, as três reflexões são as seguintes:

83
Capı́tulo 7 Um Pouco de Estruturas Algébricas

Já temos o conjunto, agora falta a operação. Neste caso, a operação é a composição de
transformações. A composição de funções é sempre associativa, logo já temos que a primeira
propriedade da operação de um grupo é satisfeita. O elemento neutro é a rotação de 0◦ . E quanto
aos inversos? O inverso da rotação de 120◦ é a rotação de 240◦ e vice-versa, e cada reflexão é sua
própria inversa. Portanto, todas as transformações acima têm inversa, e temos um grupo. Este
grupo é conhecido como D3 , e possui seis elementos, ou seja, tem ordem 6.

Usando a numeração dos vértices, podemos descrever cada transformação através da seguinte
notação: no caso da rotação de 120◦ , temos
!
1 2 3
2 3 1

Esta transformação leva cada vértice no adjacente na direção anti-horária.

Todas estas simetrias podem ser vistas como permutações dos vértices. Outro exemplo, a
reflexão em torno da mediatriz mb é descrita por
!
1 2 3
2 1 3

Vamos ver o que acontece quando operamos com essas transformações. Se ρ é a rotação de
120◦ , temos que
ρ2 = ρ · ρ

é a rotação de 240◦ , e ρ3 = e é o elemento neutro. Se σ é uma das reflexões, já sabemos que σ 2 = e.
Vejamos que transformação está associada à transformação σρ. Primeiramente, observemos que
σρ não pode ser uma rotação, ou seja,
σρ 6= e

σρ 6= ρ

σρ 6= ρ2

84
Simetrias Seção 7.2

pois caso contrário, chegarı́amos a absurdos:

σρ = e ⇒ σ(σρ) = σe ⇒ σ 2 ρ = σ ⇒ ρ = σ

σρ = ρ ⇒ (σρ)ρ2 = ρρ2 ⇒ σ = e

σρ = ρ2 ⇒ (σρ)ρ2 = ρ2 ρ2 ⇒ σ = ρ

Portanto σρ tem que ser uma reflexão. Entretanto σρ não pode ser a própria σ, pois

σρ = σ ⇒ σ(σρ) = σσ ⇒ ρ = e

Logo, σρ é uma reflexão diferente de σ. Vamos denotar por σi a reflexão em torno da mediatriz
mi , i = a, b, c. Pelo que discutimos até o momento, temos que σb ρ = σa ou σb ρ = σc . A rotação
ρ leva o vértice que está na posição 1 para a posição 2, e σb move o vértice da posição 2 para a
posição 1, ou seja
σb ρ(1) = 1

e portanto σb ρ é a reflexão que não afeta o vértice que está na posição 1, logo

σb ρ = σc

Usando a notação para descrever as transformações, temos

! ! !
1 2 3 1 2 3 1 2 3
σb ρ = = = σc
2 1 3 2 3 1 1 3 2

Usando propriedades básicas dos grupos, podemos descobrir outras relações entre elementos
de D3 a partir de σb ρ = σc . Se G é um grupo com operação ∗ e x, y ∈ G, então o inverso de x ∗ y
é y 0 ∗ x0 , onde x0 e y 0 são os inversos de x e y, respectivamente, pois

(x ∗ y) ∗ (y 0 ∗ x0 ) = x ∗ (y ∗ y 0 ) ∗ x = x ∗ e ∗ x0 = x ∗ x0 = e

Usando esta propriedade, temos

(σb ρ)0 = ρ2 σb .

Já vimos que σb ρ = σc . Como o inverso de σc é a própria σc , temos ρ2 σb = σc , e portanto

σb ρ = σc = ρ2 σb 6= ρσb

ou seja, o grupo D3 não é comutativo.

Seguindo desta maneira, podemos encontrar a tabela de operação deste grupo.

85
Capı́tulo 7 Um Pouco de Estruturas Algébricas

e ρ ρ2 σa σb σc
2
e e ρ ρ σa σb σc
ρ ρ ρ2 e σc σa σb
2 2
ρ ρ e ρ σb σc σa
σa σa σb σc e ρ ρ2
σb σb σc σa ρ2 e ρ
σc σc σa σb ρ ρ2 e

A leitura desta tabela deve ser feita da seguinte forma: o resultado da operação x ∗ y está na
intersecção da linha que se inicia com x com a coluna que se inicia com y.

7.3 Grupos Aritméticos

Voltemos ao foco do nosso estudo. Nosso foco é compreender propriedades aritméticas dos inteiros
que tem haver com primos e fatoração, e foi para isso que introduzimos a noção de grupo. Mas
qual o grupo que será objeto de nosso estudo?
Primeiramente tomemos um inteiro positivo n. Já denotamos por U (n) o conjunto dos inteiros
inversı́veis de Zn .
U (n) = {a ∈ Z : mdc(a, n) = 1}

Afirmamos que este conjunto é um grupo para a operação de multiplicação de classes de Zn .

Primeiro precisamos verificar que a operação está fechada em U (n). Se a e b são elementos
de Zn , já sabemos que a · b está em Zn , mas não podemos transpor isso para U (n) sem análise
cuidadosa. Precisamos verificar que o produto de dois elementos inversı́veis de Zn ainda é um
elemento inversı́vel de Zn .
Seja a e b elementos de U (n). Pela definição de U (n), a e b possuem inversos, digamos a0 e
b0 . Então ab é inversı́vel e seu inverso é a0 b0 . Para verificarmos, basta multiplicarmos estes dois
elementos.
ab · a0 b0 = aba0 b0 = aa0 bb0 = aa0 · bb0 = 1

Assim, temos um conjunto, U (n), onde está definida uma operação, o produto de classes. Pre-
cisamos verificar que tal operação satisfaz as propriedades da definição de grupo. A associatividade
em U (n) segue da associatividade em Z e da definição de produto de classes. Se a, b ∈ U (n), temos

a·b=a·b=b·a=b·a

O elemento neutro é 1, que é inversı́vel em Zn , e portanto está em U (n). Finalmente, a

existência de inverso para cada elemento de U (n) vem da própria definição de U (n). Portanto
U (n) é um grupo para o produto de classes.

86
Grupos Aritméticos Seção 7.3

Vamos agora tentar determinar a ordem de U (n). Comecemos definindo uma função ϕ que,
a cada inteiro positivo n, associa outro inteiro positivo, a ordem de U (n). Esta é a função ϕ de
Euler ou função totiente. Assim a ordem de U (n) é denotada por ϕ(n).
Vejamos como calcular ϕ, inicialmente em alguns casos especiais. Seja p um inteiro primo.
Dessa forma, todos os inteiros positivos menores que p são primos relativos com p, logo

U (p) = Zp − {0}

tem p − 1 elementos, e portanto ϕ(p) = p − 1.

Também é fácil calcular ϕ(pk ) para p primo. Precisamos contar os inteiros positivos menores
que pk que não são divisı́veis por p. É mais fácil contar aqueles que são dı́visiveis por p. Se a,
0 ≤ a < pk , é divisı́vel por p, então

a = p · b, com 0 ≤ b < pk−1

portanto há pk−1 inteiros positivos menores que pk que são divisı́veis por p. Logo, há pk − pk−1
que não são divisı́veis por p, ou seja

ϕ(pk ) = pk − pk−1 = pk−1 (p − 1).

Para obtermos uma fórmula geral, iniciaremos interpretando o Teorema Chinês do Resto em
forma de tabela. Sejam m e n inteiros tais que mdc(m, n)=1. Construı́mos uma tabela com m · n
casas. No alto da tabela, ao longo da horizontal, escrevemos os elementos de Zm , e a esquerda, ao
longo da vertical, os elementos de Zn . A casa da tabela que fica no encontro da coluna indexada
por a ∈ Zm com a linha indexada por b ∈ Zn será ocupada pelo inteiro x tal que:

(1) 0 ≤ x ≤ mn − 1

(2) x ≡ a (mod m) e x ≡ b (mod n)

Neste caso, dizemos que x tem coordenadas (a, b) na tabela.

O Teorema Chinês do Resto nos garante que todas as casas serão preenchidas. Além disso,
duas casas distintas (a, b) e (c, d) não podem ser preenchidas com um mesmo inteiro. De fato, se
(a, b) e (c, d) são coordenadas de casas distintas, então devemos ter a 6= c ou b 6= d. Suponha que
ambas as casas fossem preenchidas por um mesmo inteiro x0 . Desse modo terı́amos

x0 ≡ a (mod m) x0 ≡ c (mod m)
e
x0 ≡ b (mod n) x0 ≡ d (mod n)

Daı́, segue que

a − c ≡ 0 (mod m) e b − d ≡ 0 (mod n).

87
Capı́tulo 7 Um Pouco de Estruturas Algébricas

Mas por hipótese, a, c < m e b, d < n, e portanto |a − c| < m e |b − d| < n, o que nos permite
concluir que a − c ≡ 0 (mod m) e b − d ≡ 0 (mod n) se, e somente se, a = c e b = d, o que
contradiz a hipótese das casas serem distintas. Logo, duas casas de coordenadas distintas nunca
são preenchidas com um mesmo número.
Entendida esta interpretação do Teorema Chinês do Resto, vamos demonstrar a seguinte afir-
mação: digamos que x ∈ Zmn tem coordenadas (a, b) na tabela discutida anteriormente. Então
AFIRMAÇÃO: x ∈ U (nm) se, e somente se, a ∈ U (m) e b ∈ U (n).
DEMONSTRAÇÃO. Se x ∈ U (mn), então x tem inverso x0 ∈ U (mn), e portanto x·x0 ≡ 1 (mod mn),
ou seja, xx0 − 1 é divisı́vel por mn. Em particular, xx0 − 1 é divisı́vel por m, ou seja,
x · x0 ≡ 1 (mod m). Como x ≡ a (mod m), multiplicando ambos os lados da congruência
por x0 , obtemos 1 ≡ xx0 ≡ ax’.
Portanto a é inversı́vel em Zm , ou seja, a ∈ U (m). De maneira análoga concluı́mos que
b ∈ U (n).
Passemos a demonstração da recı́proca. Seja x ∈ Zmn e suponhamos que suas coordenadas
satisfazem a ∈ U (m) e b ∈ U (n). Precisamos mostrar que x é inversı́vel módulo mn. Seja a0 o
inverso de a em Zm , e b0 o inverso de b em Zn . Pelo Teorema Chinês do Resto, existe um inteiro
y tal que 0 ≤ y ≤ mn − 1 e
y ≡ a0 (mod m)

y ≡ b0 (mod n)

Vamos mostrar que y ∈ Zmn é o inverso de x. Como x ≡ a (mod m) e y ≡ a0 (mod m) temos

xy ≡ aa0 ≡ 1 (mod m)

logo xy − 1 é divisı́vel por m. Da mesma forma, como x ≡ b (mod n) e y ≡ b0 (mod n) temos

que
xy ≡ bb0 ≡ 1 (mod n)

e portanto xy − 1 é divisı́vel por n. Como mdc(m, n) = 1, temos que xy − 1 é divisı́vel por mn,
ou seja
xy ≡ 1 (mod mn)

e portanto y é o inverso de x em Zmn , ou seja, x ∈ U (mn)

Com esta afirmação demonstrada, é fácil demonstrar o seguinte teorema.

TEOREMA 7.3.1. Se m, n são inteiros positivos tais que mdc(m, n) = 1, então

ϕ(mn) = ϕ(m)ϕ(n).

DEMONSTRAÇÃO. Queremos calcular ϕ(mn). Por definição, isto é o número de elementos de

88
Subgrupos Seção 7.4

U (mn). Pela afirmação anterior queremos contar o número de casas da tabela cujas coordenadas
estão em U (m) e U (n), respectivamente. Temos ϕ(m) colunas cujos ı́ndices estão em U (m), e
para cada uma dessas, temos ϕ(n) linhas cujo ı́ndice está em U (n). Portanto temos ϕ(m) · ϕ(n)
casas com as coordenadas em U (m) e U (n) respectivamente. Portanto

ϕ(mn) = ϕ(m)ϕ(n)

Feito isso, temos tudo o que é necessário para obter uma fórmula geral para ϕ(n). Dado um
inteiro n, primeiro fatore n.
n = pe11 · · · pekk

onde p1 < · · · < pk são primos distintos. Pelo teorema anterior, temos

ϕ(n) = ϕ(pe11 ) · · · ϕ(pekk ).

Usando o cálculo de ϕ para potências de primos, obtemos

ϕ(n) = pe11 −1 · · · pkek −1 · (p1 − 1) · (pk − 1).

Façamos um exemplo numérico simples. Se n = 504 = 23 · 32 · 7, então

ϕ(504) = 22 · 3 · (2 − 1)(3 − 1)(7 − 1) = 144.

Apesar de teoricamente simples, essa fórmula é limitada, pois para aplicá-la é necessário fatorar
n, que é um problema muito difı́cil.

7.4 Subgrupos
Seja G um grupo, e ∗ uma operação em G. Um subconjunto não vazio H de G é um subgrupo de
G se:
(1) ∀a, b ∈ H tem-se a ∗ b ∈ H

(2) O elemento neutro de G está em H

(3) Para todo a ∈ H, seu inverso a0 também está em H

Para denotar que H é um subgrupo escrevemos H < G.
Note que um grupo e um subgrupo compartilham da mesma operação. Por exemplo, Q\{0}
é um grupo para o produto, e está contido em Q, mas não é subgrupo de Q, visto que este é um
grupo para a soma, e não para o produto.

89
Capı́tulo 7 Um Pouco de Estruturas Algébricas

Nos grupos finitos é possı́vel estabelecermos relações entre a ordem do grupo e as ordem de
seus subgrupos. Vamos estudar uma dessas relações: o teorema de Lagrange. Para a prova deste
teorema, vamos usar relações de equivalência.
Seja G um grupo e H um subgrupo de G. Vamos definir uma relação de equivalência em G
usando H.
Sejam x e y elementos de G. Diremos que x e y são congruentes módulo H, x ≡ y (mod H),
se
x ∗ y0 ∈ H

onde y 0 é o inverso de y em G. Verifiquemos que esta relação é de fato uma relação de equivalência.
Sejam x, y, z ∈ G.
(1) Reflexividade: x ∗ x0 = e. Como e ∈ H (pois é subgrupo) temos que x ≡ x (mod H).

(2) Simetria: se x ≡ y (mod H) temos que x ∗ y 0 ∈ H. Mas como H é subgrupo, todos os seus
elementos possuem inverso em H. Mas o inverso de x ∗ y 0 é y ∗ x0 ∈ H, logo y ≡ x (mod H).

(3) Transitividade: digamos que x ≡ y (mod H) e y ≡ z (mod H). Isto significa que x∗y 0 ∈ H
e y ∗ z 0 ∈ H. Como ∗ é uma operação em H, temos que (x ∗ y 0 ) ∗ (y ∗ z 0 ) ∈ H, ou seja,
x ∗ z 0 ∈ H, e isto significa que x ≡ z (mod H).
Visto que a relação de congruência módulo H é uma relação de equivalência, vamos determinar a
classe de equivalência de um elemento x ∈ G. Por definição,

x = {y ∈ G : y ≡ x (mod H)}

Mas y ≡ x (mod H) é equivalente à dizer que y ∗ x0 ∈ H, isto é, existe um elemento h ∈ H tal
que y ∗ x0 = h ⇔ y = h ∗ x. Sendo assim, podemos escrever a classe de equivalência de x como

{h ∗ x : h ∈ H}

Note que a classe do elemento neutro é o próprio H. Usaremos a notação Hx para a classe de
equivalência de um elemento x. A relação de congruência modulo H é uma generalização da
relação de congruência módulo n nos números inteiros. No caso particular destes, temos que
G = Z, a operação é a adição e o subgrupo H é Zn = {n · k : k ∈ Z}. Agora temos condições de
demonstrar o
TEOREMA 7.4.1 (Teorema de Lagrange). Em um grupo finito, a ordem de qualquer subgrupo
divide a ordem do grupo.
DEMONSTRAÇÃO. Seja G um grupo finito com operação ∗, e seja H um subgrupo de G. Precisamos
contar quantos elementos tem H. Primeiramente, vamos mostrar que, para um dado x ∈ H, Hx
e H tem o mesmo número de elementos.

90
Subgrupos Seção 7.4

É claro que Hx não pode ter mais elementos do que H, visto que para obter Hx, multiplicamos
cada elemento h ∈ H por um elemento fixo x ∈ G. Além disso, Hx não pode ter menos elementos
do que H, pois para isso acontecer seria necessário dois elementos distintos h1 , h2 ∈ H de modo
que h1 ∗ x = h2 ∗ x, mas esta equação nos levaria a concluir que h1 = h2 , multiplicando à esquerda
por x0 .
Sabemos que G é a reunião de todas as classes de equivalência. Visto que duas classes ou são
iguais ou são disjuntas, o número de elementos de G é igual a soma do número de elementos de
cada classe (classes disjuntas).
Mas mostramos que qualquer classe tem o mesmo número de elementos, e esse número é a
ordem de H.
Sendo assim, o número de elementos de G é igual a ordem de H vezes o número de classes, ou
seja, a ordem de H é um divisor da ordem de G.
Seja G um grupo, e S um subconjunto não vazio de G. Denotaremos por S −1 = {s−1 |s ∈ S}.
Vamos definir um conjunto usando S, e na sequência mostraremos que este conjunto é um subgrupo
de G. Faremos uso da notação multiplicativa.

.
hSi = {a1 a2 · · · an |n ∈ N, ai ∈ S ou ai ∈ S −1 }

Entendamos quem são elementos de hSi. Um elemento de hSi é igual ao produto de uma
quantidade finita de elementos de G, de modo que cada fator deste produto ou é um elemento de
S ou é o inverso de um elemento de S.

PROPOSIÇÃO 7.4.2. Seja G um grupo e S um subconjunto não vazio de S. Então o conjunto

hSi é subgrupo de G.

DEMONSTRAÇÃO. Precisamos mostrar que

(1) ∀a, b ∈ hSi tem-se ab ∈ hSi

(2) O elemento neutro de G está em hSi

(3) Para todo a ∈ hSi, seu inverso a−1 também está em hSi

Seja a e b elementos de hSi. Da definição de hSi temos que

a = a1 a2 · · · an com ai ∈ S ou ai ∈ S −1 , ∀i

b = b1 b2 · · · bm com bj ∈ S ou bj ∈ S −1 , ∀j.

Portanto ab = a1 a2 · · · an b1 b2 · · · bm satisfaz a definição de hSi, logo ab ∈ hSi, o que demonstra a

condição (1).

91
Capı́tulo 7 Um Pouco de Estruturas Algébricas

Agora, tome a um elemento qualquer de S. Sendo e o elemento neutro de G, podemos escrever

e = a · a−1

ou seja, e é igual ao produto de elemento de S e inversos de elementos de S, logo e ∈ hSi,

demonstrando a condição (2).
Finalmente, se
x = a1 a2 · · · an com ai ∈ S ou ai ∈ S −1 , ∀i

é um elemento de hSi, então

y = a−1 −1 −1 −1
n an−1 · · · a2 a1

é seu inverso, e claramente é um elemento de hSi, pois se ai ∈ S então a−1

i ∈ S −1 , e se ai ∈ S −1
então a−1
i ∈ S, logo y ∈ hSi, o que demonstra (3).
Portanto, de fato hSi é subgrupo de G.

DEFINIÇÃO 7.4.3. Dados G um grupo e S um subconjunto não vazio de G, definimos o subgrupo

gerado por S como sendo o conjunto hSi

Note que se g ∈ G, então

hgi = {..., (g −1 )2 , g −1 , e, g, g 2 , ...}.

Se r ∈ N denotaremos (g −1 )r por g −r . Dessa forma

hgi = {g t |t ∈ Z}.

Feita essa discussão, podemos definir grupo cı́clico e provar um resultado que relaciona a ordem
de um elemento g de um grupo G com a ordem do subgrupo gerado por esse elemeno g ∈ G.

DEFINIÇÃO 7.4.4. Um grupo G é cı́clico quando ele pode ser gerado por um único elemento, isto
é, quando G = hgi para algum g ∈ G.

Uma consequência de um grupo ser cı́clico é a seguinte:

PROPOSIÇÃO 7.4.5. Se um grupo G é cı́clico, então G é abeliano.

DEMONSTRAÇÃO. Se G é cı́clico, significa que existe g ∈ G tal que hgi = G, isto é,

∀x ∈ G, ∃t ∈ Z : g t = x.

Sejam x e y dois elementos quaisquer de G. Por hipótese existem inteiros r e s tais que

g r = x e g s = y.

92
Subgrupos Seção 7.4

Disto segue que

x · y = g r · g s = g r+s = g s+r = g s · g r = y · x

ou seja, G é abeliano.
Como consequência deste resultado temos, por exemplo, que o grupo D3 que vimos na segunda
seção não é cı́clico, pois não é abeliano.
Recordando: sendo G um grupo, a ordem de um elemento g ∈ G é o menor inteiro positivo
k tal que ak = e, onde e é o elemento neutro do grupo G; e a ordem de um subgrupo H < G
é o número de elementos de H. Usaremos as notações |g| e |H| para denotar as ordens de um
elemento e de um subgrupo de G, respectivamente. Temos a seguinte proposição:

PROPOSIÇÃO 7.4.6. Seja G um grupo, g ∈ G um elemento de G e H < G um subgrupo de G.

Se a ordem de g é igual a k, k ∈ Z∗+ , então a ordem do subgrupo gerado por {g} também é k.

|g| = k ⇔ |hgi| = k, k ∈ Z∗+

DEMONSTRAÇÃO. Suponha que |g| = k, ou seja, k é o menor inteiro positivo tal que g k = e.
Vamos mostrar que hgi tem k elementos. Da definição de subgrupo gerado, temos que

hgi = {..., (g −1 )2 , g −1 , e, g, g 2 , ...}.

Seja A = {e, g, g 2 , ..., g k−1 }. Afirmamos que hgi = A. A inclusão A ⊂ hgi é trivial. Basta
mostrarmos que hgi ⊂ A. De fato, seja s um inteiro. Dividindo s por k, e obtemos inteiros q e r,
com 0 ≤ r ≤ k − 1, e
s = kq + r

e daı́
g s = g kq+r = (g k )q · g r = g r

pois 0 ≤ r ≤ k − 1 e g k = e, e portanto g s ∈ A. Logo, hgi ⊂ A. Além disso, dois elementos

de A são distintos, pois se existirem inteiros a e b com a < b < k e g a = g b , multiplicando essa
igualdade por g −a , obteriamos
g b−a = e

mas isso contradiz a minimalidade de k. Dessa forma, A tem k elementos e A = hgi. Portanto a
ordem de hgi é k.
Para encerrar o capı́tulo, vamos mostrar o teorema de Euler, generalização do teorema de
Fermat e consequência do teorema de Lagrange.

TEOREMA 7.4.7 (Teorema de Euler). Sejam n > 0 e a números inteiro. Se mdc(a, n) = 1 então

aϕ(n) ≡ 1 (mod n)

93
Capı́tulo 7 Um Pouco de Estruturas Algébricas

DEMONSTRAÇÃO. Como a e n são primos entre sı́, a ∈ U (n). Logo, a ordem de a divide a ordem
de U (n), que é ϕ(n). Sendo k a ordem de a, isto significa que ϕ(n) = kr, para algum inteiro r.
Desse modo
(a)ϕ(n) = (ak )r = 1

que é equivalente à equação do teorema de Euler.

94
Capı́tulo

8
De Volta à Mersenne e Fermat

Já vimos que as fórmulas exponenciais são aquelas que mais nos rendem resultados (ou pelo
menos esperança de) quando estamos interessados em produzir primos “grandes”. Neste capı́tulo
estudaremos mais um pouco sobre os números de Mersenne e de Fermat. Vamos procurar primos
entre os números da forma 2n ± 1.

8.1 Números de Mersenne

Comecemos pelos números de Mersenne

M (n) = 2n − 1

Se n é composto, já sabemos que M (n) também é composto:

n = r · s ⇒ 2n − 1 = (2r )s − 1 = (2r − 1)(2r(s−1) + 2r(s−2) + · · · + 2r + 1)

ou seja, M (r) é fator de M (n) = M (rs). É claro que M (s) também é fator de M (n).
Sendo assim, se queremos encontrar primos entre os números de Mersenne, procurá-los-emos
somente entre os números M (p), com p primo. Já sabemos também que a primalidade de p não
garante a primalidade de M (p).
Vamos discutir um método, devido à Fermat, para buscar fatores de um número de Mersenne.
A ideia é descobrir uma fórmula geral para os primos que podem ser fatores de um número de
Mersenne. Vamos usar ferramentas desenvolvidas no capı́tulo anterior, da teoria dos grupos.
Começamos por um resultado, complementar ao teorema de Lagrange, que já fora citado e usado
na demonstração do teorema de Korselt (TEOREMA 5.4.3, p. 61).

LEMA 8.1.1 (Lema Chave).Seja G um grupo finito, munido de uma operação ∗. Sendo a ∈ G, um
inteiro positivo t satisfaz at = e se, e somente se, t é divisı́vel pela ordem de a.

95
Capı́tulo 8 De Volta à Mersenne e Fermat

DEMONSTRAÇÃO. Seja s a ordem de a ∈ G. Se s divide t, então t = s · r para algum inteiro r, e

at = asr = (as )r = er = e

Para provar a recı́proca, suponha que at = e. Como a ordem de a é o menor inteiro positivo s tal
que as = e, devemos ter s ≤ t. Dividindo t por s, encontramos inteiros q e r tais que

t = s · q + r, 0 ≤ r < s

Dai
e = at = (as )q ∗ ar = ar

visto que as = e. Como ar = e e r < s, só podemos ter r = 0, caso contrário terı́amos uma
contradição à minimalidade de s. Portanto t é divisı́vel pela ordem de a.
Vamos, então, aos números de Mersenne. Seja p 6= 2 um número primo e seja q um fator primo
de M (p) = 2p − 1. Então 2p − 1 = q · s, para algum inteiro s, ou seja

2p ≡ 1 (mod q)

Esta congruência pode ser vista como uma identidade no grupo U (q).

p
2 =1

Pelo lema chave, a ordem de 2 tem que dividir p. Como p é primo, temos que a ordem de 2 em
U (q) é 1 ou p.
Se a ordem de 2 fosse 1, terı́amos
2=1

em U (q). Mas isto significaria 2 ≡ 1 (mod q), ou seja, q|2 − 1, absurdo, pois q 6= 1. Sendo assim,
a ordem de 2 em U (q) é p.
Por outro lado, pelo teorema de Fermat,

q−1
2 = 1 em U (q)

Mais uma vez, pelo lema chave, a ordem de 2, que já sabemos ser p, divide q − 1, ou seja, existe
um inteiro k tal que q − 1 = kp. Mas podemos concluir mais.
Como M (p) = 2p − 1 é um número ı́mpar, todos os fatores de M (p) devem ser ı́mpares. Em
particular, q é ı́mpar, e portanto q − 1 é par. Como p é ı́mpar, concluı́mos que k, na equação
acima, deve ser par, e portanto q − 1 = 2rp para algum inteiro r. Está demonstrado o seguinte
resultado.

96
Números de Fermat Seção 8.2

Método de Fermat: Seja p 6= 2 um primo e q um fator primo de M (p). Então q = 1 + 2rp

para algum inteiro r.
Vamos dar um exemplo para entender como o método funciona. Vamos procurar um fator
de M (11) = 2047. Temos que qualquer fator primo de M (11) é da forma q = 1 + 22r. O que
fazemos é atribuir valores a r e testar, em cada caso, se temos um fator ou não. Antes, vamos
tentar encontrar um limitante superior para r.
p
Se M (p) for composto, então possui um fator primo menor ou igual que M (p). Dessa forma
p
q = 1 + 2rp ≤ M (p).

Também temos que

p √ p
M (p) = 2p − 1 < 2p ⇒ M (p) < 2p ⇒ M (p) < 2p/2

e portanto
p/2 2p/2 − 1
1 + 2rp < 2 ⇒r<
2p
Quando p = 11, obtemos r < 2, 011.... Portanto devemos testar apenas r = 1 e r = 2. Muito
eficiente. Fazendo r = 1 temos q = 1 + 22 · 1 = 23, que é fator de 2047.

2047 = 23 · 89

8.2 Números de Fermat

Vamos considerar os números da forma 2n + 1. Vamos supor que p = 2n + 1 seja primo. Temos
que
n
2 = −1 em U (p)

e portanto
2n
2 = 1 em U (p)
n
Disto temos que a ordem de 2 em U (p) divide 2n. Note que da primeira equação, 2 = −1, a
ordem de 2 não pode ser n, e nem um divisor de n. Como ela deve dividir 2n, temos que a ordem
de 2 deve ser um múltiplo de 2. Digamos que a ordem de 2 seja 2r, com r um inteiro positivo
divisor de n. Assim
2r
2 = 1 em U (p)

Daı́,
2r r r
0 = 2 − 1 = (2 + 1)(2 − 1)

97
Capı́tulo 8 De Volta à Mersenne e Fermat

em Zp . Como estamos supondo p primo, podemos concluir que

2r ≡ 1 (mod p) ou 2r ≡ −1 (mod p)

ou seja, p divide 2r + 1 ou 2r − 1. Mas n ≥ r e p = 2n + 1, portanto devemos ter r = n, e assim a

ordem de 2 em U (p) é 2n.
Como p − 1 = 2n , pelo teorema de Fermat

p−1 2n
2 =2 = 1 em U (p)

e portanto, a ordem de 2 (que é 2n) divide 2n . Em particular, concluı́mos que a ordem de 2 em

U (p) é uma potência de 2, ou seja, 2n + 1 só pode ser primo quando n é uma potência de 2.
k
Isto justifica o fato de estarmos interessados nos números da forma 22 + 1, os números de
Fermat, F (k).
Digamos que q é um fator primo de F (k). Então

2k 2k+1
2 = −1 em U (q) ⇒ 2 = 1 em U (q)

O lema chave nos permite concluir que a ordem de 2 divide 2k+1 . Da equação

2k
2 = −1 em U (q)

concluı́mos que a ordem de 2 não pode ser uma potência menor que 2k+1 . Portanto a ordem de 2
em U (q) é exatamente 2k+1 . Como q é primo, temos que

q−1
2 = 1 em U (q)

e concluı́mos que a ordem de 2 em U (q), 2k+1 , divide q − 1, ou seja, q − 1 = r · 2k+1 para algum
r inteiro. O raciocı́nio que desenvolvemos é parecido com o que Fermat fez para os números de
Mersenne, mas ironicamente foi Euler quem desenvolveu esse método, apenas adaptanto para os
números de Fermat o que o francês havia feito para os números de Mersenne.
Método de Euler: Se q é um fator primo de F (k), então existe um inteiro positivo r tal que

q = 1 + r · 2k+1

8.3 O método de Lucas-Lehmer

O próximo teste que estudaremos foi inventado por E. Lucas em 1878, e aperfeiçoado por D. H.
Lehmer, em 1932.

98
O método de Lucas-Lehmer Seção 8.3

O teste usa uma sequência de inteiros definida recursivamente por:

S0 = 4 e Sk+1 = Sk2 − 2

Primeiramente, vamos verificar que qualquer elemento da sequência se escreve como potência
de números irracionais.
√ √
Considere w = 2 + 3 e v = 2 − 3. Vamos mostrar que

n n
Sn = w2 + v 2 . (8.1)

n n
Obviamente, w + v = S0 , e portanto a relação vale para n = 0. Suponha que Sn = w2 + v 2 .
Elevando os dois membros ao quadrado, obtemos

n n n n
Sn2 = (w2 )2 + 2 · w2 · v 2 + (v 2 )2
n+1 n n+1
= w2 + 2(wv)2 + v 2
√ √ √ 2
Como wv = (2 + 3)(2 − 3) = 22 − 3 = 4 − 3 = 1, temos

n+1 n+1 n+1 n+1

Sn2 = w2 + 2 + v2 ⇔ w2 + v2 = Sn2 − 2

Mas Sn2 − 2 = Sn+1 por definição. Portanto, pelo princı́pio de indução finita

n n
w2 + v 2 = Sn ∀n ∈ N

Antes de demonstrar o teste, vamos introduzir novos grupos que serão úteis para a demons-
tração.
√
Considere o conjunto Z 3 definido por
h√ i √
Z 3 = {a + b 3 : a, b ∈ Z}

√
A soma e a multiplicação em Z 3 serão as mesmas que estamos habituados em R. Note que
√ √
qualquer inteiro a pode ser escrito como a + 0 · 3, logo Z ⊂ Z 3 . A soma e o produto de dois
√ √
elementos de Z 3 ainda é um elemento de Z 3 .
√ √ √
(a + b 3) + (c + d 3) = (a + c) + (b + d) 3
√ √ √
(a + b 3)(c + d 3) = (ac + 3bd) + (ad + bc) 3
√
Note que Z 3 é um grupo com respeito à soma: a operação + é evidentemente associativa,
√ √ √ √
0 + 0 3 é o elemento neutro, e o elemento inverso de a + b 3 é −(a + b 3) = (−a) + (−b) 3

99
Capı́tulo 8 De Volta à Mersenne e Fermat

Considere agora o seguinte conjunto: sendo q um inteiro primo, definimos

n h√ io
I(q) = q · α : α ∈ Z 3

Temos que
(1) 0 = q · 0 ∈ I(q)
√
(2) qα + qβ = q(α + β) ∈ I(q), ∀α, β ∈ Z 3
√ √ √
(3) se qα ∈ I(q), então α ∈ Z 3 , e como Z 3 é grupo, então −α ∈ Z 3 , e portanto
−(qα) = q(−α) ∈ I(q).
√
portanto I(q) é um subgrupo do grupo aditivo Z 3 .
Do que vimos no capı́tulo anterior, temos que a relação de congruência módulo I(q) é uma
√ √
relação de equivalência em Z 3 . Recordando: dados α, β ∈ Z 3 , então α ≡ β (mod I(q))
quando α − β ∈ I(q)
√
Seja α ∈ Z 3 . Então α se escreve como
√
α = a1 + a2 3

Dividindo a1 e a2 por q obtemos

a1 = q · b1 + r1 , 0 ≤ r1 < q

a2 = q · b2 + r2 , 0 ≤ r2 < q
√
Sabemos que r1 e r2 são determinados de maneira única. Defina ρ = r1 + r2 3. Daı́,
√ √
α − ρ = (a1 + a2 3) − (r1 + r2 3)
√ √
= (qb1 + r1 ) + (qb2 + r2 ) 3 − r1 − r2 3
√
= q(b1 + b2 3)

Portanto α ≡ ρ (mod I(q)). O número ρ será chamado de forma reduzida de α módulo I(q). Da
√
unicidade do resto da divisão euclidiana, segue que cada elemento de Z 3 tem uma única forma
√ √
reduzida. Se ρ = r1 + r2 3 é a forma reduzida de um elemento de Z 3 , note que 0 ≤ r1 , r2 < q,
ou seja, r1 pode assumir q valores, assim como r2 . Portanto há exatamente q 2 formas reduzidas
√
distintas módulo I(q) em Z 3 .
√
Além disso, cada classe de equivalência de Z 3 módulo I(q) pode ser representada por
um elemento em forma reduzida, e duas classes representadas por elementos de formas reduzi-
√ .
das distintas são obrigatoriamente distintas. Portanto o conjunto Z 3 I(q) das classes de
equivalência módulo I(q) tem q 2 elementos.

100
O método de Lucas-Lehmer Seção 8.3

√
Denotaremos a classe de α ∈ Z 3 módulo I(q) por α
e. Vamos definir uma multiplicação em
√ .
Z 3 I(q) por
e · βe = α
α ] ·β

Primeiramente, verifiquemos que tal operação está bem definida: sejam α e α0 representantes
e, e β e β 0 representantes da classe β.
da classe α e Note que

αβ − α0 β 0 = αβ − α0 β + α0 β − α0 β 0
= β(α − α0 ) + α0 (β − β 0 ) ∈ I(q)

pois α ≡ α0 (mod I(q)) e β ≡ β 0 (mod I(q)), e portanto αβ 0β 0.

f = αg

A operação ·, definida anteriormente, é associativa, comutativa e tem e

1 como elemento neutro.
√ .
Mas Z 3 I(q) não é um grupo para esta operação. Por exemplo, e 0 não possui inverso em
√ .
Z 3 I(q).
Assim como fizemos em Zn , vamos considerar o conjunto V (q) formado pelos elementos in-
√ .
versı́veis de Z 3 I(q). Este novo conjunto é um grupo, pois o produto de dois elementos
inversı́veis ainda é um elemento inversı́vel: sejam α, β ∈ V (q) com inversos α−1 e β −1 . O inverso
de αβ é β −1 α−1 , pois

(αβ)(β −1 α−1 ) = α(ββ −1 )α−1 = α · 1 · α−1 = αα−1 = 1.

Temos que h√ i .
V (q) ⊂ Z 3 I(q)\{e
0}

portanto a ordem de V (q) é necessáriamente menor que q 2 .

√ √
Além disso, como w · v = (2 + 3)(2 − 3) = 1, temos que w e v pertencem a V (q).

TESTE 8.3.1 (Teste de Lucas-Lehmer). Seja p um primo positivo. O número de Mersenne M (p) é
primo se, e somente se, Sp−2 ≡ 0 (mod M (p)).

Provaremos apenas que a condição é necessária. Para uma demonstração completa, sugerimos
consultar [02].
DEMONSTRAÇÃO. Suponha que, para algum primo p, o número de Mersenne M (p) = 2p − 1 divide
Sp−2 . Por (8.1) existe um inteiro r tal que

p−2 p−2
w2 + v2 = rM (p)

101
Capı́tulo 8 De Volta à Mersenne e Fermat

p−2
Multiplicando esta equação por w2 , e relembrando que wv = 1, obtemos

p−1 p−2
w2 + 1 = rM (p)w2 . (8.2)

Suponha, agora, que M (p) é composto e que q é seu menor fator primo, e vamos tentar chegar a
uma contradição. Como q divide M (p), obtemos a partir de (8.2) que

p−1
e2
w = −e
1 (8.3)
√ .
em Z 3 I(q). Elevando ambos os membros de (8.3) ao quadrado

p
e2 = e
w 1.

Segue disto, e do lema chave, que a ordem de we tem que dividir 2p ; mas a equação (8.3) também
nos diz que esta ordem não pode ser uma potência de 2 menor que 2p . Portanto, a ordem de w e
p
em V (q) é 2 . Mas pelo teorema de Lagrange, a ordem de we divide a ordem de V (q). Como V (q)
tem ordem menor ou igual a q 2 − 1, concluı́mos que 2p ≤ q 2 − 1. Entretanto, q é o menor divisor
primo de M (p), de modo que q 2 ≤ M (p). Assim

2p ≤ q 2 − 1 < q 2 ≤ M (p) = 2p − 1 ⇒ 2p < 2p − 1

que é a contradição desejada. Com isso, se M (p) divide Sp−2 então M (p) é primo.

102
Capı́tulo

9
Raı́zes Primitivas

No capı́tulo anterior vimos métodos que nos permitem investigar se números de Mersenne e
Fermat são primos ou compostos. Mas, e se tomarmos um inteiro n qualquer? No capı́tulo 5,
vimos testes que detectavam inteiros n compostos. Agora, veremos um teste que identifica a
primalidade de um inteiro n sem tentar encontrar fatores de n. Este teste é inspirado no teorema
da raiz primitiva, assunto já citado no capı́tulo 4. Neste capı́tulo iremos finalmente provar este
resultado.

9.1 O teste de Lucas

Seja n ∈ Z∗+ um inteiro ı́mpar. A pergunta que queremos responder é: n é primo? Suponha que
encontremos um inteiro b tal que a ordem de b em U (n) seja exatamente n − 1, isto é,

n−1 r
b = 1 e b 6= 1 sempre que r < n − 1

Lembrando que denotamos a ordem de U (n) por ϕ(n), pelo teorema de Lagrange a ordem de b,
que é n − 1, divide ϕ(n), e portanto n − 1 ≤ ϕ(n). Mas ϕ(n) ≤ n − 1, pela própria definição da
função ϕ. Concluı́mos desse modo que ϕ(n) = n − 1, e isso só é possı́vel se n for primo.
Portanto, a chave está em encontrar b ∈ U (n) com ordem n − 1. O seguinte teste nos dá uma
maneira de mostrar que a ordem de um elemento de U (n) é n − 1.

TESTE 9.1.1 (Teste de Lucas). Seja n um inteiro positivo ı́mpar e b um inteiro, 2 ≤ b ≤ n − 1. Se

n−1
bn−1 ≡ 1 (mod n) e b p 6≡ 1 (mod n)

para cada fator primo p de n − 1, então n é primo.

DEMONSTRAÇÃO. Seja k a ordem de b em U (n). Precisamos mostrar que k = n − 1. Por hipótese,

n−1
b = 1.

103
Capı́tulo 9 Raı́zes Primitivas

Pelo lema chave, k divide n − 1, ou seja, existe um inteiro t tal que

n − 1 = k · t.

Portanto, basta mostrarmos que t = 1. Suponha, por absurdo que t > 1. Então t é divisı́vel por
algum primo q (t = qs para algum inteiro s).
n−1 t
Temos também que q divide n − 1, portanto e são inteiros. E mais, visto que
q q

n−1 t
=k·
q q

n−1
concluı́mos que k divide . Como k é a ordem de b, pelo lema chave
q
n−1
b q ≡ 1 (mod n)

o que contradiz as hipóteses. Portanto t = 1, logo k = n − 1. Dessa forma, temos um inteiro

b ∈ U (n) com ordem n − 1, o que implica a primalidade de n.

Apesar de uma demonstração simples, o teste de Lucas apresenta uma pequena dificuldade
quanto a aplicação. Vamos explicitar tal dificuldade com um exemplo simples. Apliquemos o teste
para n = 41
n = 41 → n − 1 = 40 = 23 · 5 → fatores primos 2 e 5.

Precisamos encontrar um inteiro 2 ≤ b ≤ 40 tal que

b40 ≡ 1 (mod 41)

b20 6≡ 1 (mod 41)

b8 6≡ 1 (mod 41)

Se escolhemos base b = 2, temos

240 ≡ (26 )6 · 24 ≡ 236 · 24 ≡ 18 · 24 ≡ 1 (mod 41)

mas
220 ≡ 1 (mod 41).

Tentemos, então, base b = 3.

340 ≡ (320 )2 ≡ (−1)2 ≡ 1 (mod 41)

104
O teste de Lucas Seção 9.1

320 ≡ −1 6≡ 1 (mod 41)

Mas
38 ≡ 1 (mod 41)

Note ainda que

28 ≡ 10 6≡ 1 (mod 41)

ou seja, bases diferentes satisfazem equações relativas a fatores diferentes de n − 1. Mas o teste
exige que uma única base satisfaça todas as equações. Entretanto, o teste de Lucas pode ser
melhorado, de modo que podemos escolher uma base distinta para cada fator primo de n − 1.

TESTE 9.1.2 (Teste de Primalidade). Seja n > 0 um inteiro tal que

n − 1 = pe11 · pe22 · · · perr

onde p1 < · · · < pr são primos. Se para cada i = 1, ..., r existir um inteiro positivo bi ,
2 ≤ bi ≤ n − 1, que satisfaça
bin−1 ≡ (mod n)
n−1
pi
bi 6≡ 1 (mod n)

então n é primo.

DEMONSTRAÇÃO. Considere o caso i = 1. Seja s1 a ordem de b1 em U (n). Da equação

b1n−1 ≡ 1 (mod n)

concluı́mos que s1 divide n − 1, ou seja,

s1 = pk11 · · · pkr r

onde 0 ≤ k1 ≤ e1 , ..., 0 ≤ kr ≤ er . Além disso, por hipótese,

n−1

b1p1 6≡ 1 (mod n)

n−1
ou seja, não é divisivel por s1 . Como
p1

n−1
= pe11 −1 · pe22 · · · perr
p1

só podemos ter k1 = e1 , e portanto pe11 divide s1 . Pelo teorema de Lagrange, s1 divide a ordem de

105
Capı́tulo 9 Raı́zes Primitivas

U (n).
pe11 |s1 e s1 |ϕ(n) ⇒ pe11 |ϕ(n)

O raciocı́nio anterior se aplica à qualquer i = 1, ..., r. Temos então que as equações do teste nos
permitem concluir que os inteiros pe11 , pe22 , ..., perr dividem ϕ(n). Como esses inteiros são potências
de primos distintos, eles são primos entre sı́, e portanto o produto

pe11 · pe22 · · · perr = n − 1

divide ϕ(n). Como ϕ(n) ≤ n − 1, só resta uma possibilidade, ϕ(n) = n − 1, ou seja, n é primo.
Como dissemos no inı́cio do capı́tulo, o teste de Lucas tem origem no teorema da raiz primitiva.
Este resultado é alvo da nossa próxima seção.

9.2 Teorema da Raiz Primitiva

Antes de demonstrar este teorema, vamos ver um lema que nos será útil. Este resultado vale
para qualquer grupo abeliano, e não apenas para U (p), por isso seu enunciado está descrito num
contexto mais amplo.

LEMA 9.2.1. Seja G um grupo abeliano finito, munido de uma operação ∗. Se G tem elementos de
ordens r e s, então G tem um elemento cuja ordem é igual ao mı́nimo múltiplo comum de r e s.

DEMONSTRAÇÃO. Sejam a e b elementos de ordem r e s respectivamente. Primeiramente, fa-

toramos r e s em fatores primos
r = pe11 · · · pekk

s = pf11 · · · pfkk

onde os primos não estão necessariamente enumerados em ordem crescente. Além disso, isso não
significa que r e s tem os mesmos fatores. Se um fator pi de r não é fator de s, isso significa que
fi = 0. Na verdade, é conveniente que enumeremos os primos de modo que para um inteiro g,
1 ≤ g ≤ k, tenhamos

e1 ≥ f1 , ..., eg ≥ fg e eg+1 < fg+1 , ..., ek > fk

ou seja, os expoentes dos g primeiros primos na fatoração de r são maiores ou iguais aos expoentes
correspondentes na fatoração de s, e os expoentes dos primos restantes são menores na fatoração
de r do que na de s.
Agora, definimos
f
r0 = pe11 · · · pegg e s0 = pg+1
g+1
· · · pfkk

106
Teorema da Raiz Primitiva Seção 9.2

Obviamente, temos mdc(r0 , s0 ) = 1. Por outro lado, r0 s0 é o produto de potência dos primos
p1 , ...pk , onde cada primo pi aparece com o maior expoente entre ei e fi , ou seja, r0 s0 é o mı́nimo
múltiplo comum de r e s. Como r0 |r e s0 |s, existem inteiros u e v tais que

r = r0 u

s = s0 v

Vamos mostrar que c = au ∗ bv tem ordem r0 s0 .

Seja m = r0 s0 o mı́nimo múltiplo comum entre r e s. Então r|m e s|m. Digamos que m = rt e
m = sq para certos inteiros t e q. Daı́,

cm = (au ∗ bv )m = aum ∗ bvm = (ar )tu ∗ (bs )qv = e

Na segunda igualdade acima está sendo usada a hipótese de G ser abeliano, pois se x, y ∈ G

(x ∗ y)q = xq ∗ y q

só vale se ∗ for comutativa.

Como cm = e, a ordem de c divide o mı́nimo múltiplo comum de r e s.
Agora, se n é a ordem de c, temos

e = cn = aun ∗ bvn .

Elevando esta igualdade ao expoente r0 , chegamos à

0 0 0
e = (ar u )n ∗ bvnr = bvnr

pois r0 u = r é a ordem de a. Pelo lema chave, a ordem de b, que é s, divide vnr0 . Mas s = s0 v, ou
seja, s0 divide nr0 . Como s0 e r0 são primos entre sı́, concluı́mos que s0 divide n. Com raciocı́nio
análogo, invertendo os papéis de a e b e de r e s, concluı́mos que r0 também divide n. Daı́,

r0 |n 

0
s |n ⇒ r0 s0 |n ⇔ m|n

mdc(r0 , s0 ) = 1


Mas se m|n e n|m, só nos resta concluir que m = n, e c de fato é o elemento que procurávamos.

TEOREMA 9.2.2 (Teorema da Raiz Primitiva). Se p é primo, então U (p) é cı́clico.

DEMONSTRAÇÃO. Escolha um elemento qualquer a1 ∈ U (p), onde 1 < a1 < p − 1. Seja k1 a ordem
de a1 . Se k1 = p − 1, então a1 é um gerador de U (p), logo U (p) é cı́clico.

107
Capı́tulo 9 Raı́zes Primitivas

Suponhamos então que k1 < p − 1. O elemento a1 é uma solução da equação xk1 = 1 em Zp .

Como p é primo, esta equação tem no máximo k1 soluções distintas em Zp . Note que os elementos
de
H = {1, a1 , a1 2 , a1 3 , ..., a1 k1 −1 }

são soluções de xk1 = 1. Mas H possui k1 elementos, e portanto em H estão todas as soluções de
xk1 = 1. Como k1 < p − 1, existe um elemento b ∈ U (p) que não está em H e não é solução de
xk1 = 1, isto é,
k1
b 6≡ 1.

Desta última expressão e do lema chave, concluı́mos que se r é a ordem de b, então r não divide
k1 . Se r = p − 1, então b é um gerador de U (p).
Se r < p − 1, usando o lema anterior construı́mos um elemento a2 que tem ordem
k2 = mmc(k1 , r). Como r 6 |k1 , temos k2 > k1 .
Repetindo o que fizemos com a1 para o inteiro a2 , e assim sucessivamente, construiremos uma
sequência estritamente crescente
k1 < k2 < k3 < · · ·

de inteiros que são ordens de elementos de U (p), ou seja, ki ≤ p − 1 ∀i. Isso nos garante que
encontraremos um elemento aj com |aj | = p − 1, e portanto este inteiro aj será um gerador de
U (p), ou seja, U (p) é cı́clico.
A demonstração do teorema da raiz primitiva não apenas nos garante a existência de um
gerador de U (p) quando p é primo, mas ela nos diz como construir tal gerador.
Para exemplificar vamos determinar uma raiz primitiva (gerador) de U (73). Procederemos
como na demostração do teorema. Porém, antes de iniciarmos, precisamos de um método (algo-
ritmo) para calcular a ordem de um elemento de U (p).
Seja p primo e a ∈ U (p). Seja k a ordem de a. Pelo teorema de Lagrange, k divide a ordem
de U (p). Neste caso, k|p − 1. Para aplicar um método usado por Gauss, precisamos fatorar p − 1.
Digamos que
p − 1 = q1e1 · · · qm
em

onde q1 < · · · < qm são primos e e1 , ..., em são inteiros positivos. Se k divide p − 1, então existem
inteiros não negativos r1 , ..., rm tais que

k = q1r1 · · · qm
rm

e 0 ≤ r1 ≤ e1 , ..., 0 ≤ rm ≤ em . O que faremos é determinar quem são os inteiros r1 , ..., rm . Assim

determinamos k. Para encontrar o inteiro ri , faremos uso de uma sequência que depende do primo
qi . Considere a sequência
2 ei
ap−1 , a(p−1)/qi , a(p−1)/qi , ..., a(p−1)/qi

108
Teorema da Raiz Primitiva Seção 9.2

módulo p. Pelo teorema de Fermat, o primeiro termo dessa sequência é sempre 1. Seja wi o
maior inteiro não negativo tal que
wi
a(p−1)/qi ≡ 1 (mod p) (9.1)

Temos duas possibilidades: ou wi = ei ou wi < ei . No segundo caso, temos que

wi +1
a(p−1)/qi 6≡ 1 (mod p). (9.2)

p−1
Do lema chave e da equação (9.1) que caracteriza wi , temos que k divide . Além disso, de
qiwi
p−1
(9.2) concluı́mos que k não divide . Escrevendo de outra forma, o inteiro k = q1r1 · · · qiri · · · qm
rm
qiwi +1
divide
p−1
q1e1 · · · qiei −wi · · · qm
em
=
qiwi
mas não divide
p−1
q1e1 · · · qiei −wi −1 · · · qm
em
=
qiwi +1
o que nos leva à ri = ei − wi . Para esclarecer o que foi feito, passemos ao exemplo. Queremos
determinar uma raiz primitiva de U (73). Portanto temos

p = 73 → ϕ(p) = p − 1 = 72 = 23 · 32

Na demonstração do teorema da raiz primitiva, a primeira coisa que fizemos foi escolher um
elemento a1 ∈ U (p). Para “facilitar” as contas inicialmente, vamos escolher a1 = 2. Vamos agora
calcular a ordem de 2 usando o que discutimos anteriormente.

|2| = 2r1 · 3r2 , 0 ≤ r1 ≤ 3 e 0 ≤ r2 ≤ 2

x
Determinando r1 : 2(p−1)/2 , x = 1, 2, 3.
72
36 7
• x = 1 −→ 2 2 = 2 = (2 )5 · 2 = 37 · 2 = 1
72
18
• x = 2 −→ 2 22 = 2 =1
72
9
• x = 3 −→ 2 23 = 2 = 1

Portanto, para o primeiro fator primo de a1 = 2, encontramos w1 = 3, o que nos leva à

r1 = e1 − w1 = 0
x
Determinando r2 : 2(p−1)/3 , x = 1, 2.
72
• x = 1 −→ 2 3 = 64

109
Capı́tulo 9 Raı́zes Primitivas

72
8
• x = 2 −→ 2 9 = 2 = 37

Portanto, para o segundo fator primo de a1 = 2, encontramos w2 = 0, o que nos leva à

r2 = e2 − w2 = 2 − 0 = 2. Portanto

|2| = 20 · 22 = 9 6= 72 = p − 1.

Como |2| =
6 72, precisamos escolher outro inteiro b de modo que b ∈
/ h2i.

h2i = {1, 2, 4, 8, 16, 32, 64, 55, 37}

Escolhamos b = 3, e calculemos sua ordem.

|3| = 2r1 · 3r2

y
Determinando r1 : 372/2 , y = 1, 2, 3.
72
36 4 9 3 9 3
• y = 1 −→ 3 2 = 3 = (3 )9 = 8 = (2 )9 = (2 )3 = 1 = 1
72
18
• y = 2 −→ 3 22 = 3 = 72
72
9
• y = 3 −→ 3 23 = 3 = 46

Portanto, para o primeiro fator primo de b = 3, encontramos w1 = 1, o que nos leva à

r1 = e1 − w1 = 3 − 1 = 2
y
Determinando r2 : 372/3 , y = 1, 2.
72
2 4 6
• y = 1 −→ 3 3 = 3 4 = (3 )6 = 8 = 1
72
8
• y = 2 −→ 3 9 = 3 = 64

Portanto, para o segundo fator primo de b = 3, encontramos w2 = 1, o que nos leva à

r2 = e2 − w2 = 2 − 1 = 1. Portanto

|3| = 22 · 31 = 12 6= 72 = p − 1.

Como |b| 6= 72, vamos usar a1 = 2 e b = 3 para gerar a2 . Para isso, usaremos o lema, e
v
obteremos |a2 | = mmc(12, 9) = 36. a2 = a1 u · b , onde u · v = mdc(|a1 |, |b|) = mdc(12, 9) = 3 e
mdc(u, v) = 1. Fazendo uso da notação que usamos na demonstração do lema, temos

|2| = r = 32 ⇒ r0 = 32 ⇒ u = 1

|3| = s = 3 · 22 ⇒ s0 = 22 ⇒ v = 3

110
Teorema da Raiz Primitiva Seção 9.2

1 3
Daı́, a2 = 2 · 3 = 54. Já sabemos que |54| = 36.

h54i = {1, 54, 69, 3, 16, 61, 9, 48, 37, 27, 71, 38, 8, 67, 41, 24, 55, 50,
72, 19, 4, 70, 57, 12, 64, 25, 36, 46, 2, 35, 65, 6, 32, 49, 18, 23}

Agora, escolhemos um novo b ∈ / h54i. O menor b possı́vel é b = 5. Precisamos calcular a ordem

de 5. Se encontrarmos |5| = 72, teremos encontrado um gerador de U (73), caso contrário teremos
de usar a2 = 54 e b = 5 para gerar a3 .

|5| = 2r1 · 3r2

z
Determinando r1 : 572/2 , z = 1, 2, 3.
72
36 4 9 6 3
• z = 1 −→ 5 2 = 5 = (5 )9 = 41 = 41 · 41 = 8 · 9 = 72
72
18 9 2
• z = 2 −→ 5 22 = 5 = (5 )2 = 10 = 27
72
9
• z = 3 −→ 5 23 = 5 = 10

Portanto, para o primeiro fator primo de b = 5, encontramos w1 = 0, o que nos leva à r1 = e1 = 3

z
Determinando r2 : 572/3 , z = 1, 2.
72
24 6 4
• z = 1 −→ 5 3 = 5 = (5 )4 = 3 = 8
72
8
• z = 2 −→ 5 9 = 5 = 2

Portanto, para o segundo fator primo de b = 5, encontramos w2 = 0, o que nos leva à r2 = e2 = 2.

Portanto
|5| = 23 · 32 = 72

portanto 5 é gerador de U (73)

111
Capı́tulo 9 Raı́zes Primitivas

112
Capı́tulo

10
Criptografia RSA

Este método de criptografia, o mais conhecido dos métodos de chave pública, foi inventado
em 1978 por R. L. Riverst, A. Shamir e L. Adleman. As letras RSA correspondem às iniciais dos
inventores do código. Finalmente podemos descrever o funcionamento do RSA e entender porque
é seguro.

10.1 Pré-codificação
A primeira coisa que devemos fazer para usar o RSA é transformar a mensagem em uma sequência
de números. Vamos fazer um exemplo onde a mensagem contém apenas letras. Esta primeira
etapa será chamada de pré-codificação. Usaremos a seguinte tabela para convertermos letras em
números:
A B C D E F G H I J K L M
10 11 12 13 14 15 16 17 18 19 20 21 22

N O P Q R S T U V W X Y Z
23 24 25 26 27 28 29 30 31 32 33 34 35
Usaremos o número 99 para substituir o espaço entre palavras. Por exemplo, a frase Matemática
é divertida gera o número

m = 22102914221029181210991499131831142729181310.

que é a mensagem a ser codificada.

O próximo passo é escolher os parâmetros do sistema RSA. Esses parâmetros são dois primos
p e q. Seja n = pq. A última etapa da fase de pré-codificação é quebrar o número m em blocos.
Esses blocos devem ser números menores que n. No nosso exemplo, vamos escolher p = 11 e
q = 13, logo temos n = 143. Uma possı́vel maneira de quebrar o número m é

22−102−91−42−2−102−91−8−12−10−9−91−49−91−31−83−11−42−72−91−81−3−10

113
Capı́tulo 10 Criptografia RSA

Essa quebra pode ser feita de várias maneiras, mas alguns cuidados devem ser tomados. Por
exemplo, deve-se evitar que o bloco comece por 0, pois isso traria problemas na decodificação.

10.2 Codificando e Decodificando

Passemos, então, a codificação dos blocos propriamente dita. Para codificar um bloco b do número
m precisamos de dois inteiros: o inteiro n, que já escolhemos como sendo n = pq = 11 · 13 = 143,
e outro inteiro e que seja inversı́vel módulo ϕ(n). No caso temos ϕ(n) = (p − 1)(q − 1) = 120.
Vamos escolher e = 7. O par (n, e) = (143, 7) é a chave de codificação ou chave pública. Cada
bloco será codificado separadamente, e não podemos juntar os blocos codificados afim de formar
um longo número, os blocos codificados devem ser mantidos separados.
Se a chave de codificação é (n, e), como devemos proceder para codificar um bloco b? Note
que b é um inteiro positivo menor do que n. Denotando o bloco codificado por C(b), usaremos a
seguinte receita para calculá-lo:

C(b) = resto da divisão de be por n.

Em termos de aritmética modular, temos que C(b) é a forma reduzida de be módulo n. Vamos
codificar os blocos da nossa mensagem.

C(2) ⇒ 27 ≡ 128 (mod 143)

C(3) ⇒ 37 ≡ 42 (mod 143)
C(8) ⇒ 87 ≡ 57 (mod 143)
C(9) ⇒ 97 ≡ 48 (mod 143)
C(10) ⇒ 107 ≡ 10 (mod 143)
C(11) ⇒ 117 ≡ 132 (mod 143)
C(12) ⇒ 127 ≡ 12 (mod 143)
C(22) ⇒ 227 ≡ 22 (mod 143)
C(31) ⇒ 317 ≡ 125 (mod 143)
C(42) ⇒ 427 ≡ 81 (mod 143)
C(49) ⇒ 497 ≡ 36 (mod 143)
C(72) ⇒ 727 ≡ 19 (mod 143)
C(81) ⇒ 817 ≡ 16 (mod 143)
C(83) ⇒ 837 ≡ 8 (mod 143)
C(91) ⇒ 917 ≡ 130 (mod 143)
C(102) ⇒ 1027 ≡ 119 (mod 143)

114
O RSA funciona? Seção 10.3

Temos assim os blocos da mensagem codificados:

m : 22−102−91−42−2−102−91−8−12−10−9−91−49−91−31−83−11−42−72−91−81−3−10

C(m) : 22 − 119 − 130 − 81 − 128 − 119 − 130 − 57 − 12 − 10 − 48 − 130 − 36 − 130 − 125 − 8 − 132 − 81 − 19 − 130 − 16 − 42 − 10

Passemos a decodificação de um bloco codificado. Para decodificar precisamos conhecer dois

números: n e o inverso de e módulo ϕ(n), que denotaremos por d. O par (n, d) será chamado de
chave de decodificação ou chave privada. Sendo a um bloco da mensagem codificada, denotaremos
por D(a) o resultado do processo de decodificação.

D(a) = resto da divisão de ad por n.

É muito simples calcularmos d, desde que conheçamos ϕ(n) e e, simplesmente aplicando o

algoritmo euclidiano estendido. Além disso, é necessário que sendo b um bloco da mensagem
original, tenhamos D(C(b)) = b, isto é, ao decodificar um bloco codificado, recuperemos o bloco
correspondente da mensagem original. Caso contrário, nosso código será inútil.
No exemplo que estamos usando, temos n = 143 e e = 7. Aplicaremos o algoritmo euclidiano
estendido para calcular d. Neste caso particular, os cálculos são simples, pois logo que efetuamos
a divisão de ϕ(143) = 120 por 7 encontramos

120 = 7 · 17 + 1 ⇔ 1 = 120 + (−17) · 7

ou seja, o inverso de 7 módulo 120 é -17. Como d será expoente de potências, precisamos de d > 0.
Portanto d = −17 + 120 = 103.
Por exemplo, para decodificar o bloco 8 da mensagem codificada, precisamos calcular a forma
reduzida de 8103 módulo 143.

8103 ≡ (810 )10 · 83 ≡ 1210 · 83 ≡ (122 )5 · 83 ≡ 1445 · 83 ≡ 15 · 83 ≡ 83 (mod 143)

recuperando corretamente o bloco original. Para blocos maiores, teremos dificuldade com os
cálculos se nos restringirmos à lapis e papel, faz-se necessário o uso de um sistema de computação
algébrica.

10.3 O RSA funciona?

Como observamos anteriormente, para que o RSA funcione, é necessário que ao decodificarmos
um bloco codificado da mensagem, recuperemos o bloco original. Considere um sistema RSA com
parâmetros p e q, com n = pq. Então os dados de codificação são n e e, e os de decodificação n

115
Capı́tulo 10 Criptografia RSA

e d. O que precisamos fazer é verificar se dado um inteiro b, 1 ≤ b ≤ n, temos D(C(b)) = b. Na

verdade, vamos provar apenas que D(C(b)) ≡ b (mod n), pois tanto D(C(b)) quanto b então no
intervalo de 1 à n − 1, e portanto só podem ser congruentes módulo n se forem iguais. Foi por
isso que escolhemos os blocos da mensagem original como sendo inteiros menores do que n.

Da definição de D e C temos

D(C(b)) ≡ (be )d ≡ bed (mod n) (10.1)

Mas d é o inverso de e módulo ϕ(n), e portanto existe um inteiro k de modo que ed = 1 + kϕ(n).
Substituindo em (10.1), obtemos

bed ≡ b1+kϕ(n) ≡ (bϕ(n) )k · b (mod n).

Lembrando que o teorema de Euler no diz que bϕ(n) ≡ 1 (mod n), concluı́mos que bed ≡ b (mod n),
e portanto
D(C(b)) ≡ b (mod n),

o que concluiria a demonstração, se não fosse um pequeno detalhe.

Usamos o teorema de Euler, mas este teorema tem por hipótese que mdc(b, n) = 1. Mas no
nosso caso, é dificil sabermos se isto acontece. De fato, b pode ser qualquer inteiro entre 1 e n − 1.
Precisamos, então provar a congruência sem recorrer ao teorema de Euler.

Como n = pq, com p e q primos distintos, vamos calcular a forma reduzida de bed módulo p e
módulo q. Vamos fazer os cálculos para o primo p. As contas são análogas para q. Já sabemos
que
ed = 1 + kϕ(n) = 1 + k(p − 1)(q − 1)

logo
bed ≡ b · (bp−1 )k(q−1) (mod p)

Vamos usar o teorema de Fermat. Para tanto, suponha que p não divide b. Então
bp−1 ≡ 1 (mod p), o que nos permite concluir que

bed ≡ b (mod p)

Como p é primo, no caso em que p divide b a congruência é verifficada imediatamente. Portanto

bed ≡ b (mod p) qualquer que seja b. De maneira análoga, é possı́vel mostrar que bed ≡ b (mod q)
para qualquer b.

Portanto bed − b é divisı́vel por p e por q. Como p e q são primos distintos, temos que

116
Segurança do RSA Seção 10.5

mdc(p, q) = 1, e assim pq divide bed − b. Visto que n = pq, concluı́mos que

bed ≡ b (mod n)

mostrando de fato que o método funciona. Nos resta considerar apenas sua segurança.

10.4 Segurança do RSA

Como o sistema RSA é um sistema de chave pública, precisamos saber se não é possı́vel quebrar
o sistema usando as informações disponı́veis a qualquer usuário. O par (n, e) é conhecido. O RSA
será seguro se for difı́cil calcular d se forem conhecidos apenas n e e.
Em termos práticos, para calcular d devemos aplicar o algoritmo euclidiano estendido a ϕ(n)
e e. Entretanto, só conheceremos ϕ(n) se soubermos fatorar n, para obtermos p e q. Portanto,
numa primeira análise, a quebra do sistema RSA só é possı́vel se conseguirmos fatorar n. Mas
este é um problema muito difı́cil, pois este inteiro n é grande, e não conhecemos algoritmos de
fatoração eficientes, isto é, rápidos, para inteiros do porte de n.
A única situação que ainda podemos imaginar é que alguém descubra uma maneira de encontrar
d sem ter de fatorar n, por exemplo, descobrindo um método para calcular ϕ(n) a partir apenas de
n e e. Mas se tal método existir, o que terá sido descoberto, na verdade, é um algoritmo eficiente
de fatoração.
Suponha conhecidos n e ϕ(n). Queremos determinar p e q a partir disto.
(
n = pq
ϕ(n) = (p − 1)(q − 1)

Temos duas incógnitas e duas equações. Note que

ϕ(n) = (p − 1)(q − 1) = pq − p − q + 1 = n − (p + q) + 1

de modo que p + q = n − ϕ(n) + 1 é conhecido. Além disso

(p + q)2 − 4n = (p2 + 2pq + q 2 ) − 4pq = (p − q)2

ou seja
p
p−q = (p + q)2 − 4n

também é conhecido. Conhecendo p + q e p − q, calculamos p e q, ou seja, fatoramos n. Por isso

acredita-se que quebrar o RSA e fatorar n sejam problemas equivalentes, mas até agora isso não
foi demonstrado. A questão de segurança do RSA tem outros aspectos, alguns de caráter não tão

117
Capı́tulo 10 Criptografia RSA

puramente matemáticos. Veja [03], p.187.

10.5 Comentários Finais

Ao longo deste texto vimos vários testes e algoritmos para testar se um inteiro n dado é primo ou
composto. Também vimos que para uma implementação segura do RSA, precisamos de primos p
e q grandes, para que a fatoração de n = pq seja difı́cil.
Dos testes a algoritmos que vimos, alguns são chamados de testes determinı́sticos, ou seja,
detectam com certeza se n é primo ou se n é composto, mas apresentam um defeito computacional:
são algoritmos de tempo exponencial, ou seja, seu tempo de execução cresce exponencialmente
quando o inteiro n a ser testado cresce. Por outro lado, vimos testes que são executáveis em
tempo polinomial, mas não são testes determinı́sticos, ou seja, detectam que um inteiro é primo
com certa margem de erro. Um exemplo que vimos foi o teste de Miller. Note que neste teste há
a possibilidade da saı́da do algoritmo ser ”teste inconclusivo“, e neste caso n tem chance de ser
primo.
Se você pretende escrever um programa para procurar primos grandes, com objetivo final de
implementar o RSA, você não usará testes determinı́sticos exponenciais, pois provavelmente não
estará vivo quando o algoritmo parar. O que se faz é usar testes não-determinı́sticos. No caso
do teste de Miller por exemplo, se o aplicarmos usando várias bases com saı́da inconclusiva, a
probabilidade de n ser primo é muito alta1 .
Podemos estar um pouco frustrados neste momento, visto que um matemático sempre busca
certezas irrefutáveis, e no que se refere aos testes de primalidade a serem implementados com-
putacionalmente, parecemos impotentes. Se n é um inteiro muito grande que queremos saber se
é primo ou não temos duas opções: ou usamos um teste que nos dá certeza, mas que jamais vere-
mos o resultado, por ser um teste de tempo exponencial, ou então usamos outros teste, de tempo
polinomial, mas que não garantem a primalidade de n, mas nos dão apenas uma probabilidade,
ainda que alta.
Mas algo surpreendente aconteceu em agosto de 2002, três indianos publicaram um artigo no
qual expunham um teste de primalidade determinı́stico que é executado em tempo polinomial. Os
indianos eram Agrawal, Kayal e Saxena. Assim como no caso do RSA, o algoritmo teve o nome
baseado nas iniciais de seus criadores: algoritmo AKS. Uma coisa curiosa é que dois deles haviam
terminado o curso de graduação a pouco tempo.
Vamos citar rapidamente o teorema que justifica o funcionamento do algoritmo.

1
No caso do teste de Miller, sendo n é o inteiro a ser testado, se o teste for inconclusivo para n/4 bases entre 1
e n − 1, então n necessariamente é primo. Mas essa quantidade de bases é impraticável para n grande.

118
Comentários Finais Seção 10.5

TEOREMA 10.5.1. Sejam n ≥ 2 e r ≥ 1 inteiros positivos, e seja S = {1, 2, ..., r}. Suponha que
(i) r é um primo que não divide n;

(ii) mdc(n, b − b0 ) = 1, quaisquer que sejam b e b0 distintos em S;

(iii) a desigualdade
2r − 2
√
≥ n2db (r−1)/dc
r
vale para qualquer inteiro positivo d que divide (r − 1)/ν, onde ν é a ordem de n em U (r); e

(iv) a igualdade
(x̂ + b̂)n = x̂n + b̂

é verificada em Zn [x]/(xr − 1) para cada b ∈ S.

Então n é uma potência de primo.

No enunciado, (xr − 1) denota o ideal gerado por xr − 1. Um ideal é uma estrutura algébrica
análoga aos subgrupos normais em relação a anéis. Zn [x]/(xr − 1) denota o conjunto quociente do
anel Zn [x] pelo ideal (xr − 1).

Algoritmo 10.5.2 (Algorı́tmo AKS).

Entrada: um inteiro positivo ı́mpar.

Saı́da: primo ou composto.
Etapa 1: verifique se n é um quadrado, cubo ou outra potência de um número inteiro. Se for
imprima composto e pare.
Etapa 2: Calcule
2
N = 2n(n − 1)(n2 − 1)(n3 − 1) · · · (n4dlog2 ne − 1)

e determine o menor primo r que não divide N .

Etapa 3: Verifique se n é divisı́vel por algum primo q < r. Se for, e se

• q = n, imprima primo e pare.

• q < n, imprima composto e pare.

Etapa 4: Verifique se
(x̂ + b̂)n = x̂n + b̂ em Zn [x]/(xr − 1),

para cada b ∈ S{1, 2, ..., r}. Se a congruência não for verificada para algum b ∈ S, imprima
composto e pare.
Etapa 5: Se a congruência for verificada para todo b ∈ S, imprima primo e pare.

119
Capı́tulo 10 Criptografia RSA

Para detalhes e demonstrações sobre o AKS, consulte [04]. Para encerrar, vamos deixar claro
qualquer confusão que possa surgir sobre a relação entre AKS e RSA.
O AKS é um algoritmo que verifica se um inteiro n dado é primo ou composto. Portanto, o AKS
auxilia a implementação do RSA, pois este necessita de dois primos grandes como parâmetros.
Alguém poderia pensar: se o AKS detecta primos grandes com facilidade (algoritmo determinı́stico
de tempo polinomial), então podemos usá-lo para quebrar um sistema RSA. Isso não é verdade,
pois o AKS não encontra fatores de n, apenas diz se é primo ou composto. Se temos um sistema
RSA de parâmetros p e q, temos n = pq. Se inserirmos n no algoritmo AKS, ele detectará que n
é composto, pois n = pq, mas nenhuma informação teremos a respeito de quem são os primos p e
q. Portanto deve ficar claro a diferença entre dois problemas:

1. Determinar se um inteiro é primo ou composto

2. Sendo n composto, encontrar seus fatores primos.

Para o primeiro problema, vimos vários testes e algoritmos que são eficientes. O melhor deles é
o AKS. Já o segundo parece ser um dos problemas mais difı́ceis na matemática. Como já dissemos,
não são conhecidos algoritmos eficientes (rápidos) para fatorar n se este inteiro for grande. Por
enquanto isso é bom, pois nos garante segurança para continuarmos fazendo transações bancárias
pela internet.

120
Bibliografia

[01] ALFORD, W.R., GRANVILLE, A. and POMERANCE, C. There are infinitely many
Carmichael numbers, Ann. of Math. (2), 139 (1994), no. 3, pg. 703-722.

[02] BRESSOUD, D. M. (1989) Factorization and primality testing, Undergraduate Texts in Math-
ematics, Springer-Verlag, New York.

[03] COUTINHO, S. C., Números inteiros e criptografia RSA, Coleção Matemática e Aplicações,
2a Ed., Rio de Janeiro, IMPA, 2011.

[04] COUTINHO, S. C., Primalidade em Tempo Polinomial: Uma introdução ao Algorı́tmo AKS,
Coleção Iniciação Cientı́fica, Rio de Janeiro, IMPA, 2004.

[05] EVES, H. Introdução à História da Matemática. Tradução de Higino H. Domingues. Campi-

nas, São Paulo: Unicamp, 2004.

[06] GARCIA, A., LEQUAIN, Y. Elementos de Álgebra. Projeto Euclides. 5a Ed., Rio de Janeiro,
2008.

[07] MAGRINI, L. A. Sobre Números Perfeitos, Revista do Professor de Matemática, no. 78, 2012,
pg. 16-18.

[08] NERY, C. Revisitando a Aritmética, Revista do Professor de Matemática, no. 80, 2013, pg.
31-33.

[09] RIBENBOIM, P. Existem funções que geram os números primos?, Matemática Universitária,
no. 15, 1993, pg. 1-12.

[10] SAMPAIO, J. C. V., CAETANO, P. A. S. Introdução à teoria dos números: um breve curso.
São Paulo: EDUFSCAR, 2008.

121