Números Inteiros e Criptografia
S. C. Coutinho
Universidade Federal do Rio de Janeiro
i
ii
c by S. C. Coutinho 2014
Sumário
Capítulo 1. Equação de Pell
1. Compondo soluções
2. Grupos
3. Achando soluções
4. Análise do algoritmo de Brouncker
5. Estrutura do grupo P(d)
Exercícios
1
1
6
11
16
21
21
Capítulo 2. Grupos finitos
1. Inversíveis módulo n
2. Pell modular e suas generalizações
3. Subgrupos
4. O teorema de Lagrange
5. Aplicações
Exercícios
25
25
27
34
36
39
41
Capítulo 3. Comparando grupos
1. Homomorfismos
2. Ordem de P(d, p)
3. Produtos cartesianos e tabelas
4. Tabelas e grupos
5. A ordem de U(n)
Exercícios
45
45
49
52
55
57
60
Capítulo 4. Testes de primalidade
1. Os testes de Lucas e Lucas-Lehmer
2. O teste de Brilhart, Lehmer e Selfridge
3. A recíproca do teste de Lucas-Lehmer
63
63
68
70
Referências Bibliográficas
73
iii
CAPíTULO 1
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 antiguidade 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
A equação de Pell é a equação diofantina
x2 − dy 2 = 1 em que d ∈ Z.
Em outras palavras, o problema que queremos resolver consiste em determinar números
inteiros x0 e y0 que satisfaçam
x20 − dy02 = 1,
para um dado valor inteiro de d. Neste caso dizemos que o par (x0 , y0) é uma solução de
x2 − dy 2 = 1. Como as variáveis x e y aparecem ambas ao quadrado na equação, se o par
(x0 , y0) é uma solução de x2 − dy 2 = 1 então o mesmo vale para
(1)
(−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 negativo menor 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.
Um caso mais interessante é aquele em que d é um quadrado perfeito. Digamos que
d = r 2 , para algum inteiro positivo r. Então,
1 = x2 − dy 2 = x2 − r 2 y 2 = x2 − (ry)2 = (x − ry)(x + ry).
1
2
1. EQUAÇÃO DE PELL
Mas x − ry e x + ry só podem ser inteiros cujo produto dá 1 se ambos 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 encontrados no exercício
5.
As considerações dos dois últimos parágrafos nos permitem concluir que 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 de Pell quando d é pequeno. Por exemplo, o par (2, 1) é claramente
uma solução para x2 − 3y 2 = 1. Uma solução não trivial para x2 − 2y 2 = 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 menor solução é (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ção não trivial. Para isto usavam
a seguinte fórmula, descoberta por Brahmagupta e apresentada em seu livro A doutrina de
Brama corretamente estabelecida:
(2)
(xu + dyv)2 − d(xv + yu)2 = (x2 − dy 2)(u2 − dv 2 ),
que pode ser facilmente provada calculando-se, separadamente, seu lado esquerdo e seu
lado direito e comparando os resultados. Se x1 , y1 , x2 e y2 são inteiros que satisfazem
x21 − dy12 = x22 − dy22 = 1,
então, pela identidade (2), temos que
(x1 x2 + dy1 y2 )2 − d(x1 y2 + y1 x2 )2 = 1.
Em outras palavras, se (x1 , y1 ) e (x2 , y2 ) são soluções da equação de Pell x2 − dy 2 = 1,
então
(3)
(x1 x2 + dy1y2 , x1 y2 + y1 x2 )
também é solução da mesma equação.
Por exemplo, como os pares (2, 1) e (−1, 0) são soluções de x2 − 3y 2 = 1, então
podemos combiná-los usando a fórmula (3), obtendo assim que o par (−2, −1) 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 − 3y 2 = 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 (3) 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
1. COMPONDO SOLUÇÕES
3
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 uma maneira compacta de expressar as aplicações da fórmula (3) 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 resultante 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 − dy 2 = 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 − dy 2 = 1}.
Lembre-se que os elementos do produto cartesiano A × B entre dois conjuntos A 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 (2) como uma maneira de
combinar dois elementos de P(d) de modo a obter um novo elemento 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 − dy 2 = 1, definimos
(4)
σ1 ⊗ σ2 = (x1 x2 + dy1y2 , x1 y2 + y1 x2 ).
A identidade (2) 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 − 3y 2 = 1 que fizemos no início desta seção
podem ser resumidos da seguinte forma:
(2, 1) ⊗ (−1, 0) = (−2, −1)
(2, 1) ⊗ (2, 1) = (7, 4)
(7, 4) ⊗ (7, 4) = (97, 56)
(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 correspondentes, verá que a
troca nas posições dos pares não afeta em nada o resultado.
4
1. EQUAÇÃO DE PELL
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 (4) 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 encontramos
anteriormente, é a seguinte: se σ = (x0 , y0 ) ∈ P(d), então σ = (x0 , −y0 ) satisfaz
(5)
σ ⊗ σ = (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 nossos 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 ⊗ σ.
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 comutatividade 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álculos 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 ingrediente que faltava para eliminar a ambiguidade na definição da quarta potência,
verificaremos que se σ ∈ P(d) então
σ ⊗ σ3 = σ2 ⊗ σ2.
1. COMPONDO SOLUÇÕES
5
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 multiplicaçã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 − dy 2 = 1 é uma hipérbole. Por exemplo, quando d = 2 a hipérbole correspondente é
ilustrada na figura 1.
F IGURA 1. A hipérbole x2 − 2y 2 = 1
Para multiplicar duas soluções P1 e P2 da equação de Pell x2 − dy 2 = 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,
r terá que intersectar a hipérbole em um segundo ponto, que será o produto desejado.
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
y2 − y1
(6)
α=
.
x2 − x1
Por outro lado, temos de (4) que a reta por e = (1, 0) e P1 ⊗ P2 tem coeficiente angular
x1 y2 + x2 y1
.
β=
x1 x2 + dy1y2 − 1
Para que estas duas retas sejam paralelas, é necessário que α = β, que equivale a dizer que
(x1 y2 + x2 y1 )(x2 − x1 ) = (x1 x2 + dy1 y2 − 1)(y2 − y1 ).
Contudo, um cálculo simples mostra que
(x1 y2 +x2 y1 )(x2 −x1 )−(x1 x2 +dy1 y2 −1)(y2 −y1 ) = −dy1 y22 +dy12y2 −x21 y2 +y2 +x22 y1 −y1 ,
6
1. EQUAÇÃO DE PELL
b
A
F IGURA 2. A tangente no ponto A (linha cheia) como limite das secantes
que podemos reescrever na forma
(7)
y1 (−dy22 + x22 − 1) + y2 (−x21 + dy12 + 1).
Entretanto, como P1 e P2 são, por hipótese, soluções da equação de Pell x2 − dy 2 = 1,
teremos que
x21 − dy12 = 1 e que x22 − dy22 = 1
donde segue, imediatamente, que a expressão (7) é nula, confirmando, assim, que α = β,
como queríamos mostrar.
A despeito do que acabamos de provar, se tentarmos esboçar a figura correspondente
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 (6) não faz sentido. Por sorte a maneira
de contornar isto é 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 sugere 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 − dy 2 = 1. Se você sabe
um pouco de cálculo diferencial, não terá dificuldade em determinar que se y0 6= 0, então
m = x0 /dy0; se não sabe, encontrará um 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).
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 à multiplicaçã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.
2. GRUPOS
b
7
C
B
b
b
e
F IGURA 3. C = (7, 4) é o quadrado do ponto B = (2, 1)
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 elementos 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 multiplicação de 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 operaçã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, quaisquer que
forem os elementos a, b, c ∈ G, a operação satisfaz as seguintes propriedades:
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;
8
1. EQUAÇÃO DE PELL
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 de objetos que,
por pouco, não satisfazem as propriedades requeridas. Por exemplo, os números inteiros,
racionais, reais e complexos são grupos relativamente à operação de soma e o mesmo vale
para os vetores do plano e as matrizes 2 × 2. Por outro lado, os inteiros não constituem
um grupo relativamente à subtração, porque esta operação não é associativa, nem tem elemento neutro. Quando a operação é a multiplicação, nenhum 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 − dy 2 = 1, com a operação definida pela fórmula (4), mas você encontrará
mais exemplos nos 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 −dy 2 = 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
(8)
a ⋆ x = b.
Como G é um grupo, todo elemento de G tem um inverso em G; em particular, existe um
elemento a1 tal que a1 ⋆ a = e. Multiplicando a equação (8) por a1 , obtemos
a1 ⋆ (a ⋆ x) = a1 ⋆ b.
2. GRUPOS
9
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 um grupo G qualquer, toda equação da forma a ⋆ x = b tem
solução, que é sempre igual a a1 ⋆ b. Por exemplo, para achar 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 (5) é
(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 resultado de um produto de elementos independente
da maneira como escolhemos 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} .
| ⋆ ·{z
vezes
k
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
ak ⋆ aℓ = ak+ℓ
e
(ak )ℓ = akℓ .
Estas fórmulas por sua vez, sugerem que deveríamos definir a0 = e, em que e é o elemento
neutro de G. Para entender o porquê, observe que tomando ℓ = 0 na primeira destas
fórmulas, obtemos
ak ⋆ a0 = ak+0 = ak .
Mas, multiplicando a equação acima pelo inverso de ak , concluímos que
e ⋆ a0 = e;
de modo que a0 = e, como havíamos afirmado. Com isto estamos prontos para apresentar
o problema que havíamos mencionado no início deste parágrafo.
10
1. EQUAÇÃO DE PELL
P ROBLEMA DO LOGARITMO
inteiro k tal que bk = a?
DISCRETO .
Dados a e b em um grupo G, existe algum
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 da solução de equações
lineares, que sempre tem 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 criptografia, ainda que o problema tenha solução pode ser
extremamente difícil obtê-la. Como veremos no capítulo ??, a segurança do algoritmo de
criptografia conhecido como El Gamal baseia-se na dificuldade de resolver o problema do
logaritmo discreto em certos grupos.
A noção de potência também nos permite mostrar que P(3) é um conjunto infinito.
Para provar isto, analisaremos o que acontece quando comparamos as coordenadas de um
dado par P = (a, b) com as do seu quadrado. Usando a fórmula (4), verificamos que
P 2 = (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 P são ambas maiores que as respectivas coordenadas de P . Denotaremos isto escrevendo
2
P < P 2.
Note que esta desigualdade implica que as coordenadas de P 2 também têm que ser positivas, de forma que o mesmo argumento aplicado a P 2 garante que
P 2 < P 4;
e assim por diante. Em outras palavras, temos que se as coordenadas de P são positivas,
então a sequência
k
P < P2 < P4 < P8 < ··· < P2 < ···
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ávamos. Se você está familiarizado com o princípio de indução finita, vai identificar 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 − dy 2 = 1 no caso em que o inteiro positivo d não é um quadrado perfeito. É
claro que podemos fazer isto nap
base da força bruta. Por exemplo, incrementamos y de um
em um, calculando o valor de 1 + dy 2 correspondente. Teremos achado uma solução
3. ACHANDO SOLUÇÕES
11
p
da equação quando encontrarmos um y para o qual x = 1 + dy 2 é 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 − dy 2 = 1. Na forma em que vamos apresentá-lo
este algoritmo foi descrito em uma carta de John Wallis, 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áticos 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 idealizado 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
(9)
x2 − dy 2 = 1
a equação de Pell que queremos resolver. Diremos que uma solução de (9) é positiva se
suas coordenadas são inteiros maiores que zero. Se (u0, v0 ) é uma solução positiva desta
equação, então
u20 = dv02 + 1 > v02 ,
de modo que u0 > v0 . Portanto, ao dividir u0 por v0 , obtemos
u0 = v0 q + r
em que
r > 0.
Substituindo esta expressão para u0 na equação (9) e expandindo o produto notável, podemos concluir que (v0 , r) é solução da equação diofantina
(q 2 − d)x2 + 2qxy + y 2 = 1.
Como v0 , q e r são inteiros positivos, (v0 , r) só pode ser solução desta equação se d > q 2 .
Por isso é preferível reescrevê-la na forma
(10)
(d − q 2 )x2 − 2qxy − y 2 = −1,
12
1. EQUAÇÃO DE PELL
já que, quando d > q 2 , os coeficientes de (10) são todos inteiros positivos. 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 equações cada vez mais fáceis de resolver. Infelizmente, há um obstáculo óbvio
à implementação desta ideia: a substituição que usamos não transforma uma solução da
equação de Pell em uma outra solução, com ordenada menor, da mesma equação. Na
verdade, (10) não é nem mesmo 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 (9), quanto
(10).
Seguindo nos passos de Brouncker, devemos considerar equações da forma
Ax2 − 2Bxy − Cy 2 = ±1,
(11)
em que A, 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 = v0 q + r então, substituindo esta última expressão
em (11), obtemos
(Aq 2 − 2Bq − C)y 2 + 2(Aq − B)ry + Ar 2 = ±1.
(12)
Note que precisamos que q seja positivo, do contrário r = u0 e a substituição em nada
alteraria a equação dada. Brouncker propôs escolher q como o maior inteiro para o qual
Aq 2 − 2Bq − C < 0. Com isso o coeficiente de y 2 em (12) é necessariamente negativo.
Assim, multiplicando (12) por −1 e tomando
A1 = −(Aq 2 − 2Bq − C),
B1 = Aq − B
e
C1 = A
obtemos a equação
A1 y 2 − 2B1 yr − C1 r 2 = ∓1.
Como C1 = A > 0 por hipótese e A1 > 0 pela escolha de q, esta última equação será
da forma (11) 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. Se F (x, y) = Ax2 − 2Bxy − Cy 2 e q é o maior inteiro positivo tal que
F (q, 1) = Aq 2 − 2Bq − C < 0,
então, a forma derivada de F é
F ′ (x, y) = A1 x2 − 2B1 xy − C1 y 2 ,
em que,
(13)
A1 = −(Aq 2 − 2Bq − C),
B1 = Aq − B
e
C1 = A.
3. ACHANDO SOLUÇÕES
13
Os cálculos acima também mostram que
F (u0, v0 ) = F (qv0 + r, v0 ) = −F ′ (v0 , r) = −F ′ (v0 , u0 − qv0 ).
Portanto, se (u0 , v0 ) for uma solução de F (x, y) = ±1, então (v0 , u0 − qv0 ) é uma solução
de F ′ (x, y) = ∓1 — note a inversão do sinal!
Para podermos esclarecer, de maneira mais precisa, o funcionamento do algoritmo de
Brouncker, digamos que F0 = x2 − dy 2, de modo que a equação de Pell a ser resolvida é
F0 = 1. Denotaremos por Fi (x, y) a i-ésima forma derivada de F0 . Em outras palavras,
F1 = (F0 )′ ,
F2 = (F1 )′ ,
F3 = (F2 )′ ,
e assim por diante. Como será necessário fazer substituições de variáveis a cada passo
executado pelo algoritmo, denotaremos por xi e yi as variáveis da i-ésima forma derivada.
Em outras palavras,
Fi = Fi (xi , yi ) = Ai x2i − 2Bi xi yi − Cyi2,
em que estamos supondo, tacitamente, que Ai , Bi e Ci são inteiros positivos. Se qi for o
maior inteiro positivo para o qual Fi (qi , 1) < 0 então, fazendo a substituição
(14)
xi = qi xi+1 + yi+1
e
yi = xi+1 ,
em Fi (xi , yi ), obtemos a forma
Fi (qi xi+1 + yi+1 , xi+1 ) = −Fi+1 (xi+1 , xi+1 ).
Esta troca de sinal, que ocorre cada vez que este passo é executado, transforma a equação
F0 (x0 , y0 ) = 1 em
Fi (xi , yi ) = (−1)i
ao final do i-ésimo passo. Logo, se (ui , vi ) for uma solução de Fi (xi , yi ) = (−1)i então,
resolvendo o sistema linear
(15)
ui = qi ui+1 + vi+1
e
vi = ui+1 ,
obtemos uma solução
ui − vi
(ui+1, vi+1 ) = vi ,
qi
i+1
da equação Fi+1 (xi+1 , yi+1 ) = (−1) . Portanto, se em algum momento obtivermos uma
equação Fk (xk , yk ) = (−1)k que seja fácil de resolver, podemos usar as transformações
(15) para obter, a partir dela, uma solução de F0 (x0 , y0 ) = 1.
Na prática há uma maneira bem mais eficiente de determinar (u0 , v0 ), do que esperar
que (uk , vk ) tenha sido encontrado, e só então usar (15) para achar (u0 , v0 ). A ideia é utilizar (14) para escrever P = (x0 , y0 ) como função de (xi , yi ). Assim, ao cabo da primeira
iteração, teremos que
P = (x0 , y0 ) = (q1 x1 + y1 , x1 ).
14
1. EQUAÇÃO DE PELL
Substituindo, então, os valores de x1 e y1 pelas expressões obtidas substituindo i = 1 em
(14), obtemos
P = (q1 x1 + y1 , x1 ) = (q1 (q2 x2 + y2 ) + x2 , q2 x2 + y2 ) = ((q1q2 + 1)x2 + q1y2, q2x2 + y2 ).
Tomando i = 2 e procedendo da mesma maneira, obtemos
P = (((q1q2 + 1)q3 + q1)x3 + (q1q2 + 1)y3, (q2q3 + 1)x3 + q2y3 ),
ao final da terceira iteração. Continuando a efetuar as substituições adequadas, obteremos,
na k-ésima iteração,
P = (λ(xk , yk ), µ(xk , yk )),
em que λ e µ são funções lineares de xk e yk . Com isto, se (uk , vk ) for uma solução de
Fk (xk , yk ) = (−1)k , então
(λ(uk , vk ), µ(uk , vk )),
será uma solução de F0 (x0 , y0 ) = 1.
Para melhor esclarecer o funcionamento deste procedimento, faremos o exemplo resolvido por Wallis em sua carta a Brouncker datada de 17 de dezembro de 1657; ver [13, p.
479-480]. A equação de que trata o exemplo é
x2 − 13y 2 = 1.
Usando a notação introduzida acima, escreveremos esta equação na forma F0 (x0 , y0 ) = 1,
em que
F0 (x0 , y0 ) = x2 − 13y 2.
Como a maior raiz de F0 (t, 1) = 0 é t = 3.59375..., o maior inteiro q0 para o qual
F0 (q0 , 1) < 0 é q0 = 3. Fazendo a substituição
e
x0 = y1 + 3x1
y0 = x1
em F0 (x0 , y0) e no ponto P = (x0 , y0 ), obtemos
F1 (x1 , y1 ) = 4x21 − 6x1 y1 − y 2
e
P = (y1 + 3x1 , x1 );
de modo que de F0 (x0 , y0 ) = 1 obtivemos F1 (x1 , y1) = −1. Repetindo este procedimento
com F1 (x1 , y1 ) = 0, verificamos que F1 (1, t) = 0 tem uma única raiz positiva em t =
1.65625..., de modo que q1 = 1. Aplicando a substituição
x1 = y2 + x2
e
y1 = x2
F2 (x2 , y2 ) = 3x22 − 2x2 y2 − 4y22
e
P = (4x2 + 3y2 , y2 + x2 );
a F1 (x1 , y1 ) e a P , temos que
com F1 (x1 , y1) = −1 tendo sido convertido em F2 (x2 , y2 ) = 1. Para chegar até resultado
desejado, o algoritmo executa mais oito etapas, que resumimos, juntamente com as duas
que já calculamos, na tabela 1, na qual a forma Fi está abreviada como a trinca [Ai , Bi , Ci ].
3. ACHANDO SOLUÇÕES
15
q
Substituições
Fi (xi , yi )
P
3 x0 = y1 + 3x1 e y0 = x1
[4, 3, 1]
(3x1 + y1 , x1 )
1 x1 = y2 + x2 e y1 = x2
[3, 1, 4]
(4x2 + 3y2 , y2 + x2 )
1 x2 = y3 + x3 e y2 = x3
[3, 2, 3]
(7x3 + 4y3, 2x3 + y3 )
1 x3 = y4 + x4 e y3 = x4
[4, 1, 3]
(11x4 + 7y4, 3x4 + 2y4
1 x4 = y5 + x5 e y4 = x5
[1, 3, 4]
(18x5 + 11y5 , 5x5 + 3y5 )
6 x5 = y6 + 6x6 e y5 = x6
[4, 3, 1]
(119x6 + 18y6 , 33x6 + 5y6 )
1 x6 = y7 + x7 e y6 = x7
[3, 1, 4]
(137x7 + 119y7 , 38x7 + 33y7 )
1 x7 = y8 + x8 e y7 = x8
[3, 2, 3]
(256x8 + 137y8 , 71x8 + 38y8 )
1 x8 = y9 + x9 e y8 = x9
[4, 1, 3]
(393x9 + 256y9, 109x9 + 71y9
1 x9 = y10 + x10 e y9 = x10 [1, 3, 4] (649x10 + 393y10 , 180x10 + 109y10 )
Passo
1
2
3
4
5
6
7
8
9
10
TABELA 1. Aplicação do método de Brouncker à equação x2 − 13y 2 = 1
De acordo com a tabela 1, obtemos, após dez passos, a forma
2
F10 (x10 , y10 ) = x210 − 6x10 y10 − 4y10
que tem como solução x10 = 1 e y10 = 0. Substituindo estes valores em
P = (649x10 + 393y10 , 180x10 + 109y10 )
obtemos
P = (649, 180)
que é a solução desejada de x2 − 13y 2 = 1. Brouncker e Wallis descobriram que, longe
de ser atípico, o comportamento do método quando 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 com bastante facilidade. levando isto
em conta, podemos enunciar o método de Brouncker e Wallis da seguinte forma.
A LGORITMO 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 − dy 2 = 1.
Calcule a parte inteira q da raiz quadrada de d.
Inicialize A com −(q 2 − 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 −(Aq 2 − 2Bq − C), B por Aq − B e C por A.
16
1. EQUAÇÃO DE PELL
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:
(a) determinar condições sobre F , sob as quais F ′ existe e tem coeficientes positivos;
(b) assegurar que as condições em (1) se propagam à forma derivada, permitindo que
o algoritmo possa ser iterado;
(c) mostrar que as condições que fazem o algoritmo parar sempre são realizadas após
uma quantidade finita de etapas.
A ressalva sob a existência de F ′ em (a) é necessária porque a forma derivada 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 derivada; 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 derivada. Ao longo de toda a análise local, denotaremos por F
a forma
F (x, y) = Ax2 − 2Bxy − Cy 2,
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 forma
derivada F ′ de F por
F ′ (x′ , y ′) = −F (y + qx, x).
Escrevendo
F ′ (x′ , y ′) = A′ (x′ )2 − 2B ′ x′ y ′ − C ′ (y ′)2 ,
vimos que
(16)
A′ = −(Aq 2 − 2Bq − C),
B ′ = (Aq − B) e
C ′ = A.
4. ANÁLISE DO ALGORITMO DE BROUNCKER
β
b
b
b
17
q
1
b
−1
b
b
α q+1
F IGURA 4. A parábola y = −F (x, 1).
Portanto, para que F ′ 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 F ′ .
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(B 2 + 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. Logo,
18
1. EQUAÇÃO DE PELL
para que 1 esteja entre as raízes de F (t, 1) = 0 devemos ter que
F (1, 1) = A − 2B − C < 0.
Portanto, às hipóteses A > 0, B ≥ 0 e C > 0 devemos acrescentar que A − 2B − C < 0
para que exista um inteiro q > 0 para o qual F (q, 1) < 0.
Passando, agora, a (2), sabemos que a escolha feita para q garante que
A′ = −(Aq 2 − 2Bq − C) = −F (q, 1) > 0,
ao passo que
C ′ = A > 0,
é consequência direta das hipóteses originais impostas a F . Resta-nos, apenas, verificar se
B ′ = Aq − B é não negativo. Mas isto ocorre quando q ≥ B/A. Contudo, escolhendo
q ≥ 1 como o maior inteiro menor que a raiz positiva α de F (t, 1) = 0, teremos que
α < q + 1 ≤ 2q.
Por outro lado,
α+β =
donde
2B
A
α+β
α
B
=
< ,
A
2
2
pois β < 0. Combinando esta última desigualdade com α < 2q, obtemos
B
α
≤ < q,
A
2
como queríamos mostrar. Provamos, assim, que B ′ > 0 sob as mesmas hipóteses que
garantem que A′ > 0 e C ′ > 0, o que é uma ótima notícia.
Resta-nos, apenas, mostrar que estas condições são herdadas por F ′, permitindo que o
procedimento seja iterado. Como já sabemos que, sob as novas hipóteses, A′ , B ′ e C ′ são
positivos, basta verificar que elas também garantem que F ′ (1, 1) < 0. Mas
(17)
F ′ (±1, 1) = A′ ± 2B ′ − C ′ = −F (q ∓ 1, 1).
Como α < q + 1 e a parábola y = F (x, 1) tem concavidade para cima, temos de (17) que
F ′ (1, 1) = −F (q + 1, 1) < 0.
Portanto, se A > 0, B ≥ 0, C > 0 e A − C < 2B, então estas mesmas propriedades
valem para os coeficientes da forma derivada F ′ .
Antes de passar à análise global, precisamos investigar uma outra propriedade que
pertence à análise local e que será necessária mais adiante. Para isso, dada F introduzimos
sua simétrica SF como sendo a forma obtida trocando-se o coeficiente de x2 com o de y 2 ;
isto é
SF (x, y) = Cx2 − 2Bxy − Ay 2 .
4. ANÁLISE DO ALGORITMO DE BROUNCKER
19
Em particular, a simétrica de F ′ é
SF ′ = C ′ x2 − 2B ′ xy − A′ y 2.
Vejamos o que acontece se calcularmos a forma derivada de S = SF ′ . Em primeiro lugar,
para que isto seja possível, é preciso que S(1, 1) < 0; isto é, que
C ′ − 2B ′ − A′ < 0.
Substituindo as fórmulas para A′ , B ′ e C ′ de (16) e reagrupando os termos, temos que
C ′ − 2B ′ − A′ = A(q − 1)2 − 2B(q − 1) − C.
Mas q > 1 implica que 0 < q−1 < q, de modo que q−1 está entre as raízes de F (t, 1) = 0.
Logo,
(18)
A(q − 1)2 − 2B(q − 1) − C = F (q − 1, 1) < 0.
Portanto, S ′ satisfaz as condições requeridas para que o cálculo da forma derivada possa
ser efetuado. O próximo passo consiste em determinar o maior inteiro m > 0 tal que
S ′ (m, 1) = C ′ m2 − 2B ′ m − A′ < 0.
Substituindo as fórmulas de (16) e reagrupando os termos, como acima, obtemos
S ′ (m, 1) = A(q − m)2 − 2B(q − m) − C = F (q − m, 1).
Desta última equação, segue-se que
(19)
S ′ (q, 1) = −C < 0,
pois C > 0 por hipótese. Por outro lado,
C ′ (q + 1)2 − 2B ′ (q + 1) − A′ = A + 2B − C.
Logo, se
A + 2B − C > 0
então m = q e os coeficientes da forma derivada de S ′ serão
C ′ q 2 − 2B ′ q − A′ = A,
A′ q − B ′ = B
e
C ′ = A.
Em outras palavras, adicionando A + 2B − C > 0 às hipóteses vigentes, teremos que a
forma derivada de SF ′ é SF . Contudo, antes de acrescentar A + 2B − C > 0 às demais
condições, precisamos nos certificar de que é herdada pela forma derivada, do contrário
não poderíamos iterar o cálculo das derivadas das formas simétricas, requerido na análise
global. Entretanto,
A′ + 2B ′ − C ′ = −(A(q − 1)2 − 2B(q − 1) − C) = −F (q − 1, 1),
que é positivo por (18), de forma que também esta condição é preservada pelo processo de
derivação de formas.
Para simplificar o enunciado final que resulta de nossa análise da passagem de uma
forma à sua derivada, diremos que uma forma F = Ax2 − 2Bxy − Cy 2 é reduzida se
20
1. EQUAÇÃO DE PELL
A > 0, B ≥ 0, C > 0 e |A − C| < 2B e que seu discriminante é o número B 2 + AC.
Com isto, o que provamos acima pode ser resumido nas seguintes conclusões:
Conclusão 1: a forma derivada de uma forma reduzida também é reduzida;
Conclusão 2: a derivada da simétrica de uma forma reduzida é a forma original;
Precisamos, também, do seguinte resultado, que pode ser obtido por um cálculo simples a
partir das fórmulas (16):
Conclusão 3: uma forma e sua reduzida têm o mesmo discriminante.
Com isto estamos prontos para passar à análise global. Usando a notação que introduzimos na seção anterior, denotaremos por
Fi (x, y) = Ai x2 − 2Bi xy − Ci
a i-ésima forma derivada da forma
F0 (x, y) = x2 − dy 2.
Como, pela conclusão 3, o discriminante de uma forma e de sua derivada coincidem, temos
que
Bi2 + Ai Ci = d,
pois o discriminante de F0 é d. Contudo, a quantidade de inteiros não negativos α, β e γ
que satisfazem a relação
β 2 + αγ = d
é finita. Isto significa que, após uma certa quantidade r de passos, teremos, necessariamente, que
Fr (x, y) = Fq (x, y)
para algum inteiro q < r. Portanto, se Si for a forma simétrica de Fi , teremos que
Sr (x, y) = Sq (x, y).
Calculando a q-ésima forma derivada destas duas formas, obtemos
Sr−q (x, y) = S0 (x, y);
que, pela conclusão 2 equivale a
Fr−q (x, y) = F0 (x, y).
Como r > q, podemos concluir que, depois de executar uma quantidade k = r − q > 0 de
passos, o algoritmo 3.1 retorna à forma original F0 . Levando em conta a alternância dos
sinais na passagem de um passo ao outro do algoritmo, obtivemos, ao final de k etapas a
equação diofantina
Fk = F0 = (−1)k .
EXERCÍCIOS
21
Se k for par, esta equação tem (1, 0) como solução e o algoritmo para, retornando uma
solução de F0 (x, y) = 1. Se k for ímpar, continuamos a executar o algoritmo por mais k
passos, o que nos dá
F2k = Fk = F0 = (−1)2k = 1,
que tem (1, 0) como solução. Portanto, o algoritmo funciona corretamente em qualquer dos
dois casos, retornando a resposta desejada. A demonstração de que o algoritmo 3.1 funciona também explica porque os indianos, que foram os primeiros a inventá-lo, chamavamno de método cíclico: à medida que o valor de i aumenta, a sequência de formas derivadas
percorre o ciclo
F0 , F1 , . . . , Fk = F0
se k for par, ou
F0 , F1 , . . . , F2k = F0
se k for ímpar.
5. Estrutura do grupo P(d)
Nesta seção pretendo responder à pergunta, feita em aula por alguns alunos, que queriam saber se todos os elementos de P(d) são potências do elemento encontrado pelo método cíclico. A resposta é sim. Mais precisamente, se G é um grupo e todos os seus
elementos são potências de um único dentre eles, então o grupo é chamado de cíclico e
este elemento é um gerador do grupo. O resultado desejado pode então ser enunciado da
seguinte forma.
T EOREMA 5.1. O grupo P(d) é cíclico e é gerado pelo elemento obtido aplicando-se
o algoritmo 3.1 à equação x2 − dy 2 = 1.
A demonstração deste resultado é um pouco trabalhosa e vou deixá-la para outra ocasião.
Exercícios
1. Prove que se, para um dado d, a equação de Pell x2 − dy 2 = 1 tem uma solução
não trivial, então ela também admite uma solução não trivial cujas duas entradas são
positivas.
2. Determine, por tentativa, pelo menos uma solução cujas entradas são positivas, para as
seguintes equações de Pell:
(a) x2 − 3y 2 = 1;
(b) x2 − 6y 2 = 1;
(c) x2 − 15y 2 = 1.
22
1. EQUAÇÃO DE PELL
3. O objetivo deste exercício é calcular todas as soluções da equação de Pell x2 −ny 2 = 1
quando n < −2:
(a) Mostre que se n < −2 então x2 − ny 2 > 2 quaisquer que sejam os inteiros x e y.
(b) Use (a) para mostrar que se x e y são soluções da equação de Pell com n < −2,
então y = 0.
(c) Use (b) para provar que, quando n < −2, as únicas soluções da equação de Pell
são as triviais.
4. Resolva a equação de Pell x2 + y 2 = 1 seguindo os seguintes passos:
(a) se x ≥ 1 e y ≥ 1 são inteiros então x2 + y 2 > 1;
(b) conclua de (a) que se x2 + y 2 = 1 então x = 0 ou y = 0;
(c) use (b) para achar todas as Soluções de x2 + y 2 = 1.
5. Resolva a equação de Pell x2 − dy 2 = 1 quando d = r 2 para algum número inteiro não
positivo r. Siga os seguintes passos:
(a) fatore x2 − dy 2 = x2 − r 2 y 2 ;
(b) lembrando que x e y são inteiros, e comparando a fatoração obtida em (a) com o
lado direito da equação, determine os possíveis valores destes fatores;
(c) considerando todos os possíveis valores dos fatores, você obterá dois sistemas lineares, cujas soluções inteiras lhe darão todas as soluções desta equação de Pell.
6. Seja (x0 , y0) uma solução da equação de Pell x2 − dy 2 = 1. Calcule
(x0 , y0 ) ⊗ (−1, 0).
7. Seja σ0 = (−1, 0) solução de x2 − ny 2 = 1. Determine σ0k para cada inteiro k > 0.
8. Ache uma solução da equação de Pell x2 − 5y 2 = 1 e calcule seu quadrado e seu cubo.
9. Seja σ0 = (8, 3) solução de x2 − 7y 2 = 1. Determine σ02 , σ03 e σ04 .
10. Seja P = (x0 , y0 ) uma solução de x2 − 2y 2 = 1. Mostre como obter uma solução de
x2 − 8y 2 = 1 a partir de P 2 .
11. Calcule P ∈ P(7) tal que (2024, 765) ⊗ P = (514088, 194307).
12. Sejam σ0 e σ1 duas soluções da equação de Pell x2 − dy 2 = 1 cujas entradas são todas
positivas. Prove que:
(a) todas as entradas de σ0 ⊗ σ1 são positivas;
(b) a primeira entrada de σ0 ⊗ σ1 é maior que o máximo das primeiras entradas de σ0
e σ1 .
(c) Use (b) para provar que σ0 ⊗ σ1 não pode ser igual a σ0 nem a σ1 .
EXERCÍCIOS
23
13. Use o exercício 12 para provar que se a equação x2 − dy 2 = 1 tem alguma solução não
trivial, então ela tem infinitas soluções.
14. Neste exercício apresentamos um roteiro para a demonstração de que inclinação da
reta tangente à hipérbole x2 − dy 2 = 1 no ponto P = (x0 , y0) é igual a x0 /dy0.
Usaremos a mesma definição de tangente adotada no estudo da circunferência nos
cursos elementares de geometria. Isto é, diremos que uma reta é tangente à hipérbole
se ela toca a curva em um único ponto.
(a) Determine a equação quadrática em x que as abscissas dos pontos de interseção da
reta de equação y = m(x − x0 ) + y0 com a hipérbole satisfazem.
(b) Mostre que o discriminante da equação quadrática obtida em (a) é igual a (mdy0 −
x0 )2 .
(c) Use (b) para chegar à conclusão desejada.
D ICAS : para (a) substitua a equação da reta na equação da hipérbole; para (b) use que
x20 − dy02 = 1.
15. Mostre que a operação de subtração de inteiros não é associativa, nem comutativa, nem
tem elemento neutro.
16. Seja P o conjunto cujos elementos são os subconjuntos de {1, 2, . . . , n}. Para quais
das operações abaixo este conjunto constitui um grupo?
(a) união;
(b) complementar;
(c) diferença simétrica.
Para caso de você não lembrar, a diferença simétrica entre dois conjuntos A e B é
definida por (A \ B) ∪ (B \ A).
17. Dados dois números reais u e v, definimos
u+v
u◦v =
.
1 + uv
c2
Determine se o intervalo (−c, c) com a operação ◦ é ou não um grupo. Esta operação
corresponde à soma de velocidades na teoria da relatividade restrita, em que c é a
velocidade da luz.
18. Seja (G, ⋆) um grupo e a um elemento de G. Usando as fórmulas
a0 = e e
ak+ℓ = ak ⋆ aℓ ,
para inteiros não negativos k e ℓ, determine como deveríamos definir potências negativas de a em G.
19. Seja (G, ⋆) um grupo.
(a) Mostre que um grupo não pode ter mais de um elemento neutro.
(b) Mostre que cada elemento de um grupo só pode um inverso.
24
1. EQUAÇÃO DE PELL
20. Seja (G, ⋆) um grupo. Um subconjunto S de G é fechado relativamente à operação ⋆
se para quaisquer elementos a, b ∈ S temos sempre que a ⋆ b ∈ S. Quais dos seguintes
subconjuntos são fechados relativamente à operação de adição de inteiros:
(a) os números pares;
(b) os números ímpares;
(c) os múltiplos de 3;
(d) os números positivos.
21. Todo grupo tem, pelo menos dois subconjuntos distintos que são fechados relativamente à sua operação: quais são estes subconjuntos?
22. Seja (G, ⋆) um grupo e a um elemento de G. Defina hai como sendo o conjunto das
potências de a com expoentes não negativos; isto é
hai = {ak | k ≥ 0
é inteiro }.
Mostre que hai é um conjunto fechado relativamente à operação ⋆.
23. Mostre que se a equação de Pell x2 − dy 2 = 1 tem solução diferente de (±1, 0), então
o grupo P(d) é infinito.
24. Seja d > 0 um número inteiro. Qual a maior quantidade de inteiros não negativos α, β
e γ que satisfazem β 2 + αγ = d?
25. Use o algoritmo de Brouncker para achar soluções para as seguintes equações de Pell
(a) x2 − 10y 2 = 1;
(b) x2 − 12y 2 = 1;
(c) x2 − 20y 2 = 1.
26. Suponha que x0 e y0 são dois inteiros tais que x20 − ny02 = ±2.
(a) Obtenha soluções para a equação x2 − ny 2 = 4 em termos de x0 e y0 .
(b) Usando ny02 = x20 ∓ 2 e (a) obtenha u, v ∈ Z tais que (2u)2 − n(2v)2 = 4.
(c) Usando (b) ache soluções da equação de Pell x2 − ny 2 = 1 em termos de x0 e y0 .
(d) Usando (c) obtenha uma solução da equação de Pell x2 − 7y 2 = 1 a partir da
solução (3, 1) de x2 − 7y 2 = 2.
CAPíTULO 2
Grupos finitos
Neste capítulo introduzimos várias noções importantes da teoria de grupos, como subgrupos e grupos cíclicos, e provamos o teorema de Lagrange. Como os grupos mais importantes no estudo da teoria de números e da criptografia têm uma quantidade finita de
elementos, vamos nos concentrar em estudar este caso.
1. Inversíveis módulo n
Começamos relembrando que um grupo é um conjunto não vazio, no qual está definida
uma operação que é fechada, associativa, comutativa, tem elemento neutro e relativamente
ao qual todo elemento do conjunto admite um inverso. Quando a operação de um grupo é
a soma, diremos que se trata de um grupo aditivo; quando for a multiplicação, temos um
grupo multiplicativo. Assim, Z e Zn são grupos aditivos, ao passo que Q \ {0} é um grupo
multiplicativo.
Como já foi dito, ao longo de todo o capítulo nos concentramos em estudar os grupos
finitos; isto é, aqueles cujo conjunto subjacente tem uma quantidade finita de elementos.
O número de elementos de um grupo, conhecido como a ordem do grupo, desempenha
um papel muito importante no estudo dos grupos finitos. Por isso, precisaremos sempre
determinar as ordens dos grupos que estudarmos daqui em diante.
O conjunto das classes inversíveis módulo um inteiro positivo n será denotado por
U(n). O teorema da inversão nos permite escrever este conjunto na forma,
U(n) = {a ∈ Zn | mdc(a, n) = 1}.
A operação que torna este conjunto um grupo é a multiplicação usual de classes em Zn .
Como vimos no capítulo anterior, esta operação é associativa, comutativa e tem como
elemento neutro a classe de 1; que todo elemento de U(n) tem inverso em U(n) é mera
consequência da definição de U(n). Contudo, ainda não sabemos se a multiplicação é
fechada em U(n). O que sabemos com certeza é que o produto de duas classes módulo n
é uma classe módulo n; mas será que, do produto de duas classes que são inversíveis em
Zn , resulta uma classe que também é inversível? Para provar isto, considere a e b duas
classes inversíveis em Zn e digamos que seus inversos são, respectivamente, a′ e b′ . Então,
25
26
2. GRUPOS FINITOS
da associatividade e da comutatividade da multiplicação de classes, temos que
(a · b) · (a′ · b′ ) = (a · a′ ) · (b · b′ )
que é claramente igual a 1. Isto significa que o inverso de a · b é a classe a′ · b′ . Em
particular, o produto de duas classes inversíveis é uma classe inversível, confirmando que
a multiplicação usual de classes é fechada em U(n).
É fácil determinar todos os elementos do grupo dos inversíveis módulo n quando n é
primo, porque neste caso todas as classes não nulas são inversíveis. De fato, se n for primo,
então mdc(a, n) = 1 para todo inteiro 1 ≤ a ≤ n − 1. Outro caso em que os elementos de
U(n) são fáceis de enumerar ocorre quando n é potência de 2. Isto porque
mdc(a, 2m ) = 1
se, e somente se,
mdc(a, 2) = 1,
qualquer que seja o inteiro positivo m. Logo, as classes em U(2m ) correspondem aos
inteiros ímpares entre 1 e 2m . Em geral, achar os elementos de U(n) quando n é um
número composto é um problema bem mais delicado. Por exemplo,
U(12) = {1, 5, 7, 11};
ao passo que
U(15) = {1, 2, 4, 7, 8, 11, 13, 14}.
Encerraremos a seção considerando como calcular a ordem de U(n). Vimos acima que
U(p) = Zp \ {0},
quando p > 1 é um número primo, de modo que
#U(p) = p − 1.
Outro caso fácil de analisar é aquele em que o módulo é uma potência de primo. Como no
caso das potências de 2, a descrição dos elementos do conjunto U(pk ) é bastante simples.
O ponto chave é que, se a for um inteiro não nulo, então mdc(a, pk ) só pode ser diferente
de 1 quando p dividir a. Isto nos permite escrever
U(pk ) = {a ∈ Zpk | p não divide a}.
Portanto, a ordem de U(pk ) é igual à quantidade de inteiros a, no intervalo 0 ≤ a < pk ,
que não são divisíveis por p. Na prática é mais fácil contar os inteiros entre 0 e pk que
são divisíveis por p e subtrair isto de pk , que é o total de inteiros maiores ou iguais a 0 e
menores que pk . Portanto, os inteiros que desejamos contar satisfazem
0 ≤ a < pk
e
a = pℓ,
em que ℓ é o cofator de p em a. Substituindo a = pℓ na desigualdade, obtemos
0 ≤ pℓ < pk ;
que, divindo por p, nos dá
0 ≤ ℓ < pk−1 .
2. PELL MODULAR E SUAS GENERALIZAÇÕES
27
Assim, a cada inteiro ℓ neste intervalo, corresponde pℓ, mas este é um múltiplo de p que
satisfaz a desigualdade desejada. Logo, existem pk−1 múltiplos de p entre 0 e pk , donde
(20)
#U(pk ) = pk − pk−1 = pk−1 (p − 1).
Em geral, o cálculo da ordem de U(n) requer que saibamos fatorar completamente o módulo n. Contudo, como a análise do caso geral requer a noção de isomorfismo de grupos,
que será introduzida na seção 1 do capítulo 3, só estaremos em condição de fazê-la na
seção 5 daquele capítulo. Apesar disso, vale a pena notar desde já que, como veremos no
capítulo ???, é o fato do cálculo da ordem de U(n) depender da fatoração de n que torna o
RSA seguro.
2. Pell modular e suas generalizações
Dados dois inteiros n e d maiores que um, definimos a equação de Pell modular por
x2 − dy 2 = 1
(21)
cujos coeficientes são classes em Zn . Uma solução de (21) consiste de um par [x0 , y0] ∈
Zn × Zn , de classes de inteiros módulo n, que satisfaz
x0 2 − dy0 2 = 1.
Como no caso da equação de Pell usual,
[1, 0] e
[−1, 0] = [n − 1, 0]
são soluções, que continuaremos a chamar de triviais, da equação de Pell modular, quaisquer que sejam os inteiros d > 1 e n > 1. Portanto, o conjunto P(d, n) das soluções da
equação de Pell modular (21) nunca é vazio.
Assim como no caso da equação de Pell usual, o conjunto solução da equação de Pell
modular é um grupo relativamente à operação ⊗ que associa aos elementos
P1 = (a1 , b1 ) e
P2 = (a2 , b2 )
de P(d, n) o par
(22)
P1 ⊗ P2 = (a1 a2 + db1 b2 , a1 b2 + b1 a2 ).
Para mostrar que esta operação é fechada em P(d, n), basta reduzir módulo p a igualdade
(2) da página 2. A verificação da associatividade e da comutatividade é igualmente simples.
Além disso, (1, 0) funciona como elemento neutro e o inverso de (x0 , y0 ) ∈ P(d, n) é o par
(x0 , −y0 ) ∈ P(d, n), exatamente como no caso da equação de Pell usual. Portanto, P(d, n)
é, de fato, um grupo relativamente à operação ⊗.
Vejamos alguns exemplos. Para começar, se (x0 , y0) é solução da equação de Pell usual
x2 − dy 2 = 1
28
2. GRUPOS FINITOS
então o par
[x0 , y0 ] ∈ Zn × Zn ,
obtido tomando-se as classes correspondentes módulo n é solução de
x0 2 − dy0 2 = 1.
Por exemplo, como (3, 2) é solução de x2 − 2y 2 = 1, então
(3, 2) ∈ Zp × Zp
é solução não trivial de x −2y = 1, qualquer que seja o primo p > 2. Note que a restrição
p > 2 é necessária, porque quando p = 2 a solução (3, 2) se reduz a (1, 0). Entretanto,
mesmo neste caso, a equação x2 − 2y 2 = 1 tem soluções não triviais. Isto se dá porque,
2
2
x2 − 2y 2 = x2
quando os coeficientes estão em Z2 , de modo que
P(2, 2) = {(1, 0), (1, 1)}.
De agora em diante, vamos supor, quase sempre, que o módulo p > 2 é primo pois,
como veremos na seção 2 do capítulo 3, a equação x2 − dy 2 = 1 sempre tem soluções não
triviais quando o módulo é um primo ímpar. Como no caso da equação de Pell usual, há
dois casos a considerar, dependendo se d é ou não um quadrado módulo p. Vejamos alguns
exemplos. Para começar, considere a equação
(23)
x2 − 2y 2 = 1 em Z3 .
Além de [±1, 0], a equação de Pell usual x2 − 2y 2 = 1 tem como solução [3, 2]. Portanto,
[3, 2] = [0, 2]
também é solução de (23). Contudo, os três pares
[1, 0], [n − 1, 0]
e
[0, 2]
não esgotam todas as soluções de (23). Por exemplo, tomando x = 0, a equação se torna
−2y 2 = 1
Como 2 = −1, esta última igualdade equivale a
y 2 = 1;
que é satisfeita por y = 1 e por y = 2 em Z3 ; de modo que obtivemos duas novas soluções. Além disso, não pode haver novas soluções, porque já havíamos obtido as soluções
possíveis com x 6= 0. Portanto,
P(2, 3) = {[1, 0], [2, 0], [0, 1], [0, 2]}.
Outro exemplo interessante é a equação x2 − 3y 2 = 1 em Z7 . Como, −3 ≡ 4 ≡ 22
(mod 7), podemos reescrever a equação dada na forma
(24)
x2 + (2y)2 = 1.
2. PELL MODULAR E SUAS GENERALIZAÇÕES
29
Quando x = 0, obtemos
(2y)2 = 1.
Como 7 é primo, as únicas soluções da congruência z 2 = 1 em Z7 são 1 e 6, de modo que
2y = 1 ou 2y = 6.
Resolvendo estas equações lineares concluímos que y = 4 e y = 3, respectivamente.
Portanto, [0, 4] e [0, 3] são as soluções de (24) quando x = 0. Passando, agora ao caso em
que x = ±1, obtemos
1 + (2y)2 = 1 donde (2y)2 = 0.
Como 7 é primo isto só é possível se y = 0. Portanto, neste caso, as soluções são [1, 0] e
[6, 0]. Por outro lado, quando x = ±2, temos
4 + (2y)2 = 1 donde (2y)2 = −3 = 4;
de modo que 2y = ±2; isto é, y = ±1. Com isto, obtemos as soluções [±2, ±1]; isto é,
[2, 1], [2, 6], [5, 1] e [5, 6]. Finalmente, se x = ±3, então
2 + (2y)2 = 1, que equivale a (2y)2 = 6.
Mas esta última equação não tem solução porque 6 não é o quadrado de nenhuma classe
de inteiro módulo 7. Portanto, concluímos que
P(2, 7) = {[1, 0], [6, 0], [0, 4], [0, 3], [2, 1], [2, 6], [5, 1], [5, 6]}.
Há um outro grupo finito, definido de maneira semelhante a P(d, n), e que desempenhará um papel importante no cálculo da ordem deste último grupo. Como no caso da
equação de Pell modular, sejam d > 2 um inteiro e p ≥ 2 um número primo. Dados dois
elementos P1 e P2 no conjunto Z2p = Zp × Zp , definimos seu produto P1 ⊗ P2 usando a
fórmula (22). Como esta é a mesma regra que define a multiplicação em P(d, n), podemos
usar o mesmo símbolo para denotar a operação nestes dois conjuntos sem haver risco de
confusão. É claro que ⊗ é fechada em Z2p . Além disso, é fácil verificar que esta operação
é associativa, comutativa e tem (1, 0) como elemento neutro. Portanto, para que Z2p seja
um grupo com a operação ⊗ basta que cada um de seus elementos tenha inverso. Para
determinar isto, digamos que, sendo
P1 = (a1 , b1 )
e
P2 = (a2 , b2 ),
temos
P1 ⊗ P2 = (1, 0).
Usando (22) e comparando as coordenadas dos pontos dos dois lados da igualdade, verificamos que
(25)
a1 · a2 + d · b1 · b2 = 1 e
a1 · b2 + b1 · a2 = 0.
Como a primeira destas equação não é satisfeita quando P1 = (0, 0), podemos afirmar que
(0, 0) não tem inverso em Z2p . Isto significa que Z2p não é um grupo, mas não encerra nossa
análise, porque a pergunta seguinte, naturalmente, é: quais são os elementos de Z2p que têm
30
2. GRUPOS FINITOS
inverso? Que há elementos com inverso neste conjunto é claro; os exemplos mais óbvios
são (±1, 0). Mas será que há algum outro, além destes? Para isto voltamos às equações
(25). Suponhamos, por exemplo, que a primeira coordenada de P1 não se anula em Zp ; isto
é, que a1 6= 0. Multiplicando a primeira equação em (25) por a1 e usando que, da segunda
equação,
(26)
a1 · b2 = −b1 · a2 ,
obtemos
2
a2 (a1 2 − d · b1 ) = a1 .
(27)
Portanto, esta equação só é satisfeita por um par P2 = (a2 , b2 ) se
(28)
a2 6= 0 e
(29)
a1 2 − d · b1 6= 0.
2
Note que há uma enorme diferença entre estas duas desigualdades. Enquanto (28) impõe
uma restrição sobre P2 , que é o ponto que queremos determinar, (29) restringe o par que
queremos inverter. Isto é, pares que não satisfazem (29) não são inversíveis. Nossa análise
se torna mais clara se introduzirmos a seguinte terminologia. A norma de um par Q =
(a, b) ∈ Z2p é a classe
2
ν(Q) = a2 − d · b ∈ Zp .
Note que a norma depende da escolha de p e d. Com esta notação, (29) nos diz que
qualquer par cuja norma é 0 não terá inverso em Z2p . Para caracterizar completamente os
elementos inversíveis de Z2p só nos falta mostrar que se ν(P1 ) 6= 0, então P1 é inversível.
Mas, de um cálculo direto, usando a definição de ⊗, obtemos
(30)
(a1 , b1 ) ⊗ (a1 , −b1 ) = (ν(P1 ), 0).
Como o módulo p é primo, então ν(P1 ) 6= 0 tem inverso ν(P1 )′ em Zp , e podemos deduzir
de (30) que
(a1 , b1 ) ⊗ (a1 · ν(P1 )′ , −b1 · ν(P1 )′ ) = (1, 0).
Mostramos, assim, que P = (a, b) tem inverso em Z2p se, e somente se, ν = ν(P ) 6= 0.
Além disso, se o inverso de P existe, então é igual a (a·ν ′ , −b·ν ′ ). Por exemplo, escolhendo
d = 5, podemos facilmente determinar que o inverso de P = (2, 7) em Z213 é igual a
(112, −117) = (9, 1).
pois
2
2
ν(P ) = 2 − 57 = −7 = 6;
tem como inverso 11 em Z13 .
É hora de parar e considerar exatamente o que descobrimos até aqui. Para começar,
vimos que, uma vez fixado o valor de d, a operação ⊗ em Z2p é fechada, associativa, comutativa e tem (1, 0) como elemento neutro. Por outro lado, somente os pares cuja norma não
2. PELL MODULAR E SUAS GENERALIZAÇÕES
31
é a classe nula têm inverso em Z2p . Como a norma do par (0, 0) é nula não importa quais
sejam os valores de d e p, temos que Z2p não não é um grupo para todo d e p. Entretanto,
copiando o que fizemos no caso de Zp , podemos considerar o conjunto
U(d, p) = {P ∈ Zp × Zp | ν(P ) 6= 0},
formado apenas pelos elementos de Z2p que são inversíveis. Como a operação ⊗ é associativa e comutativa em Z2p , continuará satisfazendo estas propriedades quando restrita aos
elementos de U(d, p). Por outro lado, (1, 0) tem norma 1, portanto pertence a U(d, p), que
foi definido como o subconjunto dos elementos inversíveis de Z2p . Portanto, precisamos
apenas mostrar que ⊗ é fechada em U(d, p), para garantir que este conjunto é um grupo.
Há duas maneiras fáceis de fazer isto. A primeira é copiar, com as devidas modificações, a
prova de que a multiplicação em U(p) é fechada; ver página 26. A outra consiste em usar
a igualdade
(31)
ν(P1 ⊗ P2 ) = ν(P1 ) · ν(P2 ),
para todo P1 , P2 ∈ Z2p ; que é apenas a identidade (2) escrita em uma notação diferente. Se
P1 , P2 ∈ U(d, p), então suas normas não podem ser nulas. Como p é primo isto significa
que ν(P1 ) · ν(P2 ) 6= 0. Logo, ν(P1 ⊗ P2 ) 6= 0 por (31), o que prova que P1 ⊗ P2 ∈ U(d, p).
No caso em que p é um número primo, sabemos que U(p) consiste de todas as classes
não nulas de Zp . Diante do fato de que U(d, p) está para Z2p assim como U(p) está para
Zp , é razoável perguntarmos quando U(d, p) coincide com o subconjunto formado pelos
pares de Z2p que têm pelo menos uma coordenada não nula. Como os pares de U(d, p)
são aqueles cuja norma é não nula, a pergunta acima pode ser reformulada na forma: para
quais valores de d e p o único par em Z2p cuja norma é zero é (0, 0)?
Para responder a esta pergunta, tomaremos um par P = (a, b) e suporemos que sua
norma é nula; isto é, que
(32)
2
ν(P ) = a2 − db = 0.
Como b = 0 implica que a = 0, podemos supor que b 6= 0. Mas p é primo, de modo que
todo elemento não nulo de Zp tem inverso. Multiplicando ambos os membros de (32) pelo
inverso b′ , de b, em Zp , e rearrumando a equação, obtemos
2
d = a2 b′ = (a · b′ )2 .
Logo, um par diferente de (0, 0) em Z2p só pode não ter inverso relativamente à operação
⊗ se d puder ser escrito como o quadrado de uma classe em Zp .
Seguindo a terminologia proposta por Gauss no artigo 95, da seção 4, de suas Disquisitiones arithmeticae, diremos que um inteiro d é um resíduo quadrático módulo p se d 6≡ 0
(mod p) e existe um inteiro a tal que d ≡ a2 (mod p). Naturalmente isto equivale a dizer
que d = a2 em Zp . Com isto, podemos formular o enunciado do final do parágrafo anterior
da seguinte forma.
32
2. GRUPOS FINITOS
Proposição. Sejam d > 1 e p > 2 números inteiros e suponhamos que p é primo. Então,
U(d, p) = Z2p \ {(0, 0)}
se, e somente se, d não é resíduo quadrático módulo p.
Portanto, para responder à pergunta feita acima de maneira completa resta-nos apenas
determinar quais são os inteiros que são resíduos quadrados módulo p. Para simplificar a
terminologia diremos que uma classe em Zp é um resíduo quadrático quando ela tiver um
representante que é um resíduo quadrático módulo p. Por exemplo, como os quadrados
dos elementos não nulos de Z5 são
2
1 = 1,
2
2 = 4,
2
3 = 4,
2
4 = 1,
então 4 e 1 são os únicos resíduos quadráticos módulo 5. Já módulo 13 a situação é bastante
diferente. Como mostra a tabela 1, os resíduos quadráticos módulo 13 são 1, 3, 4, 9, 10 e
12.
Classes 1 2 3 4 5 6 7 8 9 10 11 12
Quadrados 1 4 9 3 12 10 10 12 3 9 4 1
TABELA 1. Quadrados módulo 13
De uma inspecção, mesmo que superficial, da tabela 1, salta aos olhos que os quadrados
módulo 7 são simétricos em relação à metade da tabela. Isto não ocorre apenas no caso
em que o módulo é 7, mas qualquer que seja o módulo ímpar n, e é mera consequência da
congruência a2 ≡ (n − a)2 (mod n). Como resultado, temos que a quantidade de inteiros
entre 1 e p − 1 que são resíduos quadráticos módulo um primo p não pode ser maior do
que (p − 1)/2. Por outro lado, se x e y são inteiros tais que x2 ≡ y 2 (mod p), então, como
p é primo, temos que
x≡y
(mod p) ou
x ≡ −y
(mod p).
Supondo que 1 ≤ x ≤ y ≤ n − 1, esta congruência nos permite concluir que
y = x ou
y = n − x.
Portanto, se p é primo, então metade dos inteiros entre 1 e p − 1 é formada por resíduos
quadráticos e a outra metade por não resíduos. Em particular, não faltam não resíduos
para usar na construção de U(d, p), qualquer que seja p > 2. Por exemplo, consultando a
tabela 1, vemos que 5 não é resíduo quadrático módulo 13, de modo que o grupo U(5, 13)
contém todos os pares não nulos de Z2p .
2. PELL MODULAR E SUAS GENERALIZAÇÕES
33
Encerraremos esta seção com a caracterização dos elementos de P(d, p) que têm ordem
2. Já sabemos que há pelo menos um tal elemento, porque
(−1, 0)2 = (1, 0)
em P(d, p), sejam quais forem o inteiro d e o primo p. Suponhamos que p > 0 seja um
primo ímpar e seja P = (a, b) um outro elemento de ordem dois no mesmo grupo. Neste
caso,
2
P 2 = (a2 + db , 2 · a · b)
tem que ser igual ao elemento neutro (1, 0). Pela propriedade fundamental dos primos, isto
só pode ocorrer se p divide a ou b. Mas se p divide b, então segue de
2
a2 + db = 1
que a = ±1, e P seria o ponto (−1, 0), contradizendo nossa hipótese. Resta, apenas, que
p divida a; donde obtemos que
2
db = 1.
Entretanto, como b2 e 1 são resíduos quadráticos módulo p, então d tem que ser um resíduo
quadrático módulo p; veja o exercício 3. Em particular, P(d, p) contém apenas um elemento de ordem dois quando d não for resíduo quadrático módulo p. Suponhamos, então,
que d > 1 seja um resíduo quadrático módulo p. Neste caso, existe um inteiro positivo β
tal que d ≡ δ 2 (mod p). Denotando por β ′ o inverso de β em U(p) temos que
2
2
2
(±β ′ , 0)2 = (d · β ′ , 0) = (β · β ′ , 0)
é o elemento neutro de P(d, p). Resumindo o que aprendemos, temos o seguinte resultado.
Proposição. Se p > 2 é um primo e d > 1 é um número inteiro então o grupo P(d, p)
contém um ou três elementos de ordem dois, dependendo se d não é ou é resíduo quadrático
módulo p.
Como no caso dos inversíveis módulo n, encerraremos a seção considerando como
proceder para calcular a ordem dos grupos #P(d, p) e #U(d, p). Se p é primo e d não é
um resíduo quadrático módulo p, então sabemos que #U(d, p) contém todos os pares de
Z2p que não têm ambas as coordenadas nulas. Como há p2 elementos em Z2p , temos que
#U(d, p) = p2 − 1.
Já o cálculo da ordem do conjunto solução da equação de Pell x2 − dy 2 = 1 é bem mais
difícil, mesmo quando d não é um resíduo quadrático módulo p. Na verdade, este cálculo
depende da noção de isomorfismo de grupos, que também usaremos para determinar a
ordem de U(n) quando n é composto; por isso vamos adiar os detalhes até a seção 2 do
capítulo 3.
34
2. GRUPOS FINITOS
3. Subgrupos
Na seção anterior vimos que, se p > 2 é um primo e d não é resíduo quadrático módulo p, então P(d, p) ⊂ U(d, p) são ambos grupos relativamente à mesma operação ⊗.
Situações como essa são bastante comuns, por exemplo
Z⊂Q⊂R⊂C
são todos grupos relativamente à soma e
Q \ {0} ⊂ R \ {0} ⊂ C \ {0}
são todos eles grupos relativamente à multiplicação. Quando temos um grupo contido
em outro e ambos partilham a mesma operação, diremos que o grupo menor é subgrupo
do maior. Note que estamos deliberadamente excluindo exemplos como Q \ {0}, com a
operação de multiplicação, e Q, com a operação de soma, em que Q \ {0} é subconjunto
de Q, mas as operações são distintas. A razão pela qual casos como este são excluídos é
puramente pragmática. Quando os conjuntos não partilham a mesma operação suas propriedades como grupos podem ser inteiramente diferentes. Já quando partilham a operação,
as propriedades de um dos grupos influencia fortemente as propriedades do outro grupo,
como veremos ao longo desta seção e da seguinte.
A definição oficial é a seguinte. Sejam G um grupo com a operação ⋆ e S é um subconjunto de G. Diremos que S é um subgrupo de G se S é ele próprio um grupo relativamente
à mesma operação ⋆ de G. Esta definição é muito boa, porque é compacta e bastante aceitável do ponto de vista intuitivo; mas é ruim quando se trata de determinar se um dado
subconjunto de um grupo é realmente um subgrupo, porque nos leva a testar muitas propriedades que são automaticamente satisfeitas por todo subconjunto de um grupo.
Para entender melhor o que está em jogo, voltemos à situação em que S ⊂ G e G é um
grupo. Das cinco propriedades de grupo, a associatividade e comutatividade correspondem
a identidades que têm que ser satisfeitas, quaisquer que sejam os elementos escolhidos em
G. Como S ⊂ G, estas identidades terão que ser verdadeiras quando escolhemos estes
elementos em S. Portanto, para determinar se um subconjunto S de um grupo G é ou não
um subgrupo basta testarmos as outras três propriedades que definem um grupo. Temos,
assim, o seguinte critério.
Critério. Um subconjunto S de um grupo G é um subgrupo se:
• a operação de G é fechada em S;
• o elemento neutro de G pertence a S;
• o inverso de cada elemento de S também está em S.
3. SUBGRUPOS
35
Usando o critério acima é fácil verificar que o conjunto dos números pares é um subgrupo aditivo do conjunto de todos os números inteiros, mas o mesmo não vale para o
conjunto dos ímpares, já que nem é fechado para a soma, nem contém o elemento neutro
0. Um argumento semelhante mostra que qualquer que seja o inteiro n, o conjunto dos
múltiplos de n é um subgrupo do grupo aditivo de todos os números inteiros.
É igualmente fácil construir subgrupos em grupos mais gerais. Para começar, todo
grupo contém pelo menos dois subgrupos distintos, aquele que contém apenas o elemento
neutro do grupo e o que corresponde ao grupo inteiro. Um exemplo mais interessante é o
seguinte. Seja G um grupo dotado de uma operação ⋆. O conjunto
Q(G) = {g 2 | g ∈ G},
dos elementos que são quadrados em G, é um subgrupo de G. Para provar isto usaremos o
critério acima. Em primeiro, dados dois elementos g 2 e h2 em Q, seu produto
g 2 ⋆ h2 = (g ⋆ h)2
também é um quadrado e, portanto, pertence a Q(G). Por outro lado, se e é o elemento
neutro de G, então e2 = e, de modo que e ∈ Q. Finalmente, se o inverso de g for g ′ , então
o inverso de g 2 será (g ′ )2 , pois
g 2 ⋆ (g ′)2 = (g ⋆ g ′)2 = e2 = e.
Logo, pelo critério, Q(G) é um subgrupo de G. Em particular, o conjunto das classes de
Zp cujos representantes são resíduos quadráticos módulo um primo p é um subgrupo do
grupo multiplicativo U(p).
Um outro exemplo, muito importante em criptografia, é o seguinte. Digamos, como
acima, que G é um grupo finito com operação ⋆ e elemento neutro e. Se g ∈ G, então
considere o conjunto
hgi = {g k | k ≥ 0}
formado pelas potências de expoente não negativo de g. Como
g k ⋆ g ℓ = g k+ℓ ,
o conjunto hgi é fechado relativamente à operação ⋆. O elemento neutro corresponde a
g 0, logo pertence a hgi. Até aqui não utilizamos a hipótese de que G é finito, mas ela é
necessária para mostrarmos que os inversos dos elementos de hgi também pertencem a hgi.
A primeira coisa a notar é que a sequência de expoentes é infinita, já que há um expoente
para cada inteiro não negativo. Contudo, como G é finito e hgi ⊂ G, então hgi também
é um conjunto finito. Isto só é possível se houver expoentes distintos que correspondem a
uma mesma potência; isto é, se
gi = gj
para dois inteiros
0 ≤ i < j.
Multiplicando ambos os lados desta equação por (g ′)i , obtemos
g j−i = e.
36
2. GRUPOS FINITOS
Como j − i > 0, há potências de g, com expoente positivo, que são iguais ao elemento
neutro. Se k > 0 for o menor expoente com esta propriedade, teremos que
hgi = {e, g, . . . , g k−1}.
Além disso, duas potências de g com expoentes menores que k não podem coincidir, porque supondo que 0 < i < j < k no argumento acima, concluiríamos que g j−i = e, o que
não é possível pela escolha de k porque 0 < j − i < k. Finalmente, como g k = e, temos
que se 0 ≤ i < k, então
g i ⋆ g k−i = g k = e.
Porém, k − i > 0, de modo que g k−i ∈ hgi. Logo, hgi é um subgrupo de G.
Como os elementos de hgi correspondem a potências que se repetem em um ciclo
com k elementos, os subgrupos construídos desta maneira são chamados de cíclicos. O
elemento g é um gerador de hgi. Como um grupo sempre é subgrupo de si próprio, os
termos cíclico e gerador podem ser aplicados a qualquer grupo. Os subgrupos cíclicos são
os mais fáceis de construir, mas nem todo subgrupo é cíclico. Por exemplo, o grupo
U(8) = {1, 3, 5, 7}
não é cíclico porque
2
2
2
3 = 5 = 7 = 1,
de modo que nenhum de seus elementos é gerador, já que nenhum deles tem mais de duas
potências distintas.
Se g é um elemento de um grupo G, então o menor expoente k para o qual g k é o
elemento neutro de G é igual à quantidade de elementos, isto é, à ordem, do subgrupo
hgi. Para simplificar a terminologia, diremos ordem do elemento g, em vez de usar a
expressão mais precisa, mas muito mais complicada, ordem do subgrupo cíclico gerado
pelo elemento g. Note que a ordem de uma classe em Zn , definida no capítulo ???, coincide
com a ordem daquela classe em U(n), no sentido acima.
4. O teorema de Lagrange
É difícil exagerar a importância do conceito de ordem na teoria de grupos finitos. Como
veremos neste capítulo, o conhecimento da ordem de um grupo pode ser suficiente para
descrever completamente a estrutura deste grupo. Este é o caso, por exemplo, dos grupos
cuja ordem é um número primo. O primeiro resultado no caminho para justificar estas
afirmações é o seguinte teorema, provado por J.-L. Lagrange em ????.
T EOREMA DE L AGRANGE . Se G é um grupo finito e S é um subgrupo de G, então a
ordem de S divide a ordem de G.
4. O TEOREMA DE LAGRANGE
37
Para provar o teorema, precisamos contar a quantidade de elementos que G tem, relacionando-a à quantidade de elementos de S. Como sempre, denotaremos por ⋆ a operação
em G e por e seu elemento neutro. Digamos, também, que
S = {h1 , . . . , hk },
em que h1 = e; naturalmente estamos supondo que os h’s são todos distintos. Vamos
enumerar os elementos de G da seguinte maneira. Começando com e, listamos
h1 , h2 , . . . , hk
que são os elementos de G obtidos multiplicando-se e pelos vários elementos de S. Se
G = S, não há mais nada a fazer e o resultado desejado é óbvio. Se S ( G, escolhemos
um elemento qualquer g1 ∈ G \ S e listamos
h1
h2
...
hk
g1 ⋆ h1 g1 ⋆ h2 . . . g1 ⋆ hk
Denotando a segunda linha da tabela por g1 ⋆ S, para lembrar como seus elementos foram
construídos, temos duas possibilidades. Se G = S ∪ (g1 ⋆ S) o processo para; senão,
escolhemos g2 ∈ G = S \ (g1 ⋆ S) e adicionamos à tabela a linha g2 ⋆ S, obtendo
h1
h2
...
hk
g1 ⋆ h1 g1 ⋆ h2 . . . g1 ⋆ hk
g2 ⋆ h1 g2 ⋆ h2 . . . g2 ⋆ hk
O processo continua dessa maneira até que todos os elementos de G estejam na tabela, o
que acontecerá inevitavelmente, pois estamos supondo que G tem uma quantidade finita
de elementos.
Vejamos como a tabela ficaria se o grupo fosse U(13) e S fosse o subgrupo cíclico
gerado 3. Como
2
3 =9 e
3
3 = 27 = 1
temos que
S = h3i = {1, 3, 9},
cujos elementos formarão a primeira linha da tabela. Para construir a segunda linha da
tabela precisamos de um elemento de U(13) que não pertença a S; por exemplo, 2. Como
2·3=6 e
2·9=5
as duas primeiras linhas da tabela serão
1 3 9
2 6 5
38
2. GRUPOS FINITOS
Mas isto ainda não esgota os elementos de U(13), já que a tabela acima ainda não contém
seis elementos deste grupo. Escolhemos, então, um dos elementos que ainda não estão na
tabela, por exemplo 8. Levando em conta que
8 · 3 = 11 e
8·9 =7
podemos adicionar mais uma linha a tabela, obtendo:
1 3 9
2 6 5
8 11 7
Precisamos executar mais um passo, pois ainda restam elementos de fora da tabela. Mas 4
é um destes elementos e
4 · 3 = 12 e 4 · 9 = 10
de modo que a tabela completa será
1 3 9
2 6 5
8 11 7
4 12 10
Como esta tabela tem #S = 3 colunas e 4 linhas e cada elemento de U(13) aparece
exatamente em uma casa da tabela, podemos afirmar que
#U(13) = #S · 4,
como afirma o teorema de Lagrange.
Como a conta ao final deste exemplo sugere, para provar o teorema de Lagrange precisamos apenas mostrar que não pode haver elementos repetidos na tabela. Mas isto é muito
fácil de fazer. Voltando ao caso geral em que o grupo é G e o subgrupo é S, suponhamos que haja dois elementos iguais a tabela. Digamos que um deles esteja na linha cujo
primeiro elemento é gi e na coluna cujo primeiro elemento é hr , ao passo que o outro elemento está na linha iniciada por gj e na coluna iniciada por ht . Em outras palavras, o que
estamos supondo é que
gi ⋆ hr = gj ⋆ ht .
Se i = j, multiplicamos esta equação pelo inverso de gi = gj , obtendo hr = ht , o que contradiz nossa hipótese de que os h’s são todos distintos. Mas, se i < j, então, multiplicando
a equação pelo inverso h′t de ht , obtemos
gj = gi ⋆ hr ⋆ h′t ,
o que também não é possível, porque gj foi escolhido de modo a não pertencer a nenhuma
das linhas anteriores da tabela, ao passo que gi ⋆ hr ⋆ h′t pertence à linha iniciada por gi .
Portanto, não há elementos repetidos na tabela. Logo, a quantidade de elementos de G é
5. APLICAÇÕES
39
igual à quantidade de linhas da tabela vezes a quantidade de colunas. Como esta última é
igual a #S, o teorema está provado.
A aplicação mais imediata do teorema de Lagrange é à determinação dos subgrupos de
um dado grupo. Por exemplo, digamos que queremos achar todos os subgrupos do grupo
multiplicativo
U(16) = {1, 3, 5, 7, 9, 11, 13, 15}.
Este grupo tem ordem 8, logo só pode ter subgrupos de ordem 1, 2, 4 ou 8. Os subgrupos
de ordem 1 e 8 são {1} e U(16), respectivamente. Antes de prosseguir, vamos determinar
as ordens de todos os elementos de U(16). Um cálculo fácil mostra que os elementos de
ordem 2 são 7, 9, 15 e os elementos de ordem 4 são 3, 5, 11 e 13. De imediato podemos
concluir que U(16) não é cíclico, porque não tem nenhum elemento de ordem 8. Além
disto, este grupo tem um subgrupo próprio que não é cíclico. Isto acontece porque o
conjunto
{1, 7, 9, 15}.
é um subgrupo de U(16), mas seus elementos têm ordem menor ou igual a 2. Note que
este subgrupo tem ordem 4, um número composto. Isto não é mera coincidência, como
veremos na próxima seção, todo grupo de ordem prima tem que ser cíclico. Logo, em um
grupo qualquer, se um subgrupo não é cíclico então sua ordem tem que ser um número
composto.
5. Aplicações
Nesta seção veremos algumas aplicações do teorema de Lagrange. Para a primeira
delas, suporemos que G é um grupo finito e que g é um elemento de G, diferente do
elemento neutro e. Pelo teorema de Lagrange, a ordem do grupo cíclico gerado por g
divide a ordem de G. Em particular, se a ordem de G for um número primo p, então a
ordem de qualquer um de seus subgrupos será igual a 1 ou à ordem de G. Como
e 6= g ∈ hgi ⊆ G,
temos que a ordem de hgi não pode ser 1. Portanto, hgi tem ordem p, o que só pode
acontecer se
hgi = G.
Mostramos, assim, que em um grupo de ordem prima, todo elemento diferente da identidade é um gerador.
Infelizmente, este resultado só se aplica a U(p) quando p = 3, porque apesar de p ser
primo, a ordem de U(p) é igual a p − 1, que é um número par, composto, quando p > 3.
Contudo, a aplicação do teorema de Lagrange ao grupo U(p) dá um resultado já nosso
conhecido. De fato, se p é primo e a ∈ Zp não é a classe do zero então, pelo teorema de
40
2. GRUPOS FINITOS
Lagrange, a ordem de hai divide p − 1, que é a ordem de U(p). Entretanto, como vimos na
seção 3, a ordem de hai coincide com o menor inteiro k > 0 para o qual ak = 1. Mas, de
p − 1 = #U(p) = k · ℓ,
para algum inteiro positivo ℓ, podemos concluir que
ap−1 = akℓ = (ak )ℓ = 1,
que é o que nos diz o teorema de Fermat. Portanto, o teorema de Fermat é uma consequência imediata do teorema de Lagrange.
Nosso próximo exemplo é bem mais ambicioso. Suponhamos que 1 < p < q são
números primos e que G é um grupo de ordem pq. O que podemos afirmar, a respeito de
um tal grupo, sabendo apenas a sua ordem? A primeira coisa a observar é que existem
grupos cíclicos de ordem pq; um exemplo simples é o grupo aditivo Zpq , que é gerado por
1. Podemos, então, reformular a pergunta da seguinte forma: existem grupos de ordem pq
que não são cíclicos ?
Suponhamos, para começar, que G é um grupo finito cujo elemento neutro é e. Digamos que S1 e S2 são subgrupos próprios de G e que a ordem de S1 é prima. Pelo que
provamos acima, isto implica que qualquer elemento de S1 , diferente de e, gera o subgrupo
S1 inteiro. Em particular, se
e 6= q ∈ S1 ∩ S2
então q gera S1 , de modo que
S1 = hqi = S1 ∩ S2 ⊂ S2 .
Provamos assim o seguinte resultado.
L EMA 5.1. Sejam G um grupo finito e S1 e S2 subgrupos próprios de G. Se S1 tem
ordem prima, então S1 ⊆ S2 ou S1 ∩ S2 = {e}.
Digamos, agora, que G não seja cíclico e que tenha ordem pq. Das duas uma: ou G
tem elementos de ordem p e elementos de ordem q, ou todos os elementos de G \ {e} têm a
mesma ordem. Analisaremos este dois casos separadamente, começando com o primeiro.
Sejam, pois, g e h elementos de G cujas ordens são, respectivamente, p e q. Se r for a
ordem de g ⋆ h, então
(g ⋆ h)r = g r ⋆ hr = e,
para algum inteiro positivo r, de modo que
g r = (h′ )r ∈ hgi ∩ hhi,
em que h′ é o inverso de h em G. Contudo, pelo lema,
hgi ∩ hhi = {e}
já que estes subgrupos têm ordem p e q, respectivamente. Logo,
g r = (h′ )r = e,
EXERCÍCIOS
41
de modo que a ordens de g e h têm que dividir r, pelo lema chave da página ???. Como
os primos p e q são distintos, pq tem que dividir r. Contudo, pelo teorema de Lagrange, r
tem que dividir #G = pq; donde podemos concluir que r = pq. Isto significaria que G é
cíclico, mas estamos supondo que não é este o caso.
Resta-nos, portanto, considerar o caso em que todos os elementos de G, diferentes de
e, têm ordem igual a um dos primos, digamos p. Desta vez vamos contar os elementos de
G usando o lema. Procederemos da seguinte maneira. Começamos com S1 = hg1 i. Como
este subgrupo tem ordem p < pq, existe g2 ∈ G \ S1 . O conjunto
S2 = {r ⋆ t | r ∈ hg1 i e t ∈ hg2i} ⊆ G,
é um subgrupo de G; veja exercício 8. Digamos que dois elementos de S2 sejam iguais;
por exemplo,
r1 ⋆ t1 = r2 ⋆ t2 ,
em que r1 , r2 ∈ hg1 i e t1 , t2 ∈ hg1 i. Multiplicando esta igualdade pelo inverso de r2 ⋆ t1 ,
obtemos
(33)
r1 ⋆ r2′ = t′1 ⋆ t2 ∈ hg1 i ∩ hg2 i,
em que estamos usando a linha para denotar o inverso de um elemento. Como já sabemos
que
hg1 i ∩ hg2 i = {e},
podemos deduzir de (33) que
r1 = r2
e
t1 = t2 .
Logo,
#S2 = p2 .
Contudo, pelo teorema de Lagrange, a ordem de S2 tem que dividir a ordem de G, o que não
é possível neste caso porque p 6= q. Logo, os elementos de G não podem ter todos ordem
igual a um dos primos que dividem #G. Podemos resumir os resultados mais importantes
desta seção da seguinte forma.
T EOREMA 5.2. Um grupo (abeliano) cuja ordem é um número primo ou um produto de
dois primos distintos é necessariamente cíclico. Além disso, todos os elementos, diferentos
do neutro, de um grupo de ordem prima são geradores do grupo.
Exercícios
1. Relativamente a quais dos primos entre 3 e 19, o número 2 é um resíduo quadrático? E
o número 3?
2. Determine todos os resíduos quadráticos módulo 5, 7 e 11.
3. Seja p > 2 um primo. Prove as seguintes propriedades dos resíduos quadráticos:
42
2. GRUPOS FINITOS
(a) se a e b são resíduos quadráticos módulo p então o mesmo vale para ab;
(b) se a é um resíduos quadrático módulo p e ab ≡ 1 mod p, então b também é um
resíduo quadrático modulo p.
4. Determine a ordem dos seguintes grupos de Pell modulares: P(3, 5), P(4, 5), P(3, 7) e
P(4, 7).
5. Seja p = 2m + 1 um número primo positivo. Mostre que se b é um resíduo quadrático
módulo p então bm ≡ 1 (mod p).
6. Seja G um grupo finito provido de uma operação ⋆. Suponha que um primo p divide a
ordem de G e considere o subconjunto Hp de G formado pelo elemento neutro e pelos
elementos de ordem p contidos em G.
(a) Mostre que Hp é um subgrupo de G.
(b) Determine H3 quando G = U(28).
7. Considere o grupo U(20).
(a) Determine a ordem de U(20).
(b) Determine a ordem de cada elemento de U(20).
(c) Mostre que o grupo U(20) não é cíclico.
(d) Determine os subgrupos de ordem 4 de U(20).
(e) Determine um subgrupo de U(20) que não seja cíclico.
8. Seja G um grupo dotado de uma operação ⋆ e sejam S1 e S2 subgrupos de G. Mostre
que o conjunto
S1 S2 = {s1 ⋆ s2 |s1 ∈ S1 e s2 ∈ S2 }
é um subgrupo de G.
9. Suponhamos que G é um grupo cíclico finito de ordem n. Mostre que se m divide n
então G tem um elemento de ordem m.
10. Sabe-se que [48, 33] é um gerador de P(11, 59). Determine elementos de ordem 5, 10,
30 e 20 neste grupo.
11. Seja G um grupo e S1 e S2 dois subgrupos de G. Mostre que S1 ∪ S2 só pode ser um
subgrupo de G se S1 ⊆ S2 ou S2 ⊆ S1 .
12. Seja n um inteiro positivo, composto e ímpar. Considere o seguinte subconjunto do
grupo U(n):
H(n) = {b ∈ U(n) : n é pseudoprimo para a base b}.
Determine se cada uma das afirmações abaixo é verdadeira ou falsa, justificando cuidadosamente suas respostas.
(a) H(n) é um subgrupo de U(n).
EXERCÍCIOS
43
(b) H(n) não pode ser igual a U(n) porque n é composto.
(c) U(n) não pode ter um elemento de ordem n − 1 porque n é composto.
13. Determine:
(a) os subgrupos cíclicos de ordem 4 de U(21) e de U(42);
(b) os subgrupos cíclicos e não cíclicos de ordem 6 de U(28);
(c) um gerador do grupo U(22);
(d) todos os subgrupos não cíclicos de ordem 4 do grupo U(33).
14. Seja p > 0 um primo e c um inteiro positivo. Mostre que se 2c! ≡ 1 (mod p) e se 2 é
um gerador do grupo U(p) então todos os fatores primos de p − 1 são menores que c.
15. Seja G um grupo cíclico finito gerado por um elemento a.
(a) Mostre que se S é um subgrupo de G e se m é o menor inteiro positivo tal que
am ∈ S, então am gera S.
(b) Dê um exemplo de um grupo G que não é cíclico, mas cujos subgrupos próprios
são todos cíclicos.
16. Seja G um grupo cíclico de ordem n, g um gerador do grupo G e r um inteiro positivo.
Mostre que:
(a) se r divide m, então a ordem de g r é igual ao cofator de r em m;
(b) se r e m são primos entre si, então a ordem de g r é igual a m.
17. Seja G um grupo finito e seja n um número inteiro positivo. Considere o conjunto
Sn = {xn : x ∈ G}. Isto é, os elementos de Sn são as potências n-ésimas de elementos
de G.
(a) Mostre que Sn é um subgrupo de G.
(b) Calcule S2 no caso em que G = U(14).
18. Seja G um grupo provido de uma operação ∗, e sejam a e b elementos de G de ordem
três. Suponha que a ∈
/ hbi.
(a) Mostre que a ∗ b tem ordem 3.
(b) Qual a ordem do menor subgrupo de G que contém a e b?
19. Ache um gerador para cada um dos seguintes grupos de Pell modulares P(3, 5), P(4, 5),
P(3, 7) e P(4, 7).
CAPíTULO 3
Comparando grupos
Neste capítulo calculamos as ordens dos grupos U(n) e P(d, p), que são necessárias,
respectivamente, no RSA e no teste de primalidade para números de Mersenne. Faremos
isto comparando estes grupos com outros cujas ordens são fáceis de determinar. A comparação entre grupos, por sua vez, é feita através dos homomorfismos; aplicações entre
grupos que preservam as operações entre elementos.
1. Homomorfismos
Quando queremos comparar dois conjuntos, construímos uma aplicação de um deles
no outro. Por exemplo, ao contar construímos uma aplicação de um subconjunto dos números inteiros no conjunto cuja quantidade de elementos queremos determinar. Entretanto,
comparar dois grupos envolve potencialmente mais do que simplesmente estabelecer uma
aplicação entre dois conjuntos. Afinal de contas, grupos vêm equipados com operações, de
modo que compará-los como grupos deveria incorporar a maneira como estas operações
se relacionam uma com a outra. A experiência mostrou que a maneira correta de comparar
dois grupos é dada pelo conceito de homomorfismo, que definimos abaixo.
Sejam G e H dois grupos providos de operações que denoremos, respectivamente, por
⋆ e ◦. Uma aplicação ψ : G → H é um homomorfismo de grupos se leva o elemento neutro
de G no elemento neutro de H e satisfaz
ψ(g1 ⋆ g2 ) = ψ(g1 ) ◦ ψ(g2 ),
quaisquer que sejam os elementos g1 , g2 ∈ G. Muitas aplicações bem conhecidas são
homomorfismos de grupos. Por exemplo, a aplicação que leva cada inteiro em seu dobro
em um homomorfismo do grupo aditivo Z nele mesmo. Já a exponencial cuja base é um
número positivo, é um homomorfismo do grupo aditivo R no grupo multiplicativo dos
números reais não nulos.
É fácil construir homomorfismos entre grupos de inversíveis modulares. Considere,
por exemplo, a função
θ : U(16) → U(32),
que leva uma classe a ∈ U(16) em a2 ∈ U(32). A primeira coisa a notar é que a é uma
classe módulo 32, ao passo que a2 está sendo considerada como uma classe módulo 32.
45
46
3. COMPARANDO GRUPOS
Por isso, antes de verificar se θ satisfaz as propriedades que definem os homomorfismos,
precisamos ter certeza de que esta aplicação está bem definida; isto é, que classes iguais em
U(16) são levadas em classes iguais em U(32). Traduzindo em termos de congruências, o
que precisamos mostrar é que se a ≡ b (mod 16), então a2 ≡ b2 (mod 32). Mas, a ≡ b
(mod 16) equivale a dizer que a = b + 16k, para algum inteiro k. Como
a2 = b2 + 32(k + 8k 2 )
podemos concluir que a2 − b2 é divisível por 32, o que mostra que a2 ≡ b2 (mod 32).
Agora que sabemos que θ está bem definida, podemos verificar se é um homomorfismo de
grupos. Como 12 = 1, é claro que θ leva o elemento neutro de U(16) no elemento neutro
de U(32). Finalmente, se a, b ∈ U(16), então
θ(a · b) = (a · b)2 ,
que, por sua vez, é igual a
2
a2 · b = θ(a) · θ(b),
confirmando que θ é mesmo um homomorfismo de grupos.
Nosso segundo exemplo é mais geral e será muito usado adiante. Sejam m e n inteiros
positivos tais que m divide n e considere a aplicação
πn,m : U(n) → U(m),
que leva a ∈ U(n) na classe de U(m) que é representada por a. Como no exemplo
anterior, a primeira coisa que precisamos mostrar é que se a = α em U(n), então a e α
também representam a mesma classe em U(m). Mas a ≡ α (mod n) equivale a dizer
que a − α é múltiplo de n. Como, por sua vez, n é múltiplo de m, podemos concluir
que m divide a − α, donde a ≡ α (mod m), como precisávamos mostrar. Para que você
não fique com a impressão de que o que mostramos é óbvio, observe que se m não divide
n então a aplicação correspondente não pode ser corretamente definida. Por exemplo,
17 ≡ 7 (mod 10), portanto 7 e 17 representam a mesma classe módulo 10. Contudo, se a
aplicação π10,7 existisse, ela levaria a classe 17 = 7 de Z10 na classe 3 ou na classe 0 de Z7 ,
dependendo se a imagem foi calculada usando 17 ou 7 como representante da classe em
Z10 . Como um elemento do domínio de uma aplicação só pode ser levado em um elemento
da imagem, π10,7 não pode ser uma aplicação.
No caso em que m divide n, o homomorfismo πn,m , definido acima, pode ser usado
para construir o homomorfismo
Πn,m : U(d, n) → U(d, m),
que leva P = (x0 , y0 ) ∈ U(d, n) no par
Πn,m (P ) = (πm,n (x0 ), πm,n (y0 )).
Como πm,n está bem definido, o mesmo vale para Πm,n . A verificação de que se trata de
um homomorfismo é fácil e ficará por sua conta.
1. HOMOMORFISMOS
47
Os homomorfismos de grupos satisfazem uma outra propriedade, que é consequência
direta da definição. Voltando à situação geral, digamos que G e H sejam grupos munidos
de operações ⋆ e ◦, respectivamente, e digamos que ψ : G → H é um homomorfismo
de grupos: qual é a imagem por ψ do inverso de um elemento g ∈ G? Para determinar
isto, digamos que g ′ é o inverso de g em G. Vamos calcular ψ(g ⋆ g ′) de duas maneiras
diferentes. Por um lado, g ⋆ g ′ é igual ao elemento neutro e de G, de modo que
ψ(g ⋆ g ′) = ψ(e)
que é o elemento neutro de H; por outro,
ψ(g ⋆ g ′ ) = ψ(g) ◦ ψ(g ′ ).
Comparando estas duas equações, deduzimos que ψ(g) ◦ ψ(g ′ ) é igual ao elemento neutro
de H. Mas isto significa que ψ(g ′ ) é o inverso de ψ(g) em H. Temos, portanto, que um
homomorfismo de grupos ψ : G → H:
• leva o produto de dois elementos de G no produto de suas imagens em H;
• leva o elemento neutro de G no elemento neutro de H;
• leva o inverso de um elemento de G no inverso da imagem daquele elemento.
Como ocorre com qualquer outra aplicação, podemos definir a imagem de um homomorfismo de grupos ψ : G → H como sendo o subconjunto de H formado por aqueles
elementos que são imagem de algum elemento de G por ψ. Em outras palavras,
im(ψ) = {ψ(g) | g ∈ G}.
É fácil mostrar que im(ψ) é um subgrupo de H. Outro subgrupo, desta vez de G, que
é muito importante no estudo dos homomorfismos de grupos é o núcleo de ψ, que é o
conjunto dos elementos de G que são levados no elemento neutro de H. Note que o núcleo
não pode ser vazio porque, por definição, o elemento neutro do domínio é levado no neutro
da imagem. Por exemplo, considere o homomorfismo grupos
θ : U(16) → U(32),
definido acima por θ(a) = a2 . Os resíduos módulo 32 dos quadrados dos inteiros ímpares
entre 1 e 15 podem ser encontrados na tabela 1.
1 3 5 7 9 11 13 15
Inteiro ímpar
Quadrado módulo 32 1 9 25 17 17 25 9 1
TABELA 1. Quadrados dos inteiros de 1 a 15 módulo 32
48
3. COMPARANDO GRUPOS
Portanto,
im(θ) = {1, 9, 25, 17} ⊆ U(32),
ao passo que
N(θ) = {1, 15} ⊆ U(16).
Embora o conceito de imagem de uma aplicação provavelmente lhe seja familiar, é possível que você nunca tenha ouvido falar em núcleo. A razão para isto é que este conceito
se aplica apenas a homomorfismos de grupos ou de outros conjuntos que admitam operações, entre eles espaços vetoriais. Por isso provaremos um resultado que ilustra porque
deveríamos estar interessados no núcleo.
Proposição. Um homomorfismo de grupos é injetivo se, e somente se, seu núcleo contém
apenas o elemento neutro.
Lembre-se que uma aplicação é injetiva quando não há dois elementos diferentes de
seu domínio sendo levados no mesmo elemento da imagem. Com isto, cada elemento do
domínio corresponde a, exatamente, um elemento do grupo imagem. Em particular, se o
domínio de uma aplicação injetiva é finito, então sua imagem tem exatamente a mesma
quantidade de elementos que seu domínio.
D EMONSTRAÇÃO . Sejam ψ : G → H um homomorfismo de grupos e g1 6= g2 elementos de G. Digamos que G tem operação ⋆ e elemento neutro e e H tem operação ◦ e
elemento neutro ε. Além disso, usaremos uma linha para indicar o inverso de um elemento,
esteja ele em G ou H. Note que se e 6= g ∈ N(ψ), então
ψ(g) = ε = ψ(e),
de modo que ψ não pode ser injetiva, já que leva e e g 6= e no mesmo elemento de H. Para
provar a recíproca, suponha que N(ψ) = {e} e que
ψ(g1 ) = ψ(g2 ).
Como H é um grupo, a igualdade acima equivale a
ψ(g1 ) ◦ ψ(g2 )′ = ε;
que pode ser reescrita na forma
ψ(g1 ) ◦ ψ(g2′ ) = ε,
pois, como já vimos, ψ(g2′ ) = ψ(g2 )′ . Como ψ é um homomorfismo, obtemos
ψ(g1 ⋆ g2′ ) = ε.
Mas, pela definição de núcleo, isto significa que
g1 ⋆ g2′ ∈ N(ψ) = {e};
que equivale a dizer que g1 = g2 , como precisávmos mostrar.
2. ORDEM DE P(d, p)
49
Os homomorfismos injetivos cujo conjunto de chegada (contra-domínio) coincide com
a imagem são chamados de isomorfismos; dois grupos são isomorfos se existe um isomorfismo de um deles no outro. Naturalmente, dois grupos isomorfos têm a mesma quantidade
de elementos. Contudo, a existência de um isomorfismo entre dois grupos nos diz muito
mais sobre eles do que sua quantidade de elementos. De fato, embora os elementos de dois
grupos isomorfos possam ser de natureza muito diferente, as suas propriedades como grupos são exatamente as mesmas. Em outras palavras, não é possível distinguir dois grupos
que são isomorfos se considerarmos apenas aquelas propriedades que decorrem do fato de
serem grupos. Nas próximas seções estabeleceremos vários isomorfismos de grupos que
nos permitirão, entre outras coisas, determinar as ordens de U(n), quando n é composto, e
de P(d, p), quando p > 2 é um primo.
2. Ordem de P(d, p)
Nesta seção usaremos homomorfismos de grupos para calcular a ordem do grupo da
equação de Pell modular. Seja p > 2 um primo e seja d um inteiro positivo. Começaremos
com o caso em que d não é resíduo quadrático módulo p, que é o que será usado, no
capítulo 4, para justificar o teste de Lucas-Lehmer para primos de Mersenne. Considere a
aplicação
ν : U(d, p) → U(p),
2
que ao par (a, b) associa sua norma a2 − db ; veja página 30. Da definição de norma é claro
que
ν(1, 0) = 1.
Além disso, como vimos na equação (31) da página 31,
ν(P1 ⊗ P2 ) = ν(P1 ) · ν(P2 ),
para todo P1 , P2 ∈ U(d, p). Logo, ν é um homomorfismo de grupos.
Dado a ∈ U(p), definimos ν −1 (a) como sendo o subconjunto de U(d, p) formado pelos
pares cuja norma é a; isto é,
ν −1 (a) = {P ∈ U(d, p) | ν(P ) = a}.
Como cada elemento de U(d, p) tem exatamente uma imagem por ν, podemos escrever
(34)
U(d, p) = ν −1 (1) ∪ ν −1 (2) ∪ · · · ∪ ν −1 (n − 1),
em que
(35)
ν −1 (a) ∩ ν −1 (b) = ∅
se a 6= b. Por outro lado, como ν é um homomorfismo, temos que se Q ∈ ν −1 (a) e
Q′ é seu inverso em U(d, p), então ν(Q′ ) é igual ao inverso de a em U(p). Portanto, se
Q1 , Q0 ∈ ν −1 (a) e Q′0 é o inverso de Q0 em U(d, p), então
ν(Q1 ⊗ Q′0 ) = ν(Q1 )ν(Q′0 ) = 1.
50
3. COMPARANDO GRUPOS
Em outras palavras, Q1 ⊗ Q′0 = P ∈ P(d, p), de modo que
Q1 = P ⊗ Q0 ;
isto é, dado Q0 ∈ ν
−1
(a), podemos dizer que
ν −1 (a) ⊆ {P ⊗ Q0 | P ∈ P(d, p)}.
Por outro lado,
ν(P ⊗ Q0 ) = ν(P )ν(Q′0 ) = ν(Q′0 ),
já que P ∈ P(d, p). Logo, temos a igualdade
ν −1 (a) = {P ⊗ Q0 | P ∈ P(d, p)}.
Contudo, como estamos em um grupo,
P1 ⊗ Q0 = P2 ⊗ Q0
só pode ocorrer se P1 = P2 , o que nos permite concluir que
#ν −1 (a) = #P(d, p).
Combinando isto com (34) e (35), obtemos
#U(d, p) = #ν −1 (1) + #ν −1 (2) + · · · + #ν −1 (p − 1) = (p − 1)#P(d, p).
Entretanto, como vimos na proposição da página 32,
#U(d, p) = (p − 1)(p + 1);
donde
(p − 1)(p + 1) = (p − 1)#P(d, p).
Cancelando p − 1 nesta igualdade concluímos que
#P(d, p) = p + 1,
no caso em que d não é resíduo quadrático módulo p.
Passando, agora, ao caso em que d é resíduo quadrático módulo p, digamos que
d ≡ q2
(mod p).
Neste caso, o lado esquerdo da equação de Pell x2 − dy 2 = 1 pode ser fatorado, de forma
que, se (x0 , y0 ) ∈ P(d, p), então
(36)
1 = x0 2 − dy0 2 = (x0 + qy0 )(x0 − qy0 ),
Mas, para que isto seja verdade, é preciso que os fatores x0 − qy0 e x0 + qy0 sejam um o
inverso do outro em Zp . Isto nos permite definir uma aplicação
η : P(d, p) → U(p)
pela regra
(37)
η(x0 , y0 ) = x0 + qy0 .
2. ORDEM DE P(d, p)
51
Como η leva (1, 0) em 1, precisamos apenas verificar que
(38)
η(P1 ⊗ P2 ) = η(P1 )η(P2 ),
quaisquer que sejam P1 , P2 ∈ P(d, p), e teremos provado que η é um homomorfismo de
grupos. Digamos que
P1 = (x1 , y1) e P2 = (x2 , y2 ).
Aplicando a regra que define η ao produto P1 ⊗ P2 , obtemos
(39)
η(P1 ⊗ P2 ) = (x1 x2 + dy1 y2 ) + q(x1 y2 + y1 x2 ).
Por outro lado,
η(P1 )η(P2 ) = (x1 + qy1 )(x2 + qy2 ).
Efetuando o produto e levando em conta que d = q 2 , descobrimos que o lado direito desta
última equação é igual ao lado direito de (39), provando que a igualdade (38) é mesmo
verdadeira. Portanto, η é um homomorfismo de grupos.
Como queremos mostrar que η é um isomorfismo, vamos tentar identificar sua imagem.
Para isto, precisamos identificar quais são os elementos α ∈ U(p) que podem ser escritos
na forma
α = x0 + qy0 ,
para algum par (x0 , y0 ) ∈ P(d, p). Mas, usando (36), obtemos
α(x0 − qy0 ) = 1,
que só pode ocorrer se x0 − qy0 for igual ao inverso α′ de α em U(p). Disto, obtemos o
sistema linear
(40)
x0 + qy0 = α
x0 − qy0 = α′ .
Como p é ímpar por hipótese, podemos escrevê-lo na forma p = 2m−1, para algum inteiro
positivo m. Mas isto signfica que
2m ≡ 1
(mod p);
isto é, m é o inverso de 2 módulo p. Levando isto em conta, as soluções do sistema linear
(40) são
x0 = (α + α′ )m e y0 = (α − α′ )m.
Mostramos, assim, que
η((α + α′ )m, (α − α′ )m) = α,
qualquer que seja α ∈ U(p). Além disso, esta é a única escolha possível de ponto em
P(d, p) que satisfaz esta propriedade, porque o sistema linear (40) não tem nenhuma solução além desta. Portanto, provamos que cada elemento de U(p) é imagem de exatamente
um elemento de P(d, n); de modo que η é um isomorfismo de grupos. Em particular,
52
3. COMPARANDO GRUPOS
P(d, p) e U(p) têm a mesma quantidade de elementos. O que aprendemos sobre as ordens dos grupos de Pell modulares pode ser resumido na seguinte fórmula: se p > 2 é um
número primo e d > 1 é um número inteiro, então
(
p−1
se d é resíduo quadrático módulo p;
(41)
#P(d, p) =
p+1
se d não é resíduo quadrático módulo p.
Contudo, os isomorfismos que provamos nesta seção nos dizem muito mais sobre estes
grupos do que apenas suas ordens. Por exemplo, veremos no capítulo 4 que os grupos U(p)
são cíclicos. Como U(p) é isomorfo a P(d, p) quando d é resíduo quadrático, podemos
deduzir que este último grupo também é cíclico. Na verdade, podemos fazer uma afirmação
ainda mais precisa: se a é um gerador de U(p), então η −1 (a) é um gerador de P(d, p); veja
exercícios 6 e 7.
3. Produtos cartesianos e tabelas
Do ponto de vista matemático, uma tabela corresponde ao produto cartesiano L×C, de
dois conjuntos finitos L e C. Neste caso, cada linha da tabela é indexada por um símbolo
de L e cada coluna por um símbolo de C. Em nossas aplicações trabalharemos com as
tabelas associadas ao produto cartesiano Zm × Zn . Por exemplo, as casas da tabela 2 são
indexadas pelos pares em Z5 × Z6 .
0 1 2 3 4 5
0
1
2
3
4
TABELA 2. Tabela indexada pelos pares em Z5 × Z6 .
Para formular de maneira matemática o que significa preencher a tabela cujas casas são
indexadas por L × C, usamos uma aplicação p : L × C → V , em que V é o conjunto ao
qual pertencem os valores que serão atribuídos às diversas casas. Usando esta terminolgia,
temos que a casa que está na linha indexada por ℓ e na coluna indexada por c recebe o valor
p(ℓ, c). Voltando ao caso que mais nos interessa, queremos preencher a tabela Zm × Zn
com elementos de Zmn . Para isso, usaremos a aplicação
σm,n : Zm × Zn → Zmn
3. PRODUTOS CARTESIANOS E TABELAS
53
que a cada par (a, b) associa a classe c ∈ Zmn para a qual
c≡a
(mod m)
c ≡ b (mod n).
Voltando à tabela do nosso exemplo, verificamos que as casas cuja linha e coluna são
indexadas pelo mesmo número inteiro podem ser preenchidas com este número. Para
as demais, precisamos resolver o sistema de congruências correspondente. Por exemplo,
a casa da tabela 2 cuja linha é indexada por 2 e cuja coluna é indexada por 5 deve ser
preenchida com o número c entre 0 e 29 que satisfaz as congruências
c≡2
(mod 5)
c≡5
(mod 6).
Resolvendo este sistema pelo algoritmo chinês do resto, descobrimos que c = 17. Como
5 e 6 são primos entre si, o teorema chinês do resto nos garante que é possível preencher
toda a tabela, casa a casa, de modo que a cada casa corresponda exatamente uma classe de
Z30 . Procedendo desta maneira, obtemos a tabela 5.
Entretanto, há uma outra maneira de preencher a tabela, muito mais simples, que faz
uso da descrição geométrica do conjunto Zn que estudamos no capítulo ???. Nosso ponto
de partida é, mais uma vez, o fato de que é fácil preencher as casas que estão no que
chamaremos de diagonal da tabela; isto é, aquelas casas cuja linha e coluna são indexadas
pelo mesmo inteiro. O problema é que, com isto, só conseguimes preencher três casas
da tabela, aquelas cujas entradas são 0, 1, 2, 3. Não podemos continuar preenchendo a
diagonal porque aparentemente a tabela acabou. Contudo, os limites desta tabela são da
mesma natureza daqueles de um mapa mundi. Isto é, são forçados pelo fato de que estamos
fazendo uma representação plana da superfície de um sólido tridimensional. Afinal, pelo
que vimos na seção ??? do capítulo ??? os lados de baixo e de cima da tabela deveriam
estar colados, já que Z5 é representado geometricamente marcando suas classes como 5
pontos igualmente espaçados ao longo de uma circunferência. Assim podemos continuar
‘preenchendo a tabela ao longo da diagonal’; isto é, movendo-nos, simultaneamente, uma
casa para à direita e uma para baixo ao longo de toda a tabela. Só que o 5, que deveria vir
uma coluna à direita e uma linha abaixo do 4, pula para a casa da coluna à direita, só que
na primeira linha da tabela; ver tabela 3.
De modo semelhante, a tabela não acaba na coluna mais à direita: colando o lado
direito ao esquerdo, verificamos que 6 deve ser posicionado na primeira coluna, uma linha
abaixo de onde está o 5. Se continuamos a nos mover uma casa para à direita e uma para
baixo ao longo da tabela, podemos posicionar, sem dificuldade, as classes 7, 8 e 9; ver
tabela 4.
54
3. COMPARANDO GRUPOS
0 1 2 3 4 5
0 0
5
1
1
2
2
3
3
4
4
TABELA 3. Posição da classe 5 ∈ Z30 na tabela Z5 × Z6 .
0 1 2 3 4 5
0 0
5
1 6 1
2
7 2
3
8 3
4
9 4
TABELA 4. Posição das 9 primeiras classes de Z30 na tabela Z5 × Z6 .
Como o 9 ocupa uma casa na fronteira inferior da tabela, a classe 10 deve ser posta na
primeira linha da tabela, uma coluna à direita do 9. O 11 vai parar uma casa à direita e
uma abaixo do 10, mas para posicionar o 12 devemos mais uma vez pular da coluna mais
à direita para a mais à esquerda da tabela, na casa logo abaixo do 6. As classes 13 e 14 são
preenchidas sem dificuldade, mas 15 vai parar na primeira linha, uma posição à direita do
14. Ao chegar a 17 precisamos dar mais um pulo da direita para a esquerda e ao chegar a
18 um de baixo para cima. Continuando desta maneira, obtemos a tabela 5.
0
1
2
3
4
0 1 2 3 4 5
0 25 20 15 10 5
6 1 26 21 16 11
12 7 2 27 22 17
18 13 8 3 28 23
24 19 14 9 4 29
TABELA 5. Tabela indexada pelos pares em Z5 × Z6 .
4. TABELAS E GRUPOS
55
Como observamos acima, o retângulo Zm × Zn é a representação bidimensional da
superfície de um sólido, da mesma maneira que um mapa mundi. No caso do mapa mundi,
trata-se da superfície de uma esfera. E no caso do Zm × Zn , qual é o sólido cuja superfície
ele representa? Tomando um retângulo de papel e colando dois de seus lados paralelos,
obtemos um tubo. Para obter a superfície do sólido, precisamos colar as circunferências
nas extremidades deste tubo. O resultado é a superfície de um toro, como o que ilustramos
na figura ???.
Em geral, quando o máximo divisor comum dos módulos é diferente de 1, nem todos
os sistemas que podemos escrever têm solução. Se pensarmos em termos da representação
gráfica, isto significa que nem todas as casas da tabela serão preenchidas. Mais uma vez
não é necessário resolver nenhum sistema para preencher a tabela. Basta ir preenchendo a
diagonal, e lembrando que a tabela habita a superfície de um toro. Fazendo isto, quando
os módulos m e n não são primos entre si, voltamos à casa de coordenadas (0, 0) antes de
esgotar os números de 0 a mn − 1. É por isso que há casas que não são preenchidas. A
tabela 6 corresponde ao caso em que m = 4 e n = 6.
0 1 2 3
0 0
6
1
1
7
2 8
2
3
9
3
4 4
10
5
5
11
TABELA 6. Tabela Z6 × Z4 com todas as casas possíveis preenchidas.
4. Tabelas e grupos
As tabelas que introduzimos na seção anterior têm suas linhas indexadas por classes de
Zm , suas colunas indexadas por classes de Zn e cada casa é preenchida por um elemento
de Zmn , quaisquer que sejam os inteiros m e n primos entre si. Além disso, vimos que a
tradução matemática destas tabelas são as aplicações
σm,n : Zm × Zn → Zmn
56
3. COMPARANDO GRUPOS
que a cada par (a, b) do domínio associam a classe c ∈ Zmn para a qual
c≡a
(mod m)
c ≡ b (mod n).
Mas Zm , Zn e Zmn são, todos três, grupos aditivos, de modo que podemos nos perguntar
se isto se reflete em alguma propriedade de σm,n . A resposta é sim. De fato, σm,n é
um homomorfismo de grupos mas, para mostrar isto, precisamos primeiro introduzir uma
estrutura de grupo no produto cartesiano Zm × Zn . Como esta estrutura em nada depende
dos grupos em questão serem inteiros módulo n, trataremos este problema de maneira
inteiramente geral.
Sejam, pois, G e H dois grupos. Como já se tornou rotina, suporemos que as operações
em G e H são ⋆ e ◦ e que seus elementos neutros são e e ε, respectivamente. Definimos
uma operação ⊛ no produto cartesiano G × H pela regra
(g1 , h1 ) ⊛ (g2 , h2 ) = (g1 g2 , h1 h2 ),
em que g1 , g2 ∈ G e h1 , h2 ∈ H. É fácil verificar que G × H é um grupo relativamente
à operação ⊛ e tem como elemento neutro o par (e, ε); os detalhes ficarão por sua conta.
Diremos que o grupo G × H resultante desta construção é o produto direto dos grupos G e
H. Em particular, podemos usar o produto direto para definir a soma de pares em Zm × Zn
obtendo regra
(a1 , b1 ) + (a2 , b2 ) = (a1 + a2 , b1 + b2 ),
em que a1 , a2 ∈ Zm e b1 , b2 ∈ Zn .
Com isto os conjuntos de partida e chegada da aplicação σm,n são grupos e a pergunta
σm,n é homomorfismo de grupos? faz perfeito sentido neste contexo. Para começar, o procedimento de preencher a tabela ao longo da diagonal, utilizado na seção anterior, garante
que
σm,n (0, 0) = 0 ∈ Zmn .
Portanto, para provar que σm,n é um homomorfismo de grupos, basta mostrar que
σm,n (p1 + p2 ) = σm,n (p1 ) + σm,n (p2 ),
quaisquer que sejam os pares p1 , p2 ∈ Zm × Zn . Suponhamos que
p1 = (a1 , b1 ) e que
p2 = (a2 , b2 );
neste caso, teremos que
σm,n (p1 ) = c1
e
σm,n (p2 ) = c2
com c1 , c2 ∈ Z definidos por
(42)
c1 ≡ a1
(mod m)
c2 ≡ a2
(mod m)
c1 ≡ b1
(mod n)
c2 ≡ b2
(mod n).
5. A ORDEM DE U (n)
57
Somando, respectivamente, as congruências módulo m e as congruências módulo n, obtemos
c1 + c2 ≡ a1 + a2
(mod m)
c1 + c2 ≡ b1 + b2
(mod n).
Portanto, pela definição da aplicação σm,n ,
σm,n (a1 + a2 , b1 + b2 ) = c1 + c2 .
Como
c1 + c2 = c1 + c2
podemos concluir que
σm,n (a1 + a2 , b1 + b2 ) = σm,n (a1 , b1 ) + σm,n (a2 , b2 ),
que é o que queríamos provar.
5. A ordem de U(n)
Embora o conjunto dos inteiros modulares não seja um grupo relativamente à multiplicação, o argumento usado na seção anterior pode ser aplicado à multiplicação, em vez da
adição. Mais precisamente, se m e n são inteiros primos entre si, então
(43)
σm,n (p1 · p2 ) = σm,n (p1 ) · σm,n (p2 ),
quaisquer que sejam p1 , p2 ∈ Zm × Zn , em que o produto dos pares
p1 = (a1 , b1 )
e
p2 = (a2 , b2 );
deve ser definido por
p1 · p2 = (a1 · a2 , b1 · b2 ).
Para provar (43), basta notar que se σm,n (p1 ) = c1 e σm,n (p2 ) = c2 então, multiplicando as
congruências módulo m e as congruências módulo n em (42), obtemos
c1 · c2 ≡ a1 · a2
(mod m)
c1 · c2 ≡ b1 · b2
(mod n).
Portanto, pela definição da aplicação σm,n ,
σm,n (a1 · a2 , b1 · b2 ) = c1 · c2 ;
donde
(44)
σm,n (a1 · a2 , b1 · b2 ) = σm,n (a1 , b1 ) · σm,n (a2 , b2 ),
que é equivalente a (43). Mas há ainda mais, porque (44) e a equação
σm,n (1, 1) = 1 ∈ Zmn ,
58
3. COMPARANDO GRUPOS
nos permitem concluir que p1 , p2 ∈ Zm × Zn satisfazem
p1 · p2 = (1, 1)
se, e somente se,
σm,n (p1 ) · σm,n (p2 ) = 1.
Portanto, a imagem de um par p ∈ Zm × Zn só é inversível em Zmn se as coordenadas de
p forem inversíveis em Zm e Zn , respectivamente. Traduzindo a afirmação acima em uma
linguagem mais adequada aos nossos propósitos podemos dizer que
p ∈ U(m) × U(n)
se, e somente,
σm,n (p) ∈ U(mn).
Em outras palavras, mostramos que, restringindo σm,n aos pares cujas coordenadas são
inversíveis, obtemos um homomorfismo
⋆
σm,n
: U(m) × U(n) → U(mn),
em que U(m) × U(n) é o produto direto dos grupos multiplicativos U(m) e U(n). Além
disso, como a cada par de elementos em U(m) × U(n) corresponde exatamente um ele⋆
⋆
mento em U(mn), o homomorfismo σm,n
tem que ser bijetivo. Temos, assim, que σm,n
é
um isomorfismo de grupos multiplicativos. Vamos sistematizar tudo isto em uma proposição, para uso futuro.
Proposição. Se m e n são inteiros primos entre si, então existe um isomorfismo entre os
grupos multiplicativos U(m) × U(n) e U(mn). Em particular, estes dois grupos têm a
mesma quantidade de elementos.
⋆
É fácil construir σm,n
quando a tabela correspondente à aplicação σm,n é conhecida;
para isto basta eliminar da tabela que descreve σm,n as casas em que ao menos uma das
coordenadas não é inversível. Fazendo isto para
σ5,6 : U(5) × U(6) → U(30),
devemos remover da tabela 5 a linha indexada por 0 e as colunas indexadas por 0, 2, 3 e 4.
⋆
Assim, σ5,6
corresponde à tabela 7.
1
2
3
4
1
1
7
13
19
5
11
17
23
29
TABELA 7. Tabela correspondente ao homomorfismo π⋆ : U(5) × U(6) → U(30).
5. A ORDEM DE U (n)
59
É a segunda parte do enunciado da proposição o que mais nos interessa no momento
porque, como veremos, ela nos permite calcular a ordem do grupo dos inversíveis módulo
um dado inteiro. Antes, porém, convém introduzir a seguinte notação. Dado um inteiro
n ≥ 2, definimos
φ(n) = #U(n).
Esta função, originalmente introduzida por Euler em 1763, também é conhecida como
função totiente. A notação que usamos foi introduzida por Gauss nas Disquisitiones arithmeticae. Reformulando o resultado da proposição ?? e a equação (20) da página 27 em
termos da função totiente, podemos afirmar que
(1) φ(pk ) = pk−1 (p − 1), quando p > 2 é primo e k > 0 é um inteiro;
(2) φ(mn) = φ(m)φ(n), quando m e n são inteiros primos entre si.
Com isso temos todos os ingredientes necessários para obter uma fórmula geral para φ(n).
Dado n um inteiro positivo, começamos por fatorar n,
n = pe11 . . . pekk
em que p1 < · · · < pk são primos distintos e os expoentes são todos positivos. Por (2),
φ(n) = φ(pe11 ) . . . φ(pekk ).
Usando, então, (1), obtemos
φ(n) = p1e1 −1 . . . pekk −1 (p1 − 1) . . . (pk − 1),
que é a fórmula desejada. Por exemplo, se n = 120 = 8 · 3 · 5, então,
φ(120) = 22 (2 − 1)(3 − 1)(5 − 1) = 32.
A utilidade desta fórmula geral é muito limitada. Para aplicá-la é necessário fatorar n; um
problema notoriamente difícil, como já tivemos oportunidade de observar. Contudo isto é
explorado de maneira positiva no RSA pois, como veremos na seção ???? do capítulo ???,
é precisamente o fato de que ninguém sabe como calcular os valores da função totiente
sem fatorar o argumento, que torna o RSA seguro.
Como aplicação da função totiente, temos a seguinte generalização do teorema de Fermat, provada por Euler em 1763, no mesmo artigo em que introduz a função φ. Como este
teorema é consequência imediata do teorema de Lagrange, deixaremos a demonstração por
sua conta.
T EOREMA
DE
E ULER . Se n > 1 e a são números inteiros primos entre si, então
aφ(n) ≡ 1 (mod n).
60
3. COMPARANDO GRUPOS
Exercícios
1. Sejam G e H grupos e ψ : G → H uma aplicação. Mostre que se ψ é sobrejetiva e se
ψ(g1 g2 ) = ψ(g1 )ψ(g2 ),
então ψ leva o elemento neutro de G no elemento neutro de H.
2. Sejam G e H grupos e ψ : G → H um homomorfismo de grupos. Mostre que o núcleo
e a imagem de ψ são subgrupos de G e H, respectivamente.
3. Sejam G e H grupos e ψ : G → H um isomorfismo de grupos. Mostre que a aplicação
inversa de ψ também é um isomorfismo de grupos.
4. Sejam G e H grupos e ψ : G → H um homomorfismo de grupos. Mostre que, se ψ
for injetivo, então, para todo g ∈ G, a ordem de g coincide com a ordem de ψ(g).
5. O objetivo deste exercício é mostrar que o resultado do exercício anterior é falso
quando ψ é um homomorfismo que não é injetivo.
(a) Calcule ordem de 2 em U(9).
(b) Calcule ordem de 2 em U(3).
(c) Mostre que a ordem de 2 em U(9) é maior que a ordem de π9,3 (2).
π9,3 é a aplicação definida na paágina 46.
6. Sejam G e H grupos e ψ : G → H um isomorfismo de grupos. Mostre que G é cíclico
se, e somente se, H é cíclico.
S UGESTÃO : mostre que um gerador de G é levado por ψ em um gerador de H e viceversa.
7. Usando o exercício 6 e o isomorfismo η definido na seção 2, ache geradores para os
grupos P(5, 11) e P(3, 13).
8. Calcule φ(125), φ(16200) e φ(10!).
9. Seja n um inteiro positivo e p um fator primo de n.
(a) Mostre que p − 1 divide φ(n).
(b) Mostre que pode acontecer que p não divida φ(n).
(c) Mostre que p < φ(n).
10. Determine os valores de n para os quais φ(n) = 18. Faça o mesmo para φ(n) = 10 e
φ(n) = 14.
11. Mostre que se φ(n) é um número primo então n = 3, 4 ou 6.
EXERCÍCIOS
61
12. Seja k um inteiro positivo. Os exercícios anteriores ilustram bem as dificuldades de
resolver a equação φ(n) = k. Curiosamente, há um algoritmo relativamente simples
para resolver nφ(n) = k. Seja k = nφ(n) e suponhamos que p é o maior primo que
divide k. Mostre que:
(a) O maior primo que divide n é menor ou igual a p.
(b) O expoente de p na fatoração de nφ(n) tem que ser ímpar.
Concluímos de (b) que se p tem expoente par na fatoração de k, então a equação k =
nφ(n) não tem solução. Suponhamos, então, que p tem expoente ímpar na fatoração
de k. Se um tal n existe, podemos escrevê-lo na forma n = pe · c, onde mdc(c, p) = 1,
temos que
k = nφ(n) = p2e−1 (p − 1)cφ(c).
Podemos usar isto para calcular e, uma vez que conhecemos o expoente de p na fatoração de k. Uma vez encontrado e, podemos escrever
k
= cφ(c),
2e−1
p
(p − 1)
e usar o mesmo método para achar o maior primo que divide c. Por que é que este
algoritmo pára?
13. Mostre que, se n é um inteiro positivo que satisfaz φ(n) = n − 1, então n é primo.
14. Escrevendo n = 2k r, onde r é um número ímpar, mostre que se φ(n) = n/2 então n é
uma potência de 2.
15. Mostre que se m divide n então φ(mn) = mφ(n).
16. Seja p > 0 um número primo e r um inteiro positivo. Use o teorema de Euler, aplicado
a pr para mostrar que pr é um pseudoprimo para a base b se, e somente se, bp−1 ≡ 1
(mod pr ).
17. Use o exercício anterior para mostrar que 10932 é um pseudoprimo para a base 2.
18. Escreva um programa, baseado no exercício 16, para determinar os pseudoprimos para
a base 2 da forma p2 , onde p é um primo menor ou igual a r > 0.
CAPíTULO 4
Testes de primalidade
Neste capítulo vamos explorar alguns testes de primalidade, todos eles baseados no
trabalho de Édouard Lucas, que já encontramos no capítulo ??? como inventor do jogo
das torres de Hanoi. Começaremos com um resultado da teoria de grupos que, aplicado
ao grupo dos inversíveis módulo um primo e à equação de Pell modular produzem, respectivamente, o teste de Lucas para primos em geral e o teste de Lucas-Lehmer para primos
de Mersenne. Nas seções seguintes analisamos uma variante do teste de Lucas introduzida
por Brilhart, Lehmer e Selfridge em 1975 e a recíproca do teste de Lucas-Lehmer. Encerrarmos o capítulo provando um resultado, devido a Gauss, que explica porque o teste de
Lucas sempre funciona, ao menos se tivermos à nossa disposição um tempo infinitamente
grande.
1. Os testes de Lucas e Lucas-Lehmer
Iniciaremos a seção discutindo um resultado da teoria de grupos que será usado para
provar os testes de Lucas e de Lucas-Lehmer. Suponhamos que G é um grupo e seja e seu
elemento neutro. Digamos que queremos determinar se g ∈ G tem ou não ordem igual
a m. Observe que estamos supondo que temos um candidato à ordem de g, queremos
apenas confirmar se este candidato é mesmo a ordem desejada. Em particular, o critério
que exploraremos a seguir não provê um algoritmo capaz de determinar a ordem de um
elemento em um grupo. Voltaremos a esta última questão no capítulo ??.
A primeira coisa a fazer é verificar se g m = e. Se isto não ocorrer, então não há a
menor chance de m ser a ordem de g. Por outro lado, mesmo que g m = e, não podemos
afirmar que g tem ordem m; a única coisa que o lema chave nos permite deduzir disto é
que a ordem de g divide m. Portanto, se k for a ordem de g e g m = e, temos que
m = kc,
em que o cofator c é um inteiro positivo. Mas k só pode ser menor que m se seu cofator
c for maior que 1. Contudo, segundo o teorema da fatoração única, todo inteiro maior ou
igual a 2 admite um fator primo. Digamos, então, que c > 1 e que p ≥ 2 é um fator primo
de c. Como p divide c, podemos escrever
c = pd
63
64
4. TESTES DE PRIMALIDADE
para algum inteiro d > 0, de modo que
m
= kd.
p
Neste caso,
g m/p = g kd = (g k )d = e.
Logo, se g tem ordem menor que m, então g m/p = e para algum fator primo p > 0 de
m. Formulando tudo o que aprendemos acima de maneira mais sistemática, obtemos o
seguinte critério.
Critério (ordem de um elemento). Um elemento g de um grupo G tem ordem m se
g m = e mas
am/p 6= e
para todos os fatores primos p de m.
O teste de Lucas é uma aplicação imediata deste critério ao caso em que G é o grupo
dos inteiros módulares inversíveis.
Teste de Lucas. Sejam b e n números inteiros maiores que 1. Se
(1) bn−1 ≡ 1 (mod n);
(2) b(n−1)/p 6≡ 1 (mod n),
para todo fator p de n − 1, então n é um número primo.
D EMONSTRAÇÃO . Segue da condição (1) que o inteiro b admite ordem módulo n.
Logo, pela proposição ????, do capítulo sobre aritmética modular, a classe de b em Zn tem
que ser invertível. Assim, b ∈ U(n). Contudo, pelo critério acima, as condições (1) e (2)
implicam que b tem ordem igual a n − 1. Mas isto significa que b tem n − 1 potências
distintas, todas elas contidas em U(n). Portanto,
n − 1 ≤ #U(n).
Combinando a desigualdade acima com o fato de que #U(n) ≤ n − 1, podemos concluir
que #U(n) = n − 1. Acontece que isto significa que todas as classes não nulas de inteiros
módulo n têm que ter representantes primos com n. Como isto só pode acontecer se n não
tiver fatores próprios, podemos concluir que n é primo, confirmando que o teste realmente
funciona.
1. OS TESTES DE LUCAS E LUCAS-LEHMER
65
Os testes anteriores detectavam com certeza apenas números compostos. Este teste
determina com certeza se um dado número é primo. Mas observe que, para aplicá-lo com
sucesso, precisamos ser capazes de fatorar n − 1. De fato, a segunda equação do teste tem
que ser verificada para cada fator primo de n−1. Na prática há muitos primos interessantes
para os quais esta condição é facilmente verificada. Um exemplo são os fatores primos dos
números de Fermat. Além disso, não há um método eficiente para escolher a base b; mas
isto não é muito surpreendente, afinal o teste forte de composição padecia do mesmo mal.
Vejamos o que acontece quando aplicamos o teste de Lucas ao número
R(19) = |1111111111111111111
{z
}.
19
Para começar, precisamos primeiro achar a fatoração completa de R(19) −1. Fazendo isto,
obtemos
R(19) − 1 = 2 · 32 · 5 · 7 · 11 · 13 · 19 · 37 · 52579 · 333667.
Nossa primeira escolha de base será b = 2. Usando um sistema de computação algébrica,
é fácil verificar que
2R(19)−1 ≡ 1
(mod R(19)).
Mas, infelizmente,
2(R(19)−1)/2 ≡ 1
(mod R(19)).
Assim a condição (2) do teste de Lucas falha para b = 2 e p = 2. Portanto, 2 não é uma
boa escolha de base.
Em seguida escolhemos b = 3. Usando novamente um sistema de computação algébrica, descobrimos que
3R(19)−1 ≡ 1
(mod R(19));
de modo que a condição (1) do teste de Lucas vale. Precisamos agora calcular as formas
reduzidas de
3(R(19)−1)/p
módulo R(19) para cada um dos primos p que aparecem na fatoração de R(19) − 1. Este
é o conteúdo da seguinte tabela.
66
4. TESTES DE PRIMALIDADE
Fator primo p Resto de 3(R(19)−1)/p por R(19)
2
R(19) − 1
3
933000903779960656
5
97919522321038174
7
742392324159673027
11
920873402557886628
13
114592042672083983
19
1011
37
397724716798816350
52579
760105763664485871
333667
555602369615218524
Assim a condição (2) do teste de Lucas vale para cada um dos fatores primos de R(19) − 1.
Portanto, R(19) é, de fato, um número primo.
Só se conhecem 5 primos da forma R(n). O primeiro é R(2) = 11, e o segundo é
R(19). Os outro são R(23), R(317) e R(1031). Não é difícil provar que R(23) é primo
usando uma versão melhorada do teste de Lucas que vamos descrever na próxima seção.
O teste de Lucas também é excelente para números de Fermat, já que F (k) − 1 tem
apenas 2 como fator primo. Para estes números temos o seguinte resultado devido a Jean
François Théophile Pepin (1826-1904).
Teste de Pepin O número de Fermat F (k) é primo, para k > 1 se, e somente se,
5(F (k)−1)/2 ≡ −1
(mod F (k)).
Segue diretamente do teste de Lucas que, se a equação acima vale, então F (k) é primo.
A recíproca vai ficar para a seção 3, onde provaremos o critério de Euler, que é usado
para determinar se um dado número é ou não resíduo quadráticoé módulo um primo. A
grande vantagem do teste de Pépin é os cálculos necessários para aplicá são fáceis de
executar porque envolvem apenas calcular o quadrado de números módulo F (k), e isto se
faz rapidamente. Por exemplo, como
21 5
F (15) − 1
=
= 214 ,
2
2
então, para aplicar o Teste de Pepin a F (15), precisamos calcular o resto da divisão de
15
52 por F (15). Utilizando o A XIOM para fazer as contas, verificamos que o resto é um
1. OS TESTES DE LUCAS E LUCAS-LEHMER
67
número com 9863 algarismos (decimais), ao passo que F (15) − 1 tem um algarismo a
mais. Portanto,
15
52 ≡ 70883540033298 · · · 1883849529 6≡ −1
(mod F (15));
o que nos permite concluir que F (15) é composto.
Finalizamos a seção aplicando o critério para provar o teste de Lucas-Lehmer, que nos
pemite determinar se um número de Mersenne, cujo expoente é primo, é ou não um número
primo. Lembre-se que um número de Mersenne cujo expoente é composto é necessariamente, ele próprio, um número composto; veja a seção ??? do capítulo ???. A versão do
teste que discutimos nesta seção é a mais simples possível diante do que já sabemos sobre
o grupo P(d, p). Uma versão mais apropriada para a implementação pode ser encontrada
seção 3.
Teste de Lucas-Lehmer. Seja p > 2 um primo. Se Q = (2, 1) ∈ U(3, 2p − 1) satisfaz
p−1
Q2
= (−1, 0)
em U(3, 2p − 1), então 2p − 1 é um número primo.
D EMONSTRAÇÃO . Seja q um fator primo de 2p − 1 e considere a aplicação
Π2p −1,q : U(3, 2p − 1) → U(3, q)
que leva um ponto P de U(3, 2p −1) no ponto de U(3, q), cujas coordenadas têm os mesmos
representantes que as coordenadas de P . Como vimos na seção 1 do capítulo 3, Π =
Π2p −1,q é um homomorfismo de grupos. Portanto, se Q0 = Π(Q), então
p−1
Q20
p−1
= Π(Q2
) = Π(−1, 0) = (−1, 0)
em U(3, q). Contudo,
p−1
Q20
= (−1, 0)
implica que
p
Q20 = (1, 0)
em U(3, q). Logo, pelo critério da seção 1, podemos afirmar que Q0 tem ordem 2p em
U(3, q). Mas,
Q0 = (2, 1)
é solução de x2 − 3y 2 = 1 módulo q. Logo, Q0 é um elemento de ordem 2p em P(3, q).
Portanto, pelo teorema de Lagrange, 2p tem que dividir a ordem de P(3, q). Pela fórmula
(41) da página 52, há dois casos a considerar, dependendo se 3 for ou não resíduo quadrático módulo q. No caso em que 3 é resíduo quadrático, teremos que 2p divide q − 1; o que
não é possível pois q é, por hipótese, fator primo de M(p) = 2p − 1 < 2p . Portanto, 3 tem
que ser resíduo quadrático módulo q. Neste caso, 2p deve dividir
#P(3, q) = q + 1.
68
4. TESTES DE PRIMALIDADE
Como q é fator primo de 2p − 1, isto só é possível se q = 2p − 1; em particular, 2p − 1 tem
que ser primo, como queríamos mostrar.
A despeito de não ser a implementação mais eficiente do teste de Lucas-Lehmer, a
versão acima é bastante poderosa. Por exemplo, Harry Lewis Nelson e David Slowinski
precisaram, em 1979, de um supercomputador Cray 1 para achar o primo de Mersenne
M(44497), que tem 13395 algarismos. Hoje em dia um notebook com um processador de
1.60GHz e 3.8GiB de RAM leva cerca de cerca de 2 minutos e 30 segundos para confirmar
que M(44497) é mesmo primo, usando o algoritmo acima implementado, no A XIOM.
2. O teste de Brilhart, Lehmer e Selfridge
Façamos um exemplo, bem simples, para ilustrar uma das dificuldades na aplicação
do teste de Lucas. Digamos que queremos usá-lo para verificar que n = 41 é primo.
Começamos fatorando n − 1 = 40, obtendo n − 1 = 23 · 5. Portanto precisamos achar um
inteiro b tal que 2 ≤ b ≤ 40 e que também satisfaça a cada uma das equações abaixo:
b40 ≡ 1 (mod 41)
b20 6≡ 1 (mod 41)
b8 6≡ 1 (mod 41).
Começamos com b = 2, mas logo verificamos que 220 ≡ 1 (mod 41). Passamos a b = 3,
mas embora 320 ≡ 40 (mod 41), temos 38 ≡ 1 (mod 41). Para tornar as coisas mais
exasperantes, 28 ≡ 10 (mod 41). Neste caso, bases diferentes satisfazem as equações que
advêm de fatores diferentes de n − 1. Infelizmente o teste requer que uma única base
satisfaça a todas as equações. Para 41 a menor destas bases é 7.
Em 1975 Brilhart, Lehmer e Selfridge observaram que não é necessário usar uma base
única no teste de Lucas. Podemos nos dar ao luxo de escolher uma base distinta para cada
primo. Com isto obtemos um teste um pouco mais eficiente.
Teste de Primalidade. Seja n > 0 um inteiro tal que
n − 1 = pe11 . . . perr
onde p1 < · · · < pr são primos. Se, para cada i = 1, . . . , r existirem inteiros positivos bi
(2 ≤ bi ≤ n − 1) que satisfaçam
bin−1 ≡ 1 (mod n)
(n−1)/pi
bi
então n é primo.
6≡ 1 (mod n),
2. O TESTE DE BRILHART, LEHMER E SELFRIDGE
69
Não é necessário que os bi ’s sejam todos distintos. Vejamos porque estas equações
forçam a que n seja primo.
Vamos considerar o caso i = 1, o mesmo se aplica a i = 2, . . . , r. Em primeiro
lugar precisamos calcular a ordem s1 de b1 em U(n). Segue do lema chave e da equação
b1n−1 ≡ 1 (mod n) que s1 divide n − 1. Logo os primos que aparecem na fatoração de s1
estão entre os primos p1 , . . . , pr . Assim
s1 = pk11 . . . pkr r
onde k1 ≤ e1 , . . . , kr ≤ er .
(n−1)/p1
Por outro lado, sabemos que b1
é divisível por s1 . Mas
6≡ 1 (mod n). Isto significa que (n − 1)/p1 não
(n − 1)/p1 = pe11 −1 pe22 . . . perr
Comparando com a fatoração de s1 vemos que a única maneira de s1 não dividir (n−1)/p1
é que k1 = e1 . Em outras palavras, pe11 divide s1 .
Não podemos perder de vista que s1 é a ordem de b1 em U(n). Pelo teorema de Lagrange, s1 divide a ordem de U(n); isto é, s1 divide φ(n). Logo pe11 divide s1 que divide
φ(n): portanto pe11 divide φ(n).
Como as contas acima se aplicam também a i = 2, . . . , r concluímos que as equações
do teste implicam que pe11 , pe22 , . . . , perr dividem φ(n). Mas estes números são potências
de primos distintos, logo primos entre si. Assim, pelo lema da seção 6 do capítulo 2, o
produto
pe11 . . . perr = n − 1
também divide φ(n). Como φ(n) ≤ n−1 resta apenas que φ(n) = n−1, e isto é suficiente
para garantir que n é primo.
Finalmente vamos reunir tudo o que aprendemos numa estratégia para verificar primalidade. Suponhamos que temos um número ímpar n, muito grande, e queremos saber se é
primo:
(1) Verificamos, por tentativa, se n é divisível pelos primos até 5000.
(2) Supondo que n não é divisível por estes primos, obtivemos um estoque de bases
para aplicar o teste de Miller.
(3) Supondo que n passou no teste de Miller para todas estas bases, tentamos finalmente aplicar o teste descrito acima.
70
4. TESTES DE PRIMALIDADE
3. A recíproca do teste de Lucas-Lehmer
Ainda há duas coisas por fazer para completarmos nosso estudo do teste de LucasLehmer. A primeira, consiste em mostrar que a recíproca do teste enunciado na seção 1
é verdadeira e a segunda em enunciar o teste de uma maneira mais apropriada à suaimplementação. Para isto, porém, precisamos de alguns resultados adicionais sobre resíduos
quadráticos, o primeiro dos quais é o seguinte critério, provado por Euler em 1748.
Critério de Euler. Se p > 0 é um primo ímpar e b é um inteiro positivo que não é divisível
por p, então
(
1 (mod p)
se b for resíduo quadrático módulo p
b(p−1)/2 ≡
−1 (mod p)
se b não for resíduo quadrático módulo p
D EMONSTRAÇÃO . Temos, pelo teorema de Fermat, que
(b(p−1)/2 )2 ≡ bp−1 ≡ 1
(mod p).
Como a equação quadrática x2 ≡ 1 (mod p) só pode ter as soluções x ≡ ±1 (mod p),
podemos concluir que
b(p−1)/2 ≡ ±1 (mod p).
Portanto, para provar o critério, basta mostrar que b é um resíduo quadrático módulo p se,
e somente se b(p−1)/2 ≡ 1 (mod p).
Suponhamos que b seja um resíduo quadrático módulo p. Neste caso
b ≡ a2
(mod p)
para algum número inteiro positivo a. Mas isto implica que
b(p−1)/2 ≡ (a2 )(p−1)/2 ≡ ap−1 ≡ 1 (mod p),
em que a última congruência é consequência do teorema de Fermat. Para provar a recíproca, usaremos o teorema da raiz primitiva, segundo o qual o grupo U(p) é cíclico.
Digamos que g seja um gerador de U(p) e que
b ≡ gm
(mod p),
em que m é um inteiro positivo. Se
b(p−1)/2 ≡ 1 (mod p)
então
g m(p−1)/2 ≡ 1
(mod p).
3. A RECÍPROCA DO TESTE DE LUCAS-LEHMER
71
Logo, pelo lema chave, p − 1 divide m(p − 1)/2; isto é
m(p − 1)
= (p − 1)ℓ
2
para algum inteiro positivo ℓ. Cancelando p − 1 e multiplicando a igualdade por 2, concluímos que m = 2ℓ. Mas isto implica que
b ≡ g m ≡ (g ℓ )2
(mod p)
é um resíduo quadrático. como precisávamos mostrar.
Vejamos como usar o critério de Euler para provar que 3 não é um resíduo quadrático
relativamente aos primos que deixam resto 7 na divisão por 12. A razão para considerarmos
estes primos é que
(45)
22n+1 − 1 ≡ (4n · 2) − 1 ≡ 7 (mod 12);
pois 4n ≡ 4 (mod 12) qualquer que seja o inteiro n > 1.
P ROPOSIÇÃO 3.1. Se p = 12m + 7 é um número primo para algum inteiro positivo m,
então 3 não é um resíduo quadrático módulo p
D EMONSTRAÇÃO . Como U(p) tem p − 1 = 12m + 6 elementos,
M = {1, . . . , 6m + 3
contém metade dos elementos de U(p). Além disso, se a ∈ M, então
−a = p − a ∈
/M
pois 1 ≤ a ≤ 6m + 3 implica que
6m + 4 < p − a = 12m + 6.
Como o produto 3 · a pertence a U(p) para cada 1 ≤ a ≤ 6m + 3, podemos concluir que
3·a∈M
ou
− 3 · a ∈ M.
Precisamos determinar quais são os elementos de M para os quais cada um destes dois
casos ocorre. Levando em conta que
p−1
3(2m + 1) = 6m + 3 ≤
2
temos que
3·a∈M
para todo 1 ≤ a ≤ 2m + 1. Por outro lado, se
a = (2m + 1) + k = 4m + 2 − k
com 1 ≤ k ≤ 2m + 1, então
3a = 12m + 6 − 3k = p − 1 − 3k = p − (3k + 1)
72
4. TESTES DE PRIMALIDADE
de modo que, neste caso,
−3 · a = 3k + 1 ∈ M.
Finalmente, se
a = (4m + 2) + k
em que 1 ≤ k ≤ 2m + 1, então
3 · a = 12m + 6 + 3k = 3k − 1 ∈ M,
para estes valores de k. Resumindo, descobrimos que


quando
 3k
3 · j + k = −3k + 1 quando

 3k − 1 quando
j=0
j = 2m + 1
j = 4m + 2,
para 1 ≤ k ≤ 2m + 1. Mas isto significa que
(3 · 1) · · · (3 · 6m + 3)
é igual a
2m+1
Y
k=1
Logo,
3k ·
2m+1
Y
−(3k + 1) ·
k=1
2m+1
Y
3k − 1 = (−1)2m+1 (1 · 6m + 2).
k=1
6m+3
3
(1 · 6m + 2) = (−1)(1 · 6m + 2),
pois 2m + 1 é ímpar. Cancelando os termos comuns, obtemos
3
2m+1
= −1
de modo que, pelo critério de Euler, 3 não é um resíduo quadrático.
To be continued...
Referências Bibliográficas
[1] W. R.Alford, A. Granville e C. Pomerance, There are infinitely many Carmichael numbers, Ann. of Math.
140 (1994), 703–722.
[2] F. Arnault, Constructing Carmichael numbers which are strong pseudoprimes to several bases, J. Symbolic Computation, 20 (1995), 151–161.
[3] M. Artin, Algebra, Prentice-Hall, Englewood Cliffs, (1991).
[4] C. B. Boyer, História da Matemática, traduzido por E.F. Gomide, Editora Edgar-Blücher, São Paulo,
(1994).
[5] D. M. Bressoud, Factorization and primality testing, Undergraduate Texts in Mathematics, SpringerVerlag, New York (1999).
[6] R. D. Carmichael On composite numbers P which satisfy the Fermat congruence aP −1 ≡ 1 (mod P ),
Amer. Math. Monthly 19 (1912), 22–27.
[7] D. Cox, J. Little, e D. O’Shea, Ideals, varieties and algorithms: an introduction to computation algebraic
geometry and commutative algebra, Undergraduate Texts in Mathematics, Springer-Verlag, New York
(1992).
[8] J. H. Davenport, Y. Siret e E. Tournier, Computer Algebra: systems and algorithms for algebraic computation, translated by A. Davenport and J.H. Davenport, Academic Press, London (1998).
[9] M. Davis, What is computation?, in Mathematics Today, editado por L. A. Steen, Vintage Books, New
York (1980), 241–267.
[10] L. E. Dickson, A history of the theory of numbers, Chelsea Publishing Company, New York, (1952).
[11] H. M. Edwards, Fermat’s last theorem, Graduate Texts in Mathematics 50, Springer-Verlag, New York
(1977).
[12] H. M. Edwards, Galois theory, Graduate Texts in Mathematics 101, Springer-Verlag, New York (1984).
[13] Pierre de Fermat, Oeuvres de Fermat, editada por Paul Tannery e Charles Henry, volume III, GauthierVillars (1896).
[14] R. P. Feynman, QED: the strange theory of light and matter, Princeton University Press, Princeton
(1985).
[15] C. F. Gauss, Disquitiones Arithmeticæ, translated by A.A. Clarke, revised by W.C. Waterhouse with the
help of C. Greither e A.W. Grotendorst, Springer-Verlag, New York (1986).
[16] P. Giblin, Primes and programming, Cambridge University Press, Cambridge (1993).
73
74
REFERÊNCIAS BIBLIOGRÁFICAS
[17] A. Gonçalves, Introdução à álgebra, Projeto Euclides, IMPA, Rio de Janeiro (1979).
[18] G. B. Gostin, New factors of Fermat numbers, Math. of Comp. 64 (1995), 393–395.
[19] G. H. Hardy, e E.M. Wright, An introduction to the theory of numbers, quinta edição, Oxford Science
Publications, Oxford University Press, Oxford (1994).
[20] A. Hefez, Curso de Álgebra, vol. 1, Coleção Matemática Universitária, IMPA, Rio de Janeiro (1993).
[21] A. E. Ingham, The distribution of primes, Cambridge University Press, Cambridge (1932).
[22] D. E. Knuth, The Art of computer programming, vol. 2, Seminumerical algorithms, segunda edição,
Addison-Wesley Publishing Company, Reading (1981).
[23] N. Koblitz, A course in number theory and cryptography, Graduate Texts in Mathematics 97, SpringerVerlag, New York (1987).
[24] E. Kranakis, Primality and criptography, Wiley-Teubner series in Computer Science, B.G. Teubner e
J. Wiley & Sons (1986).
[25] M. Lemos, Criptografia, números primos e algoritmos, 17◦ Colóquio Brasileiro de Matemática,
IMPA/CNPq (1989).
[26] A. K. Lenstra, H. W. Lenstra jr, M. S. Manasse e J. M. Pollard, The factorization of the ninth Fermat
number, Math. of Comp., 61 (1993), 319–349.
[27] C. Pomerance, A tale of two sieves, Notices of the Amer. Math. Soc., 43(12) (1996), 1473–1485.
[28] S. Ramanujan, Collected papers of Srinivasa Ramanujan, editado por G. H. Hardy, P. V. Seshu Aiyar
e B. M. Wilson, Cambridge University Press, Cambridge (1927).
[29] H. Riesel, Prime numbers and computer methods of factorization, second edition, Progress in Mathematics 126, Birkhäuser, Boston (1994).
[30] R. L. Rivest, A. Shamir e L. Adleman, A method for obtaining digital signatures and public-key cryptosystems, Comm. ACM, 21 (1978), 120–126.
[31] P.W. Shor, Algorithms for quantum computation: discrete logarithms and factoring, in Proceedings of
35th Annual Symposium on Foundations of Computer Science, IEEE Computer Science Press (1994),
124–134.
[32] J. H. Silverman e J. Tate, Rational points on elliptic curves, Undergraduate Texts in Mathematics,
Springer-Verlag, New York (1992) .
[33] B. L. van der Waerden, A history of algebra, Springer-Verlag, Berlin-Heidelberg (1985).
[34] J. F. Voloch, A distribuição dos números primos, Matemática Universitária, número 06 (1987), 71–82.
[35] A. Weil, Number theory: an approach through history, Birkhäuser, Boston (1987) .
[36] H. Weyl, Symmetry, Princeton University Press, Princeton (1982) .