Buscar

Numeros Inteiros e Criptografia RSA - Coutinho

Faça como milhares de estudantes: teste grátis o Passei Direto

Esse e outros conteúdos desbloqueados

16 milhões de materiais de várias disciplinas

Impressão de materiais

Agora você pode testar o

Passei Direto grátis

Faça como milhares de estudantes: teste grátis o Passei Direto

Esse e outros conteúdos desbloqueados

16 milhões de materiais de várias disciplinas

Impressão de materiais

Agora você pode testar o

Passei Direto grátis

Faça como milhares de estudantes: teste grátis o Passei Direto

Esse e outros conteúdos desbloqueados

16 milhões de materiais de várias disciplinas

Impressão de materiais

Agora você pode testar o

Passei Direto grátis

Você viu 3, do total de 108 páginas

Faça como milhares de estudantes: teste grátis o Passei Direto

Esse e outros conteúdos desbloqueados

16 milhões de materiais de várias disciplinas

Impressão de materiais

Agora você pode testar o

Passei Direto grátis

Faça como milhares de estudantes: teste grátis o Passei Direto

Esse e outros conteúdos desbloqueados

16 milhões de materiais de várias disciplinas

Impressão de materiais

Agora você pode testar o

Passei Direto grátis

Faça como milhares de estudantes: teste grátis o Passei Direto

Esse e outros conteúdos desbloqueados

16 milhões de materiais de várias disciplinas

Impressão de materiais

Agora você pode testar o

Passei Direto grátis

Você viu 6, do total de 108 páginas

Faça como milhares de estudantes: teste grátis o Passei Direto

Esse e outros conteúdos desbloqueados

16 milhões de materiais de várias disciplinas

Impressão de materiais

Agora você pode testar o

Passei Direto grátis

Faça como milhares de estudantes: teste grátis o Passei Direto

Esse e outros conteúdos desbloqueados

16 milhões de materiais de várias disciplinas

Impressão de materiais

Agora você pode testar o

Passei Direto grátis

Faça como milhares de estudantes: teste grátis o Passei Direto

Esse e outros conteúdos desbloqueados

16 milhões de materiais de várias disciplinas

Impressão de materiais

Agora você pode testar o

Passei Direto grátis

Você viu 9, do total de 108 páginas

Faça como milhares de estudantes: teste grátis o Passei Direto

Esse e outros conteúdos desbloqueados

16 milhões de materiais de várias disciplinas

Impressão de materiais

Agora você pode testar o

Passei Direto grátis

Prévia do material em texto

Números Inteiros e Criptografia RSA
S. C. Coutinho
Universidade Federal do Rio de Janeiro
i
ii
c© by S. C. Coutinho 2014
Sumário
Agradecimentos v
Capítulo 1. Algoritmos fundamentais 1
1. Algoritmos 1
2. Algoritmo de divisão 3
3. Teorema de divisão 6
4. Algoritmo euclidiano 7
5. Demonstração do algoritmo euclidiano 10
6. Equações Diofantinas Lineares 12
7. Recreio 18
Exercícios 21
Capítulo 2. Equação de Pell 23
1. Compondo soluções 23
2. Grupos 29
3. Achando soluções 34
4. Análise do algoritmo de Brouncker 39
5. A solução fundamental 44
Exercícios 46
Capítulo 3. Grupos finitos 51
1. Inversíveis módulo n 51
2. Pell modular e suas generalizações 53
3. Subgrupos 61
4. O teorema de Lagrange 64
5. Aplicações 66
Exercícios 69
Capítulo 4. Comparando grupos 73
1. Homomorfismos 73
2. Ordem de P(d, p) 77
3. Produtos cartesianos e tabelas 80
4. Tabelas e grupos 84
5. A ordem de U(n) 86
Exercícios 89
iii
iv SUMÁRIO
Capítulo 5. Testes de primalidade 91
1. Os testes de Lucas e Lucas-Lehmer 91
2. O teste de Brilhart, Lehmer e Selfridge 96
3. A recíproca do teste de Lucas-Lehmer 98
Referências Bibliográficas 101
Agradecimentos
Muito obrigado a Gabriel da Silva Alves, Flávio Rangel, Leonardo Barrozo
pelas correções e sugestões.
v
CAPíTULO 1
Algoritmos fundamentais
São dois: o algoritmo de divisão e o algoritmo euclidiano. Ambos eram co-
nhecidos na Grécia Antiga e são descritos nos Elementos de Euclides, escrito
por volta de 300 a.C.. O algoritmo de divisão que nos interessa é o que cal-
cula quociente e resto na divisão de um número inteiro por outro. O algoritmo
euclidiano é usado para calcular o máximo divisor comum. Que são fundamen-
tais, você vai se convencer à medida que for lendo este livro.
1. Algoritmos
O Aurélio define a palavra algoritmo da seguinte maneira
processo de cálculo, ou de resolução de um grupo de problemas
semelhantes, em que se estipulam, com generalidade e sem
restrições, regras formais para a obtenção de um resultado, ou
da solução de um problema.
Como a maior parte das definições dos dicionários, esta não ajuda muito a
identificar um algoritmo, se você se deparar com um. Na verdade um algoritmo
é, essencialmente, uma receita para resolver um determinado tipo de problema.
Para ajudá-lo a entender como um algoritmo é apresentado, vamos anal-
isar com cuidado uma receita simples. Nossa tarefa é fazer um bolo. Um bom
livro de receitas tem, logo depois do nome do bolo, uma lista dos ingredientes
necessários à sua confecção. Seguem-se as instruções do que fazer com os in-
gredientes para chegar ao objetivo; coisas como: peneire, misture, bata, asse.
Finalmente, temos o resultado: o bolo pronto.
Assim é todo algoritmo. Quando formos especificar o algoritmo, deveremos
deixar claro qual é a sua entrada e a sua saída. A entrada corresponde aos
ingredientes da receita. A saída corresponde à tarefa que desejamos ver exe-
cutada; no caso acima, o bolo que desejamos fazer. O algoritmo propriamente
dito é constituído pelo conjunto de instruções da receita.
1
2 1. ALGORITMOS FUNDAMENTAIS
Tendo seguido uma receita de bolo com o devido cuidado, esperamos, ao
tirar o assador do forno, encontrar um bolo, e não um biscoito ou um bife de
panela. Também esperamos que a receita possa ser acabada em um tempo
finito, de preferência curto. Da mesma forma, tendo executado o algoritmo,
esperamos obter um resultado compatível com a saída especificada. E mais,
esperamos que o algoritmo chegue à saída ao cabo de um tempo finito, de
preferência pequeno. Assim há dois pontos a considerar. Em primeiro lugar, é
possível escrever uma sequência de instruções que continua sendo executada
para sempre. Por exemplo, dado um número inteiro qualquer (a entrada) some
1 a este número, depois some 1 ao resultado e assim por diante. Como existem
infinitos inteiros, o processo continua para sempre. Como esperamos que um
algoritmo forneça um resultado, um conjunto de instruções deste tipo não tem
nenhuma utilidade.
Por outro lado, um algoritmo pode ser lento e mesmo assim ser útil. Talvez
não haja um algoritmo melhor; ou talvez o algoritmo sirva para mostrar que o
problema tem solução. É claro que nem todo problema pode ser resolvido pela
execução de um conjunto de instruções! Menos claro é que nem todo problema
matemático pode ser resolvido desta forma–mas esta é uma outra história,
longa demais para contar aqui. Para mais detalhes sobre problemas que não
podem ser resolvidos usando algoritmos veja [9].
Podemos enunciar um algoritmo como um fato ou teorema: dada tal entrada
existe uma maneira (o algoritmo) de produzir tal saída. Um teorema normal-
mente é enunciado na forma ‘se valem as hipóteses então temos a tese’. No caso
do teorema associado a um algoritmo, a entrada do algoritmo corresponde às
hipóteses do teorema, e a saída à tese.
Não se preocupe se estes comentários lhe parecem muito vagos, estamos
apenas estabelecendo a nomenclatura. Àmedida que os exemplos forem surgindo
tudo vai ficar mais claro. Resumindo o que já dissemos: um algoritmo é uma
receita, um conjunto de instruções que toma certos ingredientes (a entrada) e
transforma num certo produto (a saída). Digamos que alguém nos apresenta
um conjunto de instruções e afirma que se trata de um algoritmo para exe-
cutar determinada tarefa. Somos, então, moralmente obrigados a fazer duas
perguntas:
• ao executar estas instruções, sempre chegaremos a um resultado?
• o resultado obtido é sempre o desejado?
Com isto em mente, faremos uma análise cuidadosa do algoritmo de divisão.
2. ALGORITMO DE DIVISÃO 3
A etimologia da palavra algoritmo é tão curiosa que seria uma pena encer-
rar a seção sem mencioná-la. Originalmente a palavra era escrita algorismo,
que vem da forma latinizada do árabe Al-Khowarazmi, ‘o homem de Khowarazm’.
Assim era conhecido o matemático árabe BenMusa, que viveu no século IX. Foi
através de seu livro ‘Al-jabr wa’l muqabalah‘ que os algarismos indo-arábicos
chegaram ao Ocidente. Aliás algorismo e algarismo são variantes da mesma
palavra e significavam originalmente os numerais indo-arábicos. Por extensão
algorismo era também usado para significar aritmética e cálculo com números.
Algoritmo ganhou um ‘t’ por influência da palavra ‘aritmos’–que também sig-
nifica número, só que em grego.
O sentido atual da palavra algoritmo, contudo, é bem mais recente, sendo
atestado, em inglês, apenas a partir de 1812. Não é claro como a palavra chegou
a ter este sentido. É possível testemunhá-la adquirindo um significado mais
abrangente no artigo de 1684 em que Leibniz apresenta, pela primeira vez,
sua versão do cálculo diferencial e integral. No começo deste artigo Leibniz
diz que as regras do cálculo que vai apresentar podem ser consideradas como
um ‘algoritmo’. Em pouco mais de um século a palavra já havia praticamente
tomado o sentido atual. Gauss, escrevendo em latim, usa ‘algoritmus’ repetidas
vezes em suas Disquisitiones Arithmeticæ quando se refere a um conjunto de
fórmulas que constitui um método para calcular a solução de algum problema
aritmético.
Assim algoritmo é uma palavra muito antiga, mas que ganhou um signifi-
cado novo. Em tempo: do nome do livro de Ben Musa, mencionado acima, vem
a nossa palavra álgebra.
2. Algoritmo de divisão
Vamos analisar o algoritmo de divisão na forma estabelecida na seção an-
terior. Em primeiro lugar, só estamos interessados na divisão de um inteiro
por outro, a divisão com resto. Portanto, nossa tarefa é achar o quociente e
o resto da divisão entre dois inteiros positivos. Ao ouvir isto você imaginará
certamente algo assim
1234 54
154 22
46
Neste exemplo estamos dividindo 1234 por 54 e encontramos o quociente 22
e o resto 46. Na linguagem da seção anterior, o algoritmo tem por entrada o
4 1. ALGORITMOS FUNDAMENTAIS
dividendo e o divisor–neste caso 1234 e 54.A saída são o quociente e o resto–
neste caso 22 e 46.
De umamaneira geral, a entrada do algoritmo de divisão são os dois inteiros
positivos a e b, que desejamos dividir. A saída são outros dois inteiros q e r,
que estão relacionados à entrada de maneira que
a = bq+ r e 0 ≤ r < b,
como sabemos desde o primário. Falando em primário, é bom relembrar a inter-
pretação do algoritmo que aprendemos naquela época. Imagine que temos uma
barra de chocolate de comprimento a e que queremos obter o maior número
possível de pedaços de comprimento b dividindo a barra. A resposta é que
obteremos q pedaços e uma ‘sobra’ que terá comprimento r.
A barra de chocolate é a inspiração para o algoritmo mais simples possível
para achar q e r, a partir de a e b. Simples, mas não eficiente. Na verdade
trata-se de um algoritmo altamente ineficiente. Podemos descrevê-lo assim.
ALGORITMO 2.1 (Algoritmo de divisão). Entrada: inteiros positivos a e b.
Saída: inteiros positivos q e r tais que a = bq+ r e 0 ≤ r < b.
Etapa 1: Comece fazendo Q = 0 e R = a.
Etapa 2: Se R < b escreva o quociente é Q e o resto é R e pare; senão vá para a
Etapa 3.
Etapa 3: Se R ≥ b subtraia b de R, incremente Q de 1 e volte à Etapa 2.
Ao longo deste livro os algoritmos serão frequentemente estruturados na
forma descrita acima. A leitura correta das instruções pressupõe algumas con-
venções. Observe que o algoritmo usa duas variáveis, Q e R. Os nomes das
variáveis foram escolhidos por razões mnemônicas: ao final da execução do al-
goritmoQ vai ser o valor do quociente e R o valor do resto na divisão de a por b.
Para determinar estes valores teremos geralmente que executar as instruções
das Etapas 2 e 3 várias vezes: chamamos a isto um laço. Ao final de cada laço
as variáveis Q e R terão valores diferentes. A mudança de valor é efetuada na
Etapa 3. A instrução subtraia b de R significa: à variável R será atribuído um
novo valor que corresponde ao valor que tinha ao final do laço anterior menos
b. Analogamente incremente Q de 1 significa: à variável Q será atribuído o
valor que tinha ao final do laço anterior mais 1.
Por exemplo, se a > b, então tendo passado uma vez pela Etapa 3 obtivemos
Q = 1 e R = a − b. Se a − b ≥ b então o algoritmo nos manda aplicar a Etapa
3 mais uma vez. Tendo feito isto, teremos obtido Q = 2 e R = a − 2b. E assim
2. ALGORITMO DE DIVISÃO 5
por diante. Por que isto não se repete para sempre? Ou, em outras palavras,
por que é que o algoritmo pára? Observe que aplicando a Etapa 3 várias vezes
geramos a seguinte sequência de valores da variável R:
valor inicial 1o laço 2o laço 3o laço . . .
a a− b a− 2b a− 3b . . .
Trata-se de uma sequência decrescente de números inteiros. Como existe
apenas uma quantidade finita de inteiros entre a e 0, a sequência acima vai
chegar eventualmente a um valor menor que b. Neste momento a Etapa 2 nos
manda encerrar o processo e divulgar a resposta. Logo o algoritmo sempre
pára.
Que o resultado da aplicação do algoritmo corresponde às especificações da
saída é fácil de ver. Note que se q e r são obtidos pelo algoritmo então, auto-
maticamente, temos r = a− bq e r < b. Da primeira equação segue facilmente
que a = bq + r. Falta apenas descobrir porque r ≥ 0. Pelo que vimos acima, o
algoritmo parou no laço de número q. Logo no laço anterior (que é q− 1) temos
a− b(q− 1) ≥ b ou não estaríamos subtraindo b mais uma vez para chegar ao
laço q. Subtraindo b de ambos os membros desta última equação chegamos a
a− bq ≥ 0, que é o que queríamos verificar. Logo o algoritmo descrito realiza o
que dele se pede.
Não é preciso pensar muito para ver que o algoritmo apresentado é muito
lento. O número de laços executados é igual ao quociente; assim, se a for
muitas ordens de grandeza maior que b, estamos perdidos. O método usual
de divisão oferece uma maneira prática de acelerar este algoritmo. Infeliz-
mente este método (como costumamos usá-lo) é excelente para seres humanos
dividirem números pequenos e péssimo quando os números são grandes ou o
calculista é uma máquina.
Para entender o porquê da observação acima vamos acompanhar os cálculos
na divisão do começo da seção. Em primeiro lugar escolhemos o menor número
formado pelos algarismos de 1234 (começando da esquerda) que é maior que
54. Este número é 123. Fazemos, então, a pergunta: ‘qual o maior inteiro que
posso multiplicar por 54 e ainda assim obter um produto menor que 123?’ E
é nesta pergunta que reside o problema. Se os números são pequenos, um
pouco de experiência e algumas tentativas nos levam rapidamente ao valor
correto. Se os números são grandes, nossa experiência é inútil, e a quantidade
de possibilidades pode tornar impossível atacar o problema por tentativa. Há
uma saída para este impasse, mas discuti-la aqui nos levaria a uma digressão
muito longa. Para mais detalhes sobre esta questão consulte o livro [22, §4.3].
6 1. ALGORITMOS FUNDAMENTAIS
Antes de encerrar a seção precisamos considerar um problema prático. A
maior parte dos resultados abordados neste livro só se torna interessante se
os números a que se aplicam são ‘relativamente grandes’; grandes o bastante
para tornar o cálculo de divisões com lápis e papel impraticável. Isto sem falar
no fato de que teremos de executar dezenas de divisões na solução de alguns
problemas. A saída é usar uma máquina de calcular. Mas máquina de calcular
não faz divisão com resto–ou faz? Imagine que temos dois inteiros positivos
a e b e desejamos calcular a expressão decimal da fração a/b. O começo da
divisão é exatamente igual ao da divisão com resto. Só que ao invés de parar
e escrever o resto, colocamos a vírgula decimal e continuamos a dividir. Moral:
a parte inteira da expressão decimal de a/b é o quociente da divisão com resto
de a por b. Se o quociente é q então o resto é simplesmente a − bq; e achamos
quociente e resto com uma calculadora. Se a calculadora tem memória é muito
fácil executar esta conta (com um pouco de prática) em tempo recorde.
Mas cuidado: o tamanho dos inteiros a serem divididos está limitado pelo
número máximo de algarismos que o visor da calculadora aceita (normalmente
oito ou dez). Talvez você esteja pensando que isto não é um grande problema.
Afinal sua calculadora escreverá números de até 99 algarismos em notação
científica; isto é na forma r · 10n, onde 1 ≤ r < 10. O problema é que precis-
aremos conhecer o quociente exatamente. Mas se sua calculadora está usando
notação científica isto normalmente significa que a parte inteira do quociente
está sendo truncada.
3. Teorema de divisão
Na seção 1 também mencionamos que todo algoritmo vem acompanhado
de um teorema. Vamos enunciar o teorema correspondente ao algoritmo de
divisão.
TEOREMA DE DIVISÃO. Teorema de divisão Sejam a e b inteiros positivos.
Existem números inteiros q e r tais que
a = bq+ r e 0 ≤ r < b.
Além disso, os valores de q e r satisfazendo as relações acima são únicos.
No enunciado acima, o que vem antes do ‘além disso’ não oferece surpresa.
Que, dados a e b, existem q e r já sabemos. Sabemos até como calculá-los us-
ando o algoritmo descrito acima. O que vem depois do ‘além disso’ é que é a
novidade. O que quer dizer que os valores são únicos? Imagine que escolhemos
dois inteiros positivos a e b e os distribuímos a várias pessoas com a instrução
de que determinem (do jeito que bem desejarem) inteiros q e r satisfazendo as
4. ALGORITMO EUCLIDIANO 7
relações do teorema. A unicidade do quociente e do resto significa que todas es-
tas pessoas encontrarão os mesmos valores. Em particular algoritmos distintos
para calcular quociente e resto não podem achar valores distintos, o que é uma
informação muito útil.
Vejamos porque isto é verdade. Digamos que escolhemos dois inteiros pos-
itivos a e b. Entregamos estes números a duas pessoas, Carlos e Sofia, e ped-
imos que determinem quociente e resto satisfazendo as condições do teorema.
Carlos encontrouq e r e Sofia q ′ e r ′. Sabendo apenas que
a = bq+ r e 0 ≤ r < b
e que
a = bq ′ + r ′ e 0 ≤ r ′ < b
mostraremos que q = q ′ e r = r ′. Lembre-se que r e r ′ são inteiros; logo um
deles é maior ou igual ao outro. Para fixar as idéias, digamos que r ≥ r ′. Da
equação de Carlos r = a − bq e da equação de Sofia r ′ = a − bq ′. Subtraindo
uma da outra
r− r ′ = (a− bq) − (a− bq ′) = b(q ′ − q).
Por outro lado, tanto r quanto r ′ são menores que b. Como estamos supondo
também que r ≥ r ′, obtemos 0 ≤ r− r ′ < b. Comparando com r− r ′ = b(q ′ − q)
concluímos que
0 ≤ b(q ′ − q) < b.
Mas b é um inteiro positivo e pode ser cancelado, logo 0 ≤ q ′−q < 1. Como q ′−q
é um número inteiro, estas desigualdades só se verificam quando q ′ −q = 0, ou
seja q = q ′. Disto segue imediatamente que r = r ′, e verificamos a unicidade.
Recapitulando, vimos que o algoritmo de divisão dá lugar a um teorema
que nos diz duas coisas: que o quociente e o resto sempre existem, e que o
quociente e o resto são únicos. Muitos outros teoremas que estudaremos neste
curso afirmarão existência e unicidade de certas condições. O mais importante
deles será o teorema da fatoração única a ser estudado no próximo capítulo.
4. Algoritmo euclidiano
O objetivo do algoritmo euclidiano é calcular o máximo divisor comum en-
tre dois números inteiros. Mesmo correndo o risco de parecer pedante, vamos
definir cuidadosamente o que deve ser entendido por máximo divisor comum.
Em primeiro lugar um inteiro b divide outro inteiro a se existe um outro
número inteiro c tal que a = bc. Também dizemos que b é um divisor ou fator
de a, ou ainda que a é múltiplo de b. Todas estas expressões significam a
mesma coisa. O número c, na definição acima é chamado de co-fator de b em
8 1. ALGORITMOS FUNDAMENTAIS
a. Na prática, determinamos que b divide a efetuando a divisão e verificando
que o resto é zero. O co-fator é o quociente da divisão.
Suponhamos que temos dois inteiros positivos a e b. O máximo divisor
comum entre a e b é o maior inteiro positivo d que é divisor de a e também
é divisor de b. Se d é o máximo divisor comum entre a e b, escrevemos d =
mdc(a, b). Se mdc(a, b) = 1, dizemos que os números são primos entre si.
Um livro da quarta série primária descreve a seguinte maneira de calcu-
lar o máximo divisor comum entre a e b. Primeiro calcule todos os divisores
de a; depois todos os divisores de b. Foram obtidos dois conjuntos: calcule
a intersecção dos dois. O maior número inteiro contido na intersecção é o
máximo divisor comum desejado. O que há de errado nisto? Nada; mas se
precisássemos recorrer a este método para calcular o máximo divisor comum,
nunca chegaríamos a usá-lo para nada. Infelizmente, achar todos os divisores
de um inteiro é totalmente impraticável quando o número é grande, mesmo
usando um bom computador. Discutiremos isto com detalhes no próximo capí-
tulo. Milagrosamente existe uma outra maneira de calcular o máximo divisor
comum através de um algoritmo muito eficiente. Este algoritmo é descrito por
Euclides nas proposições 1 e 2 do Livro 7 dos Elementos, mas acredita-se que
sua origem seja muito anterior a Euclides.
Digamos, mais uma vez, que a e b sejam inteiros positivos e que a ≥ b.
Queremos calcular o máximo divisor comum entre a e b. O algoritmo euclid-
iano consiste em dividir a por b, achando o resto r1. Se r1 6= 0, dividimos b
por r1, obtendo o resto r2. Se r2 6= 0, dividimos r1 por r2, obtendo o resto r3. E
assim por diante. O último resto diferente de zero desta sequência de divisões
é o máximo divisor comum entre a e b. Quando o cálculo do máximo divisor
comum é feito com lápis e papel, é costume arrumar as divisões em um quadro.
No exemplo abaixo, calculamos o máximo divisor comum entre 1234 e 54.
1234 | 54 | 46 | 8 | 6 | 2
46 | 8 | 6 | 2 | 0
No quadro acima escrevemos apenas os restos das divisões. Os quocientes
não são usados diretamente no cálculo do máximo divisor comum. De acordo
com a regra exposta no parágrafo anterior, temos que mdc(1234, 54) = 2, que
é o último resto não nulo da sequência de divisões. Temos então o algoritmo:
para calcular o máximo divisor comum tudo o que temos a fazer é calcular
uma sequência de divisões. Mas porquê o resultado destas divisões é o máximo
4. ALGORITMO EUCLIDIANO 9
divisor comum? Além disso, precisamos verificar que a sequência de divisões
chega sempre a um resto zero, ou o algoritmo continuaria para sempre.
Começaremos tratando a segunda questão. Portanto, verificaremos primeiro
que o algoritmo sempre pára. Digamos que, para calcular o máximo divisor co-
mum entre a e b, fazemos uma sequência de divisões como abaixo.
a = bq1 + r1 e 0 ≤ r1 < b
b = r1q2 + r2 e 0 ≤ r2 < r1
r1 = r2q3 + r3 e 0 ≤ r3 < r2
r2 = r3q4 + r4 e 0 ≤ r4 < r3
... . . .
...
Esqueça por um instante o que está acontecendo na coluna da esquerda. À
direita temos uma sequência de restos, e observamos que o seguinte é sempre
menor que o anterior mas todos são maiores ou iguais a zero. Escrevendo as
desigualdades dos restos uma em seguida à outra,
(1) b > r1 > r2 > r3 > r4 · · · ≥ 0.
Como entre b e 0 há apenas uma quantidade finita de inteiros, esta sequência
não pode continuar indefinidamente. Mas ela só chega ao final se um dos restos
for zero, e é isto que garante que o algoritmo sempre pára.
Podemos usar o argumento do parágrafo anterior para determinar qual o
número máximo de divisões que precisamos fazer para chegar ao máximo di-
visor comum. Considere novamente a sequência de restos (4.1). Cada resto é
estritamente menor que o anterior. Assim, o maior resto possível numa certa
divisão é igual ao resto anterior menos 1. Se isto acontecer em cada uma das
divisões, teremos que executar b divisões até chegar a um resto igual a zero, e
este seria o pior caso possível. Logo o número de divisões a serem executadas
em cada caso é no máximo b.
Na verdade, podemos mostrar que o número máximo de divisões é sem-
pre menor que b (exceto quando b ≤ 3). É preferível formular o problema da
seguinte maneira: quais os menores valores (positivos) de a e b para os quais
é preciso efetuar n divisões a fim de calcular que mdc(a, b) ? Para que a e b
sejam os menores possíveis é preciso que os quocientes de cada divisão sejam
os menores possíveis. O menor quociente possível na divisão de dois números
positivos é 1. Suponhamos que foram efetuadas n divisões para chegar ao resto
10 1. ALGORITMOS FUNDAMENTAIS
zero. Assim a sequência de restos é
r1 > r2 > r3 > . . . rn−1 > rn = 0.
Mas já vimos que no pior caso possível o quociente entre quaisquer dois restos
consecutivos tem que ser 1. Escrevendo as divisões do fim para o começo obte-
mos então
rn−2 = rn−1 · 1
rn−3 = rn−2 · 1+ rn−1
rn−4 = rn−3 · 1+ rn−2
· · ·
a = b · 1+ r1
Para fixar as idéias, digamos que rn−1 = 1 e que n = 10, a sequência de
restos fornecida pelas equações acima (escrita em ordem decrescente) é então:
34, 21, 13, 8, 5, 3, 2, 1, 1, 0.
Assim, os menores valores de a e b para os quais temos que efetuar n divisões
a fim de calcular mdc(a, b) (e descobrir que vale 1) são a = 34 e b = 21. Observe
que mesmo b sendo o menor possível neste caso, ainda assim temos b = 21 que
é muito maior que n = 10. A sequência obtida acima é a famosa sequência de
Fibonacci; que aparece também no exercício 5.
5. Demonstração do algoritmo euclidiano
Vimos assim que o algoritmo sempre pára–e executa no máximo tantas di-
visões quanto o menor dos números de que se quer calcular o máximo divisor
comum. Mas por que é que o último resto não nulo coincide com o máximo
divisor comum? Para entender isto precisamos de um resultado auxiliar, o que
os matemáticos costumam chamar de lema. A palavra vem do grego e significa
‘alguma coisa que é assumida’ a fim de se provar um teorema.
LEMA 5.1. Sejam a e b números inteiros positivos. Suponhamos que existam
inteiros g e s tais que a = bg+ s. Então mdc(a,b) = mdc(b, s).
Precisamos mostrar que a afirmação contida no lema é verdadeira. Antes
de fazer isto, porém, usaremos o lema para provar que o último resto não nulo
da sequência de divisões é o máximo divisor comum. Aplicando o algoritmo a
a e b e supondo que o resto nulo ocorre após n divisões, temos
5. DEMONSTRAÇÃO DO ALGORITMO EUCLIDIANO 11
a = bq1 + r1 e 0 ≤ r1 < b(2)
b = r1q2 + r2 e 0 ≤ r2 < r1
r1 = r2q3 + r3 e 0 ≤ r3 < r2
r2 = r3q4 + r4 e 0 ≤ r4 < r3
... . . .
...
rn−4 = rn−3qn−2 + rn−2 e 0 ≤ rn−2 < rn−3
rn−3 = rn−2qn−1 + rn−1 e 0 ≤ rn−1 < rn−2
rn−2 = rn−1qn e rn = 0
Desta vez podemos ignorar a coluna da direita; vamos nos concentrar no
que ocorre à esquerda. Da última divisão temos que rn−1 divide rn−2. Logo o
maior divisor comum entre os dois é o próprio rn−1. Portanto mdc(rn−2, rn−1) =
rn−1.
Aqui entra em ação o lema. Aplicando-o à penúltima divisão, concluímos
que
mdc(rn−3, rn−2) = mdc(rn−2, rn−1)
que, por sua vez, é igual a rn−1. Aplicando novamente o lema, desta vez à
ante-penúltima divisão, temos
mdc(rn−4, rn−3) = mdc(rn−3, rn−2)
que já vimos que é igual a rn−1. Continuando assim, coluna acima, chegamos
finalmente a mdc(a, b) = rn−1; que é o que desejávamos verificar.
Para que não fique nenhum detalhe faltando na nossa prova de que o algo-
ritmo funciona, falta apenas demonstrar o lema. O lema nos diz que assumindo
que a, b, g e s estão relacionados por a = bg + s devemos ser capazes de con-
cluir que mdc(a, b) = mdc(b, s). Fica mais fácil explicar a demonstração se
supusermos que
d1 = mdc(a, b) e d2 = mdc(b, s).
Até aqui não fizemos nada: apenas demos nome aos respectivos máximos di-
visores comuns. Com esta notação, o que queremos mostrar é que d1 = d2.
Provaremos isto em duas etapas, verificando que d1 ≤ d2 e em seguida que
d2 ≤ d1. Destas duas desigualdades segue a igualdade desejada.
12 1. ALGORITMOS FUNDAMENTAIS
Provaremos que d1 ≤ d2; a outra desigualdade é provada demaneira análoga
e fica por sua conta. Lembre-se que d1 = mdc(a, b). Assim d1 divide a e d1 di-
vide b. De acordo com a definição isto significa que existem inteiros u e v tais
que
a = d1u e b = d1v.
Vamos substituir estas expressões para a e b na relação a = bg + s, que é um
dos dados do lema. Obteremos d1u = d1vg+ s, ou seja
s = d1u− d1vg = d1(u− vg).
Mas isto significa que d1 divide s. Recapitulando: como d1 = mdc(a, b) temos,
em particular, que d1 divide b. Com um cálculo mostramos que d1 também
divide s. Portanto d1 é um divisor comum entre b e s. Mas d2 é o maior divisor
comum entre b e s. Logo d1 ≤ d2, que é o que devíamos provar.
Voltando ao enunciado do lema, observe que precisamos da relação a =
bg+ s, que é análoga à relação entre dividendo, divisor, quociente e resto; mas
não precisamos saber que s é menor que b. Portanto o fato do resto ser menor
que o divisor não é usado para mostrar que o último resto não nulo é o máx-
imo divisor comum. Entretanto precisamos desta condição quando mostramos
que o algoritmo pára. Assim as duas condições do algoritmo de divisão são
necessárias para provar que o algoritmo euclidiano funciona.
6. Equações Diofantinas Lineares
Como vimos na seção ??, as equações diofantinas mais simples são da forma
(3) ax + by = c,
em que a, b e c são inteiros dados e x e y são inteiros a serem determinados.
Em outras palavras, uma solução desta equação é um par de inteiros (x, y) que
satisfaz (3). Começamos mostrando que as soluções de uma equação diofantina
linear estão relacionadas ao máximo divisor comum dos coeficientes que mul-
tiplicam as variáveis x e y.
Sejam x0 e y0 inteiros e suponhamos que o par (x0, y0) é uma solução de (3).
Se d for o máximo divisor comum entre a e b, então existem inteiros a ′ e b ′ tais
que
a = d · a ′ e b = d · b ′.
Substituindo isto em ax0 + by0 = c, obtemos
c = (d · a ′)x0 + (d · b ′)y0 = d(a ′x0 + b ′y0).
Como as hipóteses que fizemos guarantem que a ′x0+b ′y0 é um número inteiro,
então d tem que dividir c. Resumindo, mostramos que se ax + by = c tem
6. EQUAÇÕES DIOFANTINAS LINEARES 13
solução inteira, então o máximo divisor comum entre a e b tem que dividir c.
De partida, isto nos permite concluir que existem muitas equações diofantinas
lineares sem solução; por exemplo, toda vez que a e b forem números pares e c
for ímpar, a equação ax + by = c não terá solução inteira.
Ainda que seja interessante saber que há equações diofantinas lineares sem
solução, o que gostaríamos mesmo de fazer é resolver aquelas que têm solução.
Como vimos na seção anterior, nem sempre isto é possível. Contudo, no caso
das equações diofantinas lineares há um algoritmo simples e capaz de gerar
todas as soluções destas equações. Dados números inteiros positivos a e b, o
algoritmo que vamos descrever determina dois números inteiros α e β tais que
(4) α · a+ β · b = d,
em que d é o máximo divisor comum de a e b. Observe que, a não ser que a
divida b ou vice-versa, o máximo divisor comum d será menor do que ambos,
a e b, de modo que α ou β terá que ser um inteiro negativo. Para resolver a
equação ax + by = c quando d divide c, multiplicamos (4) pelo cofator c ′ de d
em c, obtendo
(5) (c ′α) · a+ (c ′β) · b = c ′ · d = c;
de modo que o par (c ′α, c ′β) é solução de ax+ by = c.
O procedimento que vamos descrever é conhecido como algoritmo euclidi-
ano estendido, porque, tendo como entrada inteiros positivos a e b, executa o
algoritmo euclidiano usual, juntamente com fórmulas que nos permitem cal-
cular inteiros α e β que satiszem (4). A versão que apresentaremos deve-se
a D.E. Knuth, autor de uma série de livros chamada The art of computer pro-
gramming, que é considerada a bíblia da teoria de algoritmos; veja [22].
A implementação inventada pelo Knuth é bastante sutil e consiste em escr-
ever cada um dos restos obtidos na sequência de divisões do algoritmo euclid-
iano em termos de a e b, usando fórmulas semelhantes a (4). Como veremos
a seguir, a grande vantagem em proceder desta maneira é que, para efetuar
os cálculos correspondentes a uma determinado laço, basta guardar os dados
referentes aos dois laços imediatamente anteriores. Tudo o mais pode ser apa-
gado, o que mantém uma área maior de memória disponível.
Digamos que, calculando o máximo divisor comum entre a e b, obtemos
a sequência de divisões (5.1). Reescrevemos esta sequência abaixo, acrescen-
tando ao lado de cada divisão a relação entre o resto que acabamos de calcular
14 1. ALGORITMOS FUNDAMENTAIS
e os inteiros a e b:
a = bq1 + r1 e r1 = ax1 + by1(6)
b = r1q2 + r2 e r2 = ax2 + by2
r1 = r2q3 + r3 e r3 = ax3 + by3
r2 = r3q4 + r4 e r4 = ax4 + by4
... . . .
...
rn−3 = rn−2qn−1 + rn−1 e rn−1 = axn−1 + byn−1
rn−2 = rn−1qn e rn = 0.
Como estamos supondo que que rn = 0, mas rj 6= 0 para todo 1 ≤ j ≤ n, então
d = mdc(a, b) = rn−1.
Logo,
rn−1 = axn−1 + byn−1
nos permite concluir que α = xn−1 e β = yn−1 satisfazem (4).
Os números x1, . . . , xn−1 e y1, . . . , yn−1 são inteiros a determinar e é conve-
niente condensar a informação contida em (6.2) na tabela 1.
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
TABELA 1. Algoritmo euclidiano estendido aplicado a a e b
A primeira coisa que você vai observar é que introduzimos duas linhas no
começo da tabela que ‘legalmente’ não deviam estar lá. Estas linhas não cor-
respondem a nenhuma divisão. Afinal nem a, nem b são restos. Chamaremos
estas linhas de −1 e 0, refletindo assim seu caráter ‘fora da lei’. Logo veremos
porque são necessárias.
6. EQUAÇÕES DIOFANTINAS LINEARES 15
O que queremos, então, fazer? Queremos descobrir como preencher as col-
unas x e y. Vamos imaginar, por um momento, que já recebemos a tabela
preenchida até um determinado ponto: até a (j − 1)-ésima linha, por exemplo.
Começamos a preencher a j-ésimalinha dividindo rj−2 por rj−1 para achar rj e
qj, de forma que rj−2 = rj−1qj + rj e 0 ≤ rj < rj−1. Assim
(7) rj = rj−2 − rj−1qj.
Lendo nas linhas j−1 e j−2 os valores de xj−2, xj−1, yj−2 e yj−1, podemos escrever
rj−2 = axj−2 + byj−2 e rj−1 = axj−1 + byj−1.
Substituindo estes valores em (6.3), obtemos
rj = (axj−2 + byj−2) − (axj−1 + byj−1)qj = a(xj−2 − qjxj−1) + b(yj−2 − qjyj−1).
Portanto
xj = xj−2 − qjxj−1 e yj = yj−2 − qjyj−1.
Observe que, para calcular xj e yj, usamos apenas valores contidos nas duas
linhas imediatamente anteriores à linha j, além do quociente qj. Concluindo:
sabemos como preencher qualquer linha da tabela, desde que as duas linhas
que a precedem sejam conhecidas.
Temos assim um processo que nos permite, dadas duas linhas da tabela, de-
terminar a imediatamente seguinte. Portanto, basta descobrirmos como achar
as duas primeiras linhas da tabela e saberemos como preenchê-la completa-
mente, obtendo assim os valores de α e β desejados. É aqui que entram em
jogo as duas linhas ilegais que introduzimos no início da tabela. A razão pela
qual estão lá é que é muito fácil calcular os valores de x e y nestes dois casos.
Interpretando estas linhas como as demais, deveremos ter
a = ax−1 + by−1 e b = ax0 + by0;
que nos sugere escolher
x−1 = 1, y−1 = 0, x0 = 0 e y0 = 1;
como valores iniciais a partir dos quais todos os outros valores de x e y podem
ser determinados.
Vejamos um exemplo numérico. Tomando a = 1234 e b = 54 como na seção
4 do capítulo 1, teremos a tabela 2.
Portanto, α = −7 e β = 160 e
(−7) · 1234+ 160 · 54 = 2.
Como sempre, precisamos analisar este algoritmo para saber porque pára
e porque funciona. Mas, como seu nome sugere, este novo algoritmo é apenas
uma extensão do algoritmo original. Assim, além da sequência de divisões,
16 1. ALGORITMOS FUNDAMENTAIS
resto quociente x y
1234 * 1 0
54 ∗ 0 1
46 22 1− 22 · 0 = 1 0− 22 · 1 = −22
8 1 0− 1 · 1 = −1 1− 1 · (−22) = 23
6 5 1− 5 · (−1) = 6 −22− 5 · 23 = −137
2 1 −1− 1 · 6 = −7 23− 1 · (−137) = 160
0 3 ∗ ∗
TABELA 2. Algoritmo euclidiano estendido aplicado a 1234 e 54
estamos fazendo cáculos adicionais para determinar os valores de x e y a cada
passo. Como o algoritmo euclidiano pára, este também tem que parar. Por
outro lado, os valores de α e β obtidos ao final são apenas o x e y da última linha
da tabela. Logo (6.1) é verificada porque a condição análoga é satisfeita para
os valores de x e y correspondentes a cada linha da tabela. Observe, também,
que, na prática, não há necessidade de executar as duas colunas da tabela
acima porque, tendo calculado α e d que satisfazem (4), podemos facilmente
encontrar o valor de β usando a fórmula
β =
d− α · b
b
.
Formulando o algoritmo euclidiano estendido como um teorema, temos o seguinte
resultado.
TEOREMA 6.1. Sejam a e b inteiros positivos e seja d o máximo divisor co-
mum entre a e b. Existem inteiros α e β tais que
α · a+ β · b = d.
Voltando a nosso problema original, vejamos como usar o algoritmo eu-
clidiano estendido para resolver qualquer equação diofantina linear. Dada a
equação ax + by = c, aplicamos o algoritmo euclidiano estendido a a e b ob-
tendo seu máximo divisor comum d e inteiros α e β tais que αa + βb = d. Se
d não divide c, então a equação não terá solução e nada mais há a fazer. Por
outro lado, se d divide c, então calculamos o cofator c ′ de d em c e deduzimos
de (5) que o par (c ′α, c ′β) é solução de ax + by = c.
Observe que tomamos cuidado em dizer que o par de inteiros assim calcu-
lado é solução, mas não a solução. A razão para isto é simples: uma equação
diofantina linear que tem uma solução, obrigatoriamente terá uma quantidade
6. EQUAÇÕES DIOFANTINAS LINEARES 17
infinita de soluções. Para provar isto, suponhamos que o par (x0, y0) é solução
de ax + by = c; de modo que
ax0 + by0 = d.
Se a ′ e b ′ são os cofatores de d em a e b, respectivamente, então
kab ′ = k(da ′)b ′ = ka ′(ab ′) = ka ′b.
Logo, dado um número inteiro k qualquer, teremos que
a(x0 + kb
′) + b(y0 − ka
′) = (ax0 + by0) + (kab
′ − ka ′b) = d.
Podemos, assim, concluir que:
se (x0, y0) é solução de ax + by = c e k é um inteiro qualquer,
então (x0+kb ′, y0−ka ′) também é solução da mesma equação.
Também é verdade que todas as soluções de ax + by = c são da forma acima,
mas a demonstração terá que esperar até chegarmos à seção ???? do capítulo
????.
Vejamos como aplicar o algoritmo que acabamos de descrever para resolver
a equação diofantina 2356293x+26928y = 21, começamos aplicando o algoritmo
euclidiano estendido, que resumimos na tabela 3.
resto Quociente x
2356293 ** 1
26928 ** 0
13557 87 1
13371 1 - 1
186 1 2
165 71 - 143
21 1 145
18 7 - 1158
3 1 1303
0 * *
TABELA 3. Algoritmo euclidiano estendido aplicado a 2356293 e 26928
de modo que d = 3 e α = 1303, donde
1303 · 2356293+ β · 26928 = 3.
18 1. ALGORITMOS FUNDAMENTAIS
Resolvendo esta equação linear em uma variável, descobrimos que β = −114017.
Como 21 = 3 · 7, multiplicamos
1303 · 2356293+ (−11401726928) · 26928 = 21.
por 7, obtendo:
(1303 · 7) · 2356293 ·+(−11401726928 · 7) · 26928 = 21.
como os cofatores de 3 em 2356293 e 26928 são, respectivamente 785431 e 8976,
então a solução geral da equação
2356293x+ 26928y = 21,
é dada por
x = (1303 · 7) + k · 8976
y = (−114017 · 7) − k · 785431,
qualquer que seja o inteiro k.
7. Recreio
Vamos concluir nosso estudo das equações diofantinas lineares analisando
como podem ser utilizadas para resolver alguns problemas de caráter recre-
ativo, frequentemente encontrados em livros de matemática. Contudo, nosso
interesse pelas equações diofantinas vai muito além dos problemas de caráter
recreativo que elas nos permite resolver. Na verdade, alguns dos principais re-
sultados que estudaremos requerem a solução de equações diofantinas, entre
eles o algoritmo de criptografia RSA. Mas vamos aos problemas.
PROBLEMA 7.1. Determine todos os múltiplos de 12354 e de 7854 cuja soma
seja 18?
Começamos modelando o problema em termos de uma equação diofantina.
Para isto, denotamos os múltiplos aos quais o problema se refere por 53213x e
72131y, em que x e y representam números inteiros. Usando esta terminologia,
o problema corresponde à equação
(8) 12354x+ 7854y = 18.
Aplicando o algoritmo euclidiano estendido a 12354 e de 7854, obtemos a tabela
4.
Como mdc(12354, 7854) = 6, que divide 18, o termo constante da equação,
então a equação tem solução. Para encontrá-las, usamos α = 281 e
β =
6− 281 · 12354
7854
= −442,
7. RECREIO 19
resto quociente x
12354 ** 1
7854 ** 0
4500 1 1
3354 1 - 1
1146 1 2
1062 2 - 5
84 1 7
54 12 - 89
30 1 96
24 1 - 185
6 1 281
TABELA 4. Algoritmo euclidiano estendido aplicado a 12354 e 7854
que satisfazem
α · 12354+ β · 7854 = 6.
Multiplicando esta última equação por 3, obtemos
(3α) · 12354+ (3β) · 7854 = mdc(12354, 7854) = 18.
A solução geral de (8) é, então,
3 · 281+ 1306k e − 3 · 442− 2059k.
Os múltiplos desejados são, portanto,
12354(3 · 281+ 1306k) e 7854(−3 · 442− 2059k).
Nosso segundo problema também é recorrente nos livros de matemática
recreativa, mas sua solução modelagem e solução em termos de equações dio-
fantinas é bemmais elaborada que o anterior. Isto se dá porque sua formulação
natural requer aritmética modular, tópico que só estudaremos no capítulo ???.
PROBLEMA 7.2. Determine omenor inteiro positivo que deixe resto 2 quando
dividido por 28 e resto 5 quando dividido por 17.
Chamando de n o número a ser determinado, usamos o Teorema da Divisão
para escrever
(9) n = 28q1 + 2 = 17q2 + 7,
20 1. ALGORITMOS FUNDAMENTAIS
em que q1 e q2 são inteiros positivos que representam os quocientes das di-
visões de n por 3 e 7, respectivamente. Note que não podemos usar o mesmo
símbolo para denotar s quocientes de ambas as divisões porque não há nen-
huma razãopara acreditar que sejam iguais. Mas, da igualdade (9), segue-se
que
0 = (17q2 + 7) − (28q1 + 2) = 17q2 − 28q2 + 5.
Tomando x = −q2 e y = q1, obtemos, a partir do problema proposto, a equação
(10) 28x+ 17y = 5.
O que não é imediatamente aparente é que uma solução desta última equação
nos permite resolver o problema original. Mas, para isto, basta repetir, de trás
para a frente, os cálculos que fizemos para chegar a (10). Digamos que x0 e y0
são inteiros positivos tais que
28x0 + 17y0 = 5.
Como 5 = 7− 2, então,
28x0 − 17(−y0) = −7+ 2,
donde obtemos que o número
(11) n = 28x0 + 2 = 17(−y0) + 7
satisfaz as condições do problema. Contudo, para que n seja um número pos-
itivo, precisa ser possível escolher x0 > 0 e y0 < 0. Para implementar este
procedimento, aplicamos o algoritmo euclidiano estendido a 28 e 17, obtendo a
tabela 5.
restos quocientes x
28 ** 1
17 ** 0
11 1 1
6 1 - 1
5 1 2
1 1 - 3
0 5 17
TABELA 5. Algoritmo euclidiano estendido aplicado a 28 e 17
Portanto,
28 · (−3) + 17 · β = 1,
EXERCÍCIOS 21
donde β = 5. Multiplicando esta equação por 5, obtemos
28 · (−15) + 17 · 25 = 5.
Contudo, não podemos escolher x0 = −15 e y0 = 25, porque não satisfazem a
condição x0 > 0 e y0 < 0 que havíamos estabelecido anteriormente. Contor-
namos este problema, usando a solução geral de 28x+ 17y = 5, pode ser escrita
na forma:
x = −15+ 17k e y = 25− 28k.
Para que existam soluções x0 e y0 satisfazendo as condições desejadas, deve
existir um inteiro k0 tal que
x0 = −15+ 17k0 > 0 e y0 = 25− 28k0 < 0.
Mas, da primeira inequação, k0 > 15/17, ao passo que da segunda inequação
k0 > 25/28. Como qualquer k0 > 1 satisfaz as duas desigualdades, teremos de
(11) que
n = 28(−15+ 17k0) + 2 = 17(−25+ 28k0) + 7
é um inteiro positivo que deixa resto 2 na divisão por 28 e resto 7 na divisão por
17, qualquer que seja o inteiro k0 > 0. Como o problema pede o menor inteiro
que satisfaz estas condições, devemos escolher k0 = 1, o que nos dá que
n = 28 · 2+ 2 = 17 · 3+ 7 = 58
é a solução desejada.
Exercícios
1. Para cada par a, b de números inteiros abaixo, calcule o máximo divisor
comum e determine α, β de modo que mdc(a, b) = α · a+ β · b.
(a) 14 e 35
(b) 252 e 180
(c) 6643 e 2873
(d) 272828282 e 3242
2. Sendo n um número inteiro maior que 1, verifique as seguintes igualdades:
(a) mdc(n, 2n+ 1) = 1
(b) mdc(2n+ 1, 3n+ 1) = 1
(c) mdc(n! + 1, (n+ 1)! + 1) = 1
3. Sejam n > m inteiros positivos. Mostre que se o resto da divisão de n por
m é r então o resto da divisão de 2n − 1 por 2m − 1 é 2r − 1.
4. Sejam n > m inteiros positivos. O objetivo desta questão é calcular mdc(22
n
+
1, 22
m
+ 1).
22 1. ALGORITMOS FUNDAMENTAIS
(a) Usando que 22
m+1
− 1 = (22
m
+ 1)(22
m
− 1), mostre que 22
n
− 1 é múltiplo
de 22
m
+ 1 quando n > m. Qual o quociente desta divisão?
(b) Usando (1), mostre que o resto da divisão de 22
n
+ 1 por 22
m
+ 1 é 2.
(c) Usando (2), determine mdc(22
n
+ 1, 22
m
+ 1).
O resultado deste exercício será usado no exercício 8 do capítulo 3.
5. Na sequência de Fibonacci 1, 1, 2, 3, 5, 8, 13 . . . , cada número depois do primeiro
é soma dos dois anteriores. Denotando por fn o n-ésimo termo da sequência
temos portanto que
fn = fn−1 + fn−2,
e que f0 = f1 = 1.
(a) Mostre que o máximo divisor comum de dois termos consecutivos da
sequência de Fibonacci é sempre 1.
(b) Quantas divisões são necessárias para calcular mdc(fn, fn−1)?
6. Sejam a e b inteiros positivos. O mínimo múltiplo comum de a e b é o
menor inteiro positivo que é múltiplo de a e que é múltiplo de b. Vamos
denotar este número por mmc(a, b). Mostre que
mmc(a, b) =
ab
mdc(a, b)
.
7. Escreva um programa que, tendo como entrada dois inteiros a e b, deter-
mina o máximo divisor comum de a e b. Adapte o seu programa para gerar
aleatoriamente pares de inteiros a e b e calcular o mdc(a, b). O programa
deve ter como entrada o número total de pares que você deseja testar, e
como saída o quociente
total de pares cujo mdc é 1
total de pares testados
.
Este quociente dá uma medida da probabilidade de que um par de in-
teiros escolhido aleatoriamente seja co-primo. Vai ser necessário deixar
o programa testar um número muito grande de pares para obter uma boa
aproximação da probabilidade. Execute o programa dez vezes para cada
valor escolhido para a entrada. Faça uma tabela com esses valores, tendo
como entrada 10, 100, 1000, 10000 e 100000 pelo menos. Usando argumen-
tos de teoria da probabilidade é possível mostrar que, testando um número
grande de pares, o quociente acima deve ficar próximo de 6/π2; veja [16, p.
16]. Como é que este valor se compara aos resultados experimentais que
você obteve?
CAPíTULO 2
Equação de Pell
Neste capítulo estudaremos a equação de Pell. Como vimos na seção ??
da introdução, esta equação diofantina vem sendo investigada desde a an-
tiguidade e existe uma teoria bastante desenvolvida acerca das suas soluções.
Começaremos considerando o método utilizado pelos matemáticos indianos
para gerar novas soluções, a partir de outras duas já conhecidas. Na seção
seguinte, veremos que este método pode ser interpretado como uma operação
no conjunto das soluções da equação de Pell, o que nos levará à definição de
grupo abeliano e ao estudo de algumas de suas propriedades mais elementares.
Finalmente, nas duas últimas seções, descrevemos um algoritmo capaz de
achar uma solução de uma equação de Pell e provamos que sempre para e
que funciona corretamente.
1. Compondo soluções
Como vimos na introdução, a equação de Pell é a equação diofantina
x2 − dy2 = 1
em que d é um número inteiro. Se x0 e y0 são números inteiros tais que
x20 − dy
2
0 = 1,
dizemos que o par (x0, y0) é uma solução de x2 − dy2 = 1. Como as variáveis x
e y aparecem ambas ao quadrado na equação, sempre que o par (x0, y0) é uma
solução de x2 − dy2 = 1, o mesmo vale para
(12) (−x0, y0), (x0,−y0), e (−x0,−y0).
Observe, também, que, não importa qual seja o valor de d, a equação de Pell
sempre tem os pares (±1, 0) como soluções. Estas são as chamadas soluções
triviais e são as únicas soluções possíveis quando d é um inteiro negativomenor
que −1. Já no caso em que d = −1, a equação tem outras duas soluções, a saber
(0,±1). Uma versão devidamente decupada da demonstração destes fatos pode
ser encontrada nos exercícios 3 e 4.
23
24 2. EQUAÇÃO DE PELL
Um caso mais interessante é aquele em que d é um quadrado perfeito. Dig-
amos que d = r2, para algum inteiro positivo r. Então,
1 = x2 − dy2 = x2 − r2y2 = x2 − (ry)2 = (x− ry)(x+ ry).
Mas o produto dos número inteiros x−ry e x+ry só pode ser igual a 1 se ambos
os termos forem iguais a 1, ou ambos forem iguais a −1. Obtemos, assim, os
sistemas lineares
x− ry = 1 x− ry = −1
x+ ry = 1 x + ry = −1,
cujas soluções são, respectivamente, (1, 0) e (−1, 0). Portanto, também neste
caso a equação tem apenas as soluções triviais. Mais detalhes podem ser en-
contrados no exercício 5.
Levando em conta as considerações dos dois últimos parágrafos, há apenas
um caso em que ainda não sabemos resolver a equação de Pell: aquele em que d
é um inteiro positivo, mas não é um quadrado perfeito. Mesmo neste caso, não
é difícil advinhar soluções para a equação quando d é pequeno. Por exemplo,
o par (2, 1) é claramente uma solução para x2 − 3y2 = 1. Uma solução não
trivial para x2 − 2y2 = 1 não é tão óbvia mas, depois de algumas tentativas,
verificamos que o par (3, 2) é uma tal solução. Com um pouco de paciência, os
casos em que d = 5, 6, 7, 8 e 11 podem ser resolvidos da mesma maneira. Já
d = 13 é bem mais complicado, porque a solução cujas entradas são as menores
possíveis, em valor absoluto, é (649, 180).
Como os matemáticos indianos do século VII já sabiam, é possível obter
infinitas soluções de uma dada equação de Pell a partir de qualquer soluçãonão trivial. Para isto usavam a fórmula de Brahmagupta
(13) (xu+ dyv)2 − d(xv + yu)2 = (x2 − dy2)(u2 − dv2),
que já consideramos na introdução. Se x1, y1, x2 e y2 forem inteiros que satis-
fazem
x21 − dy
2
1 = x
2
2 − dy
2
2 = 1,
então, por (13),
(x1x2 + dy1y2)
2 − d(x1y2 + y1x2)
2 = 1.
Em outras palavras, se (x1, y1) e (x2, y2) são soluções da equação de Pell x2 −
dy2 = 1, então
(14) (x1x2 + dy1y2, x1y2 + y1x2)
também é solução da mesma equação.
Por exemplo, como os pares (2, 1) e (−1, 0) são soluções de x2−3y2 = 1, então
podemos combiná-los usando a fórmula (14), obtendo assim que o par (−2,−1)
1. COMPONDO SOLUÇÕES 25
também é solução da mesma equação. Mas isto, convenhamos, não é muito
interessante porque já sabíamos que (±2,±1) são todas elas soluções de x2 −
3y2 = 1. Combinar (2, 1) e (1, 0) é ainda menos interessante, porque o resultado
é o próprio par (2, 1). Antes que você comece a pensar que a fórmula (14) não
é, afinal, tão útil, convém lembrar que há uma possibilidade que ainda não
exploramos: aquela que consiste em combinar (2, 1) com ele mesmo. Fazendo
isto, obtemos o par (7, 4), que é uma solução genuinamente diferente de todas
as anteriores. Isto sugere duas novas possibilidades. A primeira consiste em
combinar (7, 4) com ele mesmo, donde resulta o par (97, 56); já na segunda,
combinamos (2, 1) com (7, 4), obtendo (26, 15).
Como você deve ter notado, seria mais conveniente se tivéssemos umamaneira
mais compacta de expressar as aplicações da fórmula (14) do que a utilizada no
parágrafo anterior. O ideal seria uma notação que nos informasse, de maneira
clara e direta, quais são os pares que estão sendo combinados e qual o par re-
sultante da aplicação da fórmula. Naturalmente, há várias maneiras possíveis
de fazer isto. A que utilizaremos terá consequências significativas em nosso
estudo da equação de Pell.
Para começar, dado um inteiro d, definimos o conjunto solução da equação
de Pell x2 − dy2 = 1 como sendo o conjunto de todos os pares de inteiros (x, y)
que satisfazem aquela equação. Denotando este conjunto por P(d), podemos
escrever
P(d) = {(x, y) ∈ Z× Z | x2 − dy2 = 1}.
Lembre-se que os elementos do produto cartesiano A×B entre dois conjuntosA
e B são os pares (a, b) em que a ∈ A e b ∈ B. No caso acima, estamos listando
apenas os pares que satisfazem a condição imposta pela equação de Pell. A
propósito, já sabemos que P(d) nunca é vazio, porque (±1, 0) ∈ P(d), qualquer
que seja o inteiro d.
Tendo introduzido P(d), podemos interpretar a identidade (13) como uma
maneira de combinar dois elementos de P(d) de modo a obter um novo ele-
mento de P(d). Usando a terminologia usual, o que fizemos foi definir uma
operação no conjunto P(d), para a qual usaremos a notação ⊗. Assim, dadas
duas soluções σ1 = (x1, y1) e σ2 = (x2, y2) da equação de Pell x2 − dy2 = 1,
definimos
(15) σ1 ⊗ σ2 = (x1x2 + dy1y2, x1y2 + y1x2).
A identidade (13) nos garante que, como σ1, σ2 ∈ P(n) então σ1 ⊗ σ2 ∈ P(d).
Usando esta notação, os cálculos com soluções de x2 − 3y2 = 1 que fizemos no
26 2. EQUAÇÃO DE PELL
início desta seção podem ser resumidos da seguinte forma:
(2, 1)⊗ (−1, 0) = (−2,−1) (7, 4)⊗ (7, 4) = (97, 56)
(2, 1)⊗ (2, 1) = (7, 4) (2, 1)⊗ (7, 4) = (26, 15).
Para falar a verdade, também vimos que
(2, 1)⊗ (1, 0) = (2, 1)
e as equações acima sugerem outras combinações que podemos tentar, como
(−1, 0)⊗ (2, 1) e (7, 4)⊗ (2, 1). Entretanto, se você efetuar os cálculos correspon-
dentes, verá que a troca nas posições dos pares não afeta em nada o resultado.
Estes últimos comentários escondem propriedades gerais da operação ⊗,
que convém explicitar para que possamos usá-las livremente em nosso estudo
das equações de Pell. As propriedades são as seguintes. Em primeiro lugar,
uma aplicação direta de (15) nos dá
se e = (1, 0) e σ é um elementos qualquer de P(d), então σ⊗e =
σ;
isto é, o par (1, 0), que denotaremos a partir de agora por e, funciona como
elemento neutro para a operação ⊗. Por outro lado, a comutatividade da soma
e da multiplicação de números inteiros implica que
quaisquer que sejam σ1, σ2 ∈ P(d) teremos σ1 ⊗ σ2 = σ2 ⊗ σ1;
de modo que ⊗ também é comutativa. Uma outra propriedade, que não encon-
tramos anteriormente, é a seguinte: se σ = (x0, y0) ∈ P(d), então σ = (x0,−y0)
satisfaz
(16) σ⊗ σ = (x0, y0)⊗ (x0,−y0) = (1, 0);
de modo que σ, que também pertence a P(d), funciona como uma espécie de
inverso de σ.
Apesar das propriedades que já identificamos simplificarem em muito nos-
sos cálculos com soluções de uma equação de Pell, ainda deixam problemas
bastante simples sem solução. Por exemplo, dado σ ∈ P(d), podemos definir
seu quadrado σ2 como sendo σ⊗ σ e seu cubo σ3 como sendo
σ⊗ σ2 ou σ2 ⊗ σ;
já que são iguais pela propriedade comutativa. Mas como definir σ4? A primeira
impressão é que a resposta é óbvia; basta tomar
σ⊗ σ3 = σ3 ⊗ σ.
1. COMPONDO SOLUÇÕES 27
Entretanto, neste caso, também poderíamos definir σ4 como σ2 ⊗ σ2, que não
sabemos se é ou não igual a σ ⊗ σ3. Verificamos, assim, que, embora a co-
mutatividade de ⊗ basta para podermos definir o cubo de uma solução sem
ambiguidade, o mesmo não se dá com a quarta potência. Para podermos lidar
com ela, precisamos mostrar que
σ1 ⊗ (σ2 ⊗ σ3) = (σ1 ⊗ σ2)⊗ σ3, quaisquer que sejam σ1, σ2, σ3 ∈
P(d).
Esta propriedade, conhecida como associativa, nos dá a garantia de que, não
importa como agrupemos os termos de um produto em uma multiplicação, o
resultado sempre será o mesmo. De todas as propriedades básicas da operação
que definimos em P(d) esta é a mais complicada de provar, porque os cálcu-
los são longos e requerem atenção; mas não são difíceis, razão por que vamos
deixá-los por sua conta. Para confirmar que a associatividade era o ingredi-
ente que faltava para eliminar a ambiguidade na definição da quarta potência,
verificaremos que se σ ∈ P(d) então
σ⊗ σ3 = σ2 ⊗ σ2.
Começamos observando que
σ⊗ σ3 = σ⊗ (σ⊗ σ2),
pois σ3 = σ⊗ σ2. Mas, pela associatividade,
σ⊗ (σ⊗ σ2) = (σ⊗ σ)⊗ σ2,
que é igual a σ2 ⊗ σ2, como desejávamos mostrar.
Não podemos encerrar esta questão sem mostrar que a operação de multi-
plicação de soluções de uma equação de Pell admite uma linda interpretação
geométrica. Em primeiro lugar, o conjunto de todos os pontos com coordenadas
reais que satisfazem a equação x2 − dy2 = 1 é uma hipérbole. Por exemplo,
quando d = 2 a hipérbole correspondente é ilustrada na figura 1.
FIGURA 1. A hipérbole x2 − 2y2 = 1
28 2. EQUAÇÃO DE PELL
Para multiplicar duas soluções P1 e P2 da equação de Pell x2 − dy2 = 1 de
maneira puramente geométrica começamos determinando a reta r, paralela ao
segmento que une P1 a P2, e que passa pelo ponto e = (1, 0). Como a equação de
Pell tem grau dois, esta reta terá que intersectar a hipérbole em um segundo
ponto, que será o produto desejado; veja Exercício 14. Queremos mostrar que
esta construção produz o ponto P1⊗ P2. Para isto, suporemos que P1 = (x1, y1) e
que P2 = (x2, y2). A reta que passa por P1 e P2 tem coeficiente angular
(17) α =
y2 − y1
x2 − x1
.
Por outro lado, temos de (15) que a reta por e = (1, 0) e P1 ⊗ P2 tem coeficiente
angular
β =
x1y2 + x2y1
x1x2 + dy1y2 − 1
.
Para que estas duas retas sejam paralelas, é necessário que α = β, que equiv-
ale a dizer que
(x1y2 + x2y1)(x2 − x1) = (x1x2 + dy1y2 − 1)(y2 − y1).
Contudo, um cálculo simples mostra que
(x1y2+x2y1)(x2−x1)−(x1x2+dy1y2−1)(y2−y1) = −dy1y
2
2+dy
2
1y2−x
2
1y2+y2+x
2
2y1−y1,
que podemos reescrever na forma
(18) y1(−dy22 + x
2
2 − 1) + y2(−x
2
1 + dy
2
1 + 1).
Entretanto, como P1 e P2 são, por hipótese, soluções da equação de Pell x2 −
dy2 = 1, teremos que
x21 − dy
2
1 = 1 e que x
2
2 − dy
2
2 = 1
donde segue, imediatamente, que a expressão (18) é nula, confirmando, assim,
que α = β, como queríamos mostrar.
A despeito do que acabamosde provar, se tentarmos esboçar a figura corre-
spondente ao cálculo do quadrado do ponto (2, 1) ∈ P(3) vamos ter uma amarga
surpresa. Afinal, para isso, teríamos que aplicar a construção geométrica com
P1 = P2. Contudo, neste caso, a fórmula para o coeficiente angular dada em
(17) não faz sentido. Por sorte podemos contornar isto de maneira bastante
simples, porque à medida que o ponto P2 se aproxima do ponto P1, a secante vai
se aproximando cada vez mais da tangente, como ilustra a figura 2. Isto sug-
ere que a solução do problema está em substituir, na construção geométrica, a
secante através de P1 e P2, pela tangente em P1. Entretanto, isto requer que
determinemos a inclinação m, em um dado ponto P, da tangente à hipérbole
x2 − dy2 = 1. Se você sabe um pouco de cálculo diferencial, não terá dificul-
dade em verificar que se y0 6= 0, entãom = x0/dy0; se não sabe, encontrará um
2. GRUPOS 29
bA
FIGURA 2. A tangente no ponto A (linha cheia) como limite das secantes
roteiro de como provar isto no exercício 14. A figura 3 ilustra a representação
geométrica do cálculo do quadrado de (2, 1) em P(3).
b
e
b
B
b
C
FIGURA 3. C = (7, 4) é o quadrado do ponto B = (2, 1)
2. Grupos
Vimos na seção anterior que, dada uma equação de Pell, é possível definir
uma operação no conjunto das suas soluções. Além disso, esta operação satisfaz
várias das propriedades que estamos acostumados a associar à soma e à multi-
plicação de números, sejam eles inteiros, reais ou complexos. A frequência com
que uma operação definida em um dado conjunto satisfaz estas propriedades é
tanta que os matemáticos usam o termo grupo para indicar sua presença.
30 2. EQUAÇÃO DE PELL
Um grupo é constituído de dois ingredientes básicos: um conjunto e uma
operação definida neste conjunto. Vamos chamar o conjunto de G e a operação
de ⋆. Por operação estamos entendendo uma regra que a cada dois elemen-
tos a, b ∈ G associa um terceiro elemento a ⋆ b que também está em G. As
operações mais conhecidas são, certamente, a soma, a subtração e a multipli-
cação definidas nos conjuntos de números inteiros, racionais e reais. Outros
exemplos de operações com os quais você já deve ter se deparado são a soma
e o produto de matrizes e a soma de vetores do plano. Observe, contudo, que
nem tudo que, em matemática, chamamos de operação é coberto pela definição
acima. Por exemplo, o produto escalar de dois vetores do plano associa a um par
de vetores um número, não um vetor; ao passo que, segundo nossa definição, a
cada par de elementos de um conjunto, a operação deve associar um elemento
do mesmo conjunto. Para chamar a atenção para este fato, diremos que a op-
eração de um grupo tem que ser fechada no sentido de que combina elementos
de um conjunto e retorna um outro elemento do mesmo conjunto. Com isto
estamos prontos para a definição oficial de grupo.
Um conjunto G no qual está definida uma operação ⋆ é um grupo se, quais-
quer que forem os elementos a, b, c ∈ G, a operação satisfaz as seguintes pro-
priedades:
fechamento: a ⋆ b ∈ G;
associatividade: a ⋆ (b ⋆ c) = (a ⋆ b) ⋆ c;
comutatividade: a ⋆ b = b ⋆ a;
elemento neutro: existe e ∈ G tal que a ⋆ e = a;
elemento inverso: dado a ∈ G, existe a1 ∈ G tal que a ⋆ a1 = e.
Para ser honesto, a definição usual de grupo não inclui a comutatividade da
operação. Um grupo cuja operação é comutativa, como será o caso de todos
os exemplos neste livro, é conhecido como grupo abeliano. Contudo, dado que
só estamos interessados em grupos abelianos, podemos omitir o adjetivo sem
incorrer em nenhuma confusão, o que simplifica nossa terminologia. Outra
coisa: precisamos de um verbo que faça o papel da expressão combinar dois
elementos do conjunto G pela operação ⋆. Como “estrelar” soa muito estranho,
usaremos multiplicar, a não ser quando a operação for a soma ou a subtração,
para as quais já existem os verbos somar e subtrair.
Uma boa maneira de nos certificarmos de que entendemos um novo conceito
é buscando objetos matemáticos que exemplifiquem este conceito, assim como
objetos para os quais alguma das propriedades requeridas não é satisfeita. Por
2. GRUPOS 31
exemplo, os números inteiros, racionais, reais e complexos são grupos relativa-
mente à operação de soma e o mesmo vale para os vetores do plano e as ma-
trizes 2×2. Por outro lado, os inteiros não constituem um grupo relativamente
à subtração, porque esta operação não é associativa, nem comutativa, nem tem
elemento neutro; veja exercício 15. Quando a operação é a multiplicação, nen-
hum dos conjuntos de números mencionados acima é um grupo, porque 0 não
tem inverso multiplicativo; isto é, não existe nenhum número que multiplicado
por 0 dê como resultado 1. Embora, os números racionais, reais e complexos
não nulos formem um grupo para a multiplicação usual, o mesmo não se dá
com os inteiros, já que os únicos inteiros que admitem inversos multiplicativos
são 1 e −1.
A menos dos exemplos mencionados acima, e que você já conhecia, mesmo
sem saber que eram grupos, o único outro grupo com o qual trabalharemos
neste capítulo é o que introduzimos na seção anterior; isto é, o conjunto P(d)
das soluções inteiras da equação de Pell x2 − dy2 = 1, com a operação definida
pela fórmula (15). Contudo, mais exemplos podem ser encontrados exercícios
16 e 17. Embora um grupo devesse sempre ser designado pelo par formado
pelo conjunto e a operação, seguiremos a tradição de não mencionar a operação
quando ela estiver implícita no contexto. Por exemplo, como definimos apenas
uma operação no conjunto das soluções da equação de Pell x2 − dy2 = 1, vamos
nos referir a este grupo apenas como P(d), e não como (P(d),⊗).
Uma coisa que as propriedades das operações de um grupo nos permitem
fazer é resolver equações simples. Por exemplo, se (G, ⋆) é um grupo e a, b ∈ G,
podemos nos perguntar se existe um elemento x ∈ G que satisfaça a equação
(19) a ⋆ x = b.
Como todo elemento de um grupo tem inverso, tem que existir um elemento
a1 ∈ G tal que a1 ⋆ a = e. Multiplicando a equação (19) por a1, obtemos
a1 ⋆ (a ⋆ x) = a1 ⋆ b.
Levando em conta que ⋆ é associativa, a equação acima equivale a
(a1 ⋆ a) ⋆ x = a1 ⋆ b.
Mas
(a1 ⋆ a) ⋆ x = e ⋆ x = x;
de modo que
x = a1 ⋆ b.
Mostramos, assim, que em qualquer grupo, toda equação da forma a ⋆ x = b
tem solução, e que esta solução é sempre igual a a1⋆b. Por exemplo, para achar
32 2. EQUAÇÃO DE PELL
o elemento S ∈ P(3) que satisfaz
S⊗ (7, 4) = (−2, 1),
multiplicamos os dois lados da equação pelo inverso de (7, 4) que, pela equação
(16) é (7,−4), obtendo
S⊗ (7, 4)⊗ (7,−4) = (−2, 1)⊗ (7,−4);
de modo que
S = (−2, 1)⊗ (7,−4) = (−26, 15).
Há um outro tipo de problema que podemos resolver em um grupo e que
é especialmente importante do ponto de vista da criptografia mas, antes de
enunciá-lo, precisamos definir potências de um elemento em um grupo. Como
vimos na seção anterior, a associatividade de uma operação garante que o re-
sultado de um produto de elementos independente da maneira como escolhe-
mos agrupá-los quando efetuamos o cálculo. Isto nos permite definir a potência
de um dado elemento a, de um grupo (G, ⋆), por um expoente inteiro positivo k
como
ak = a ⋆ · · · ⋆ a︸ ︷︷ ︸
k vezes
.
Por exemplo, nossos cálculos anteriores mostram que no grupo P(3),
(2, 1)2 = (7, 4), (2, 1)3 = (26, 15) e (2, 1)4 = (97, 56).
Segue diretamente desta definição e da associatividade da operação ⋆ que, se k
e ℓ são inteiros positivos, então
(20) ak ⋆ aℓ = ak+ℓ e (ak)ℓ = akℓ.
Estas fórmulas, por sua vez, sugerem que deveríamos definir a0 como sendo o
elemento neutro de G, que denotaremos por e. Para entender porquê, observe
que tomando ℓ = 0 na primeira das fórmulas em (20), obtemos
ak ⋆ a0 = ak+0 = ak.
Mas, multiplicando a equação acima pelo inverso de ak, concluímos que
e ⋆ a0 = e.
Como e ⋆ a0 = a0 pela definição do elemento neutro, temosque a0 = e, como
havíamos afirmado. Com isto estamos prontos para enunciar o problema men-
cionado no início deste parágrafo.
PROBLEMA DO LOGARITMO DISCRETO. Dados a e b em um grupo G, existe
algum inteiro k tal que bk = a?
2. GRUPOS 33
Talvez você se surpreenda pelo uso da palavra logaritmo neste problema,
mas a escolha é bastante adequada. Afinal de contas, se a e b fossem números
reais, o número real k que satisfaz bk = a seria o logaritmo de a na base b. Ao
contrário das equações lineares, que sempre têm solução qualquer que seja o
grupo e os elementos a e b que escolhermos, o problema do logaritmo discreto
nem sempre tem solução. Além disso, e esta é a parte importante em crip-
tografia, ainda que o problema tenha solução, pode ser extremamente difícil
obtê-la. A segurança do algoritmo de criptografia conhecido como El Gamal,
por exemplo, baseia-se na dificuldade de resolver o problema do logaritmo dis-
creto em certos grupos; veja Exercício ??? do capítulo ???.
A noção de potência nos permite mostrar que P(3) é um conjunto infinito.
Para provar isto, analisaremos o que acontece quando comparamos as coorde-
nadas de um dado par P = (a, b) com as do seu quadrado. Usando a fórmula
(15), verificamos que
P2 = (a2 + 3b2, 2ab).
Mas, se a e b são ambos positivos, então
a < a2 + 3b2 e b < 2ab.
Em outras palavras, as coordenadas de P2 são ambas maiores que as respecti-
vas coordenadas de P. Denotaremos isto escrevendo
P < P2.
Note que esta desigualdade implica que as coordenadas de P2 também têm que
ser positivas, de forma que o mesmo argumento aplicado a P2 garante que
P2 < P4;
e assim por diante. Em outras palavras, temos que se as coordenadas de P são
positivas, então a sequência
P < P2 < P4 < P8 < · · · < P2k < · · ·
tem que ser infinita, porque as coordenadas de qualquer um dos seus pares têm
que ser maiores que as do seu antecessor. Logo, escolhendo P = (2, 1), obtemos
uma sequência infinita de pares distintos em P(3), provando o que desejáva-
mos. Se você está familiarizado com o princípio de indução finita, vai identi-
ficar esta demonstração como uma aplicação mal disfarçada deste método; caso
contrário, talvez você queira reler este argumento depois de estudar o capítulo
??.
Para completar nossa análise da equação de Pell falta, apenas, descobrir
como achar uma solução de x2 − dy2 = 1 no caso em que o inteiro positivo d
não é um quadrado perfeito. É claro que podemos fazer isto na base da força
bruta. Por exemplo, incrementamos y de um em um, calculando o valor de
34 2. EQUAÇÃO DE PELL
√
1+ dy2 correspondente. Teremos achado uma solução da equação quando
encontrarmos um y para o qual x =
√
1+ dy2 é número inteiro. O problema
deste algoritmo é que só temos certeza de que funciona se já soubermos que
toda equação de Pell para a qual d não é quadrado perfeito sempre tem solução
com entradas positivas. Na próxima seção descreveremos um outro algoritmo,
muito menos ingênuo que a busca proposta acima, e que seremos capazes de
provar que sempre para, retornando uma solução da equação de Pell que lhe
foi dada como entrada.
3. Achando soluções
Nesta seção completamos nossa análise da equação de Pell, descrevendo
um algoritmo que, tendo como entrada um inteiro positivo d, que não é um
quadrado perfeito, retorna uma solução da equação de Pell x2 − dy2 = 1. Na
forma em que vamos apresentá-lo este algoritmo foi descrito em uma carta de
JohnWallis, em que ele explica a solução de um problema proposto por Fermat.
Segundo Wallis, o algoritmo teria sido descoberto por William Brouncker. Na
verdade, uma versão do mesmo algoritmo, conhecido como método cíclico, era
conhecida dos matemáticos indianos desde o século XII, embora os matemáti-
cos europeus que estudaram a equação não tivessem conhecimento disto. Seguindo
os passos de Wallis, vamos descrever nesta seção o método cíclico como ideal-
izado por Brouncker e executar um exemplo passo a passo. No final da seção
enunciamos o método na forma de um algoritmo, cuja demonstração detalhada
será feita na próxima seção. Este algoritmo ilustra um fato surpreendente,
mas comum em matemática: um problema mais geral pode ser mais fácil de
resolver que um de seus casos especiais.
Digamos que d > 0 é um inteiro positivo que não é um quadrado perfeito e
seja
(21) x2 − dy2 = 1
a equação de Pell que queremos resolver. Diremos que uma solução de (21) é
positiva se suas coordenadas são inteiros maiores que zero. Se (u0, v0) é uma
solução positiva desta equação, então
u20 = dv
2
0 + 1 > v
2
0,
de modo que u0 > v0. Portanto, ao dividir u0 por v0, obteremos
u0 = v0q+ r em que r > 0.
Substituindo esta expressão para u0 na equação (21) e expandindo o produto
notável, podemos concluir que (v0, r) é solução da equação diofantina
(q2 − d)x2 + 2qxy + y2 = 1.
3. ACHANDO SOLUÇÕES 35
Como v0, q e r são inteiros positivos, (v0, r) só pode ser solução desta equação
se d > q2. Por isso, vamos reescrevê-la na forma
(22) (d− q2)x2 − 2qxy − y2 = −1,
já que isto faz com que o coeficiente do termo quadrático em (22) seja positivo
quando d > q2. O ponto crucial deste argumento é que 0 ≤ r < v0 porque, se
pudermos iterar o procedimento acima, obteremos equações com soluções em
inteiros cada vez menores, reduzindo assim o problema a outro mais fácil de
resolver. Infelizmente, há um obstáculo óbvio à implementação desta ideia. O
problema é que o par (v0, r), obtido quando substituímos u0 = v0q + r em u0 −
dv20 = 1, é solução de (22), que não é, nemmesmo, uma equação de Pell. A saída
consiste em ampliar o escopo das equações que estamos tentando resolver, de
modo a incluir tanto (21), quanto (22).
Seguindo os passos de Brouncker, devemos considerar equações da forma
(23) Ax2 − 2Bxy − Cy2 = ±1,
em queA, B e C são inteiros positivos. Se (u0, v0) for uma solução desta equação
e q e r forem inteiros positivos tais que u0 = v0q + r então, substituindo esta
última expressão em (23), obtemos
(24) (Aq2 − 2Bq− C)y2 + 2(Aq− B)ry +Ar2 = ±1.
Note que precisamos que q seja positivo, pois se q = 0, então r = u0 e a substi-
tuição em nada alteraria a equação dada. Brouncker propôs escolher q como o
maior inteiro para o qual Aq2 − 2Bq − C < 0. Com isso o coeficiente de y2 em
(24) é necessariamente negativo. Assim, multiplicando (24) por −1 e tomando
A1 = −(Aq
2 − 2Bq − C), B1 = Aq− B e C1 = A
obtemos a equação
A1y
2 − 2B1yr− C1r
2 = ∓1.
Note a inversão do sinal do lado direito da equação. Como C1 = A > 0 por
hipótese e A1 > 0 pela escolha de q, esta última equação será da forma (23)
desde que B1 também seja positivo. Como veremos a seguir, o método de
Brouncker consiste em iterar esta construção até obter uma equação para a
qual seja fácil obter uma solução. No melhor estilo da época, nem Brouncker,
nem Wallis, tentaram provar que este método sempre funciona corretamente.
Parecem ter ficado satisfeitos em verificar que tudo corria como previsto nos
exemplos aos quais aplicaram o método.
Para podermos sistematizar o método de Brouncker vamos introduzir a
seguinte terminologia. Digamos que F(x, y) = Ax2 − 2Bxy − Cy2 e que q é o
maior inteiro positivo tal que
F(q, 1) = Aq2 − 2Bq− C < 0,
36 2. EQUAÇÃO DE PELL
então, diremos que a transformada de F é a forma
Ft(x, y) = A1x
2 − 2B1xy− C1y
2,
em que,
(25) A1 = −(Aq2 − 2Bq − C), B1 = Aq − B e C1 = A.
Os cálculos acima também mostram que
F(x0, y0) = F(qy0 + r, y0) = −F
t(y0, r) = −F
t(y0, x0 − qy0).
Portanto, se F(x0, y0) = ±1, então Ft(y0, x0−qy0) = ∓1. Observe que houve uma
inversão do sinal do termo constante na passagem de F à sua transformada. Há
uma outra maneira de enunciar esta mesma conclusão que se adapta melhor
à aplicação que dela faremos no algoritmo para resolver a equação de Pell.
Supondo que (x1, y1) é solução de Ft(x, y) = ∓1 e comparando-a com (y0, x0−qy0)
deduzimos que
x1 = y0 e y1 = x0 −qy0;
donde
x0 = y1 + qy0 = y1 + qx1 e y0 = x1.
Com isto expressamos as coordenadas de uma solução de F(x, y) = ±1 em ter-
mos das coordenadas de uma solução de Ft(x1, y1) = ∓1. Resumindo, temos a
seguinte conclusão.
CONCLUSÃO. Se q é o maior inteiro positivo tal que F(q, 1) < 0 e Ft(x1, y1) =
∓1, então F(y1 + qx1, x1) = ±1.
O próximo passo consiste em iterar o procedimento acima até obter uma
equação cujas soluções são fáceis de descobrir. Seguindo o exemplo de Wallis,
começaremos ilustrando a aplicação do algoritmo à uma equação específica.
Para tornar a apresentação mais clara, adicionaremos o índice i à forma con-
struída na i + 1-ésima iteração do algoritmo, assim como às suas variáveis e
demais elementos do algoritmo. Portanto, se F(x, y) = x2 − dy2, então
F0 = F
t, e Fi = (Fi−1)t quando i ≥ 1.
A forma Fi pode ser escrita como
Fi = Fi(xi, yi) = Aix
2
i − 2Bixiyi − Cy
2
i .
em que estamos supondo, tacitamente, que Ai, Bi e Ci são inteiros positivos.
Convém lembrar que, conforme a conclusão a que chegamos acima, as variáveis
de Fi e de Fi−1 estão relacionadas por
(26) xi−1 = qixi + yi e yi−1 = xi,
em que qi é o maior inteiro positivo para o qual Fi(qi, 1) < 0. Finalmente,
a alternância do sinal do termo constante na passagem de uma forma à sua
transformada implica que Fi(xi, yi) = (−1)i.
3. ACHANDO SOLUÇÕES 37
Talvez você esteja se perguntando porque definimos F0 como sendo a trans-
formada da equação de Pell dada e não a própria equação de Pell. A razão
para esta escolha só se tornará clara na próxima seção, onde analisaremos em
detalhe o funcionamento do método cíclico.
Usando a notação introduzida acima, a equação cuja solução Wallis deter-
mina na carta que enviou a Brouncker em 17 de dezembro de 1657, ver [13, p.
479-480], pode ser escrita na forma F(x, y) = 1, em que
F0(x, y) = x
2 − 13y2.
Como a maior raiz de F(t, 1) = 0 é t = 3.59375..., o maior inteiro q0 para o qual
F(q, 1) < 0 é q = 3. Fazendo a substituição
x = y0 + 3x0 e y = x0
em F(x, y) e no ponto P = (x, y), obtemos
F0(x0, y0) = 4x
2
0 − 6x0y0 − y
2 e P = (y0 + 3x0, x0);
de modo que de F0(x0, y0) = 1 obtivemos F0(x0, y0) = −1. Repetindo este pro-
cedimento com F0(x0, y0) = 0, verificamos que F0(1, t) = 0 tem uma única raiz
positiva em t = 1.65625..., de modo que q0 = 1. Aplicando a substituição
x0 = y1 + x1 e y0 = x1
a F0(x0, y0) e a P, temos que
F1(x1, y1) = 3x
2
1 − 2x1y1 − 4y
2
1 e P = (4x1 + 3y1, y1 + x1);
com F0(x0, y0) = −1 tendo sido convertido em F1(x1, y1) = 1. Para chegar ao
resultado desejado, o algoritmo executa mais oito etapas, que resumimos, jun-
tamente com as duas que já calculamos, na tabela 1, na qual a forma Fi está
abreviada como a trinca [Ai, Bi, Ci].
De acordo com a tabela, obtemos, após dez passos, obtemos a forma
F9(x9, y9) = x
2
9 − 6x9y9 − 4y
2
9
que tem como solução x9 = 1 e y9 = 0. Substituindo estes valores em
P = (649x9 + 393y9, 180x9 + 109y9)
concluímos que
P = (649, 180)
é uma solução de x2 − 13y2 = 1. Brouncker e Wallis descobriram que, longe
de ser atípico, o comportamento do método quando d = 13 se repetia em todos
os exemplos. Mais precisamente, era sempre possível encontrar um número
inteiro positivo par k de modo que o coeficiente de x2k em Fk(xk, yk) fosse igual
a 1, garantindo assim que Fk(1, 0) = 1, o que permitia resolver F0(x0, y0) = 1
38 2. EQUAÇÃO DE PELL
Passo q Substituições Fi(xi, yi) P
0 3 x = y0 + 3x0 e y = x0 [4, 3, 1] (3x0 + y0, x0)
1 1 x0 = y1 + x1 e y0 = x1 [3, 1, 4] (4x1 + 3y1, y1 + x1)
2 1 x1 = y2 + x2 e y1 = x2 [3, 2, 3] (7x2 + 4y2, 2x2 + y2)
3 1 x2 = y3 + x3 e y2 = x3 [4, 1, 3] (11x3 + 7y3, 3x3 + 2y3
4 1 x3 = y4 + x4 e y3 = x4 [1, 3, 4] (18x4 + 11y4, 5x4 + 3y4)
5 6 x4 = y5 + 6x5 e y4 = x5 [4, 3, 1] (119x5 + 18y5, 33x5 + 5y5)
6 1 x5 = y6 + x6 e y5 = x6 [3, 1, 4] (137x6 + 119y6, 38x6 + 33y6)
7 1 x6 = y7 + x7 e y6 = x7 [3, 2, 3] (256x7 + 137y7, 71x7 + 38y7)
8 1 x7 = y8 + x8 e y7 = x8 [4, 1, 3] (393x8 + 256y8, 109x8 + 71y8
9 1 x8 = y9 + x9 e y8 = x9 [1, 3, 4] (649x9 + 393y9, 180x9 + 109y9)
TABELA 1. Aplicação do método de Brouncker a x2 − 13y2 = 1
com bastante facilidade. levando isto em conta, podemos enunciar o método de
Brouncker e Wallis da seguinte forma.
ALGORITMO 3.1 (Método cíclico). Dado um inteiro positivo d, que não é um
quadrado perfeito, o algoritmo retorna uma solução não trivial da equação de
Pell x2 − dy2 = 1.
Calcule a parte inteira q da raiz quadrada de d.
Inicialize A com −(q2 − d), B com q e C com 1.
Inicialize um contador k := 1 e P := [x, y].
Enquanto A 6= 1 ou k for ímpar repita:
Determine o maior inteiro q menor que a raiz positiva de At2 −
2Bt− C = 0.
Substitua A por −(Aq2 − 2Bq− C), B por Aq− B e C por A.
Substitua x por qx + y e y por x em P.
Incremente k de uma unidade.
Substitua x por 1 e y por 0.
Retorne P.
Embora nossa descrição do algoritmo de Brouncker esteja completa, não é
fácil entender porque a execução deste conjunto de instruções deveria parar.
Uma análise mais detalhada do que fizemos revela que há muito mais a ser
verificado. A lista de pendências é a seguinte:
4. ANÁLISE DO ALGORITMO DE BROUNCKER 39
(a) determinar condições sobre F, sob as quais Ft existe e tem coeficientes
positivos;
(b) assegurar que as condições em (a) se propagam à transformada, per-
mitindo que o algoritmo possa ser iterado;
(c) mostrar que as condições que fazem o algoritmo parar sempre são re-
alizadas após uma quantidade finita de etapas.
A ressalva sob a existência de Ft em (a) é necessária porque a transformada
só existe se houver um inteiro positivo q para o qual F(q, 1) < 0. Note que
há uma grande diferença entre, de um lado (a) e (b), e do outro (c). De fato,
para resolvermos (a) e (b) basta considerarmos o que ocorre na passagem de
uma dada forma à sua transformada; já (c) requer que consideremos o efeito
do algoritmo sobre tantos passos quantos forem necessários para atingirmos
as condições que fazem o algoritmo parar. Por isso vamos nos referir a (a) e (b)
como parte da análise local do algoritmo e a (c) como resultando de sua análise
global. A próxima seção é dedicada a uma demonstração detalhada de (a), (b)
e (c).
4. Análise do algoritmo de Brouncker
Começamos a seção com a análise local do algoritmo de Brouncker, que
trata da passagem de uma forma à sua transformada. Ao longo de toda a
análise local, denotaremos por F a forma
F(x, y) = Ax2 − 2Bxy − Cy2,
em que A > 0, B > 0 e C > 0 são inteiros. Se F(t, 1) = 0 tiver uma raiz positiva
maior que 1, determinamos o maior inteiro positivo q para o qual F(q, 1) < 0 e
definimos a transformada Ft de F por
Ft(x ′, y ′) = −F(y ′ + qx ′, x ′).
Escrevendo
Ft(x ′, y ′) = A ′(x ′)2 − 2B ′x ′y ′ − C ′(y ′)2,
vimos que
(27) A ′ = −(Aq2 − 2Bq− C), B ′ = (Aq− B) e C ′ = A.
Portanto, para que Ft possa ser calculada e tenha as mesmas propriedades que
F, precisamos identificar condições que garantam que:
(1) F(t, 1) = 0 tenha uma raiz maior que 1;
(2) A ′ > 0, B ′ > 0 e C ′ > 0;
(3) as condições que garantem (1) e (2) também valham para Ft.
40 2. EQUAÇÃO DE PELL
b
−1
b
1
b
q+ 1
b
q
b
β
b
α
FIGURA 4. A parábola u = −F(t, 1).
As condições desejadas decorrem da análise da parábola u = F(t, 1), ilustrada
na figura 4. Para começar, o discriminante 4(B2 + AC) de F(t, 1) = 0 é positivo,
de modo que a equação F(t, 1) = 0 tem duas raízes reais distintas α < β. Como
αβ = −
C
A
e A e C são positivos, uma dessas raízes será positiva e a outra negativa; isto
é β < 0 < α. Até aqui usamos apenas que A e C são positivos e que B > 0.
Contudo, nem toda escolha de inteiros satisfazendo estas condições garante
que a forma F correspondente satisfaça (1). Isto porque (1) equivale a dizer que
α > 1 e as hipóteses que temos só garantem que α > 0. Entretanto, a parábola
u = F(t, 1) tem concavidade para cima, pois A > 0.

Outros materiais