Introdução À Teoria Dos Números: Notas de Aula - Jerônimo Pellegrini Id
Introdução À Teoria Dos Números: Notas de Aula - Jerônimo Pellegrini Id
Jerônimo Pellegrini
id: 13e852406210a08d9a115a9faad64881302c9f71
Sumário i
Nomenclatura vii
Parte I 1
1 Introdução 3
2 Números 5
2.1 Naturais . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 6
2.1.1 Um modelo para N . . . . . . . . . . . . . . . . . . . . . . . 7
2.1.2 Independência dos axiomas . . . . . . . . . . . . . . . . . 8
2.2 Indução . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 9
2.2.1 Indução “Forte” . . . . . . . . . . . . . . . . . . . . . . . . 15
2.2.2 Aritmética . . . . . . . . . . . . . . . . . . . . . . . . . . . 17
2.2.3 Ordem . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 20
2.3 Descida Infinita . . . . . . . . . . . . . . . . . . . . . . . . . . . . 24
2.4 Inteiros e Racionais . . . . . . . . . . . . . . . . . . . . . . . . . . 30
2.4.1 Definições e Modelos . . . . . . . . . . . . . . . . . . . . . 33
2.5 Anéis e Corpos . . . . . . . . . . . . . . . . . . . . . . . . . . . . 34
3 Bases 41
3.1 Naturais . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 42
3.2 Racionais positivos . . . . . . . . . . . . . . . . . . . . . . . . . . 45
3.3 A função base 13 de Conway . . . . . . . . . . . . . . . . . . . . . 46
4 Divisibilidade 55
4.1 Divisão . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 55
4.2 Máximo Divisor Comum . . . . . . . . . . . . . . . . . . . . . . . 58
4.3 Algoritmo de Euclides para cálculo do MDC . . . . . . . . . . . . 63
4.3.1 Coeficientes de Bézout: algoritmo estendido de Euclides . 65
4.4 Mínimo Múltiplo Comum . . . . . . . . . . . . . . . . . . . . . . . 68
4.5 Números de Fibonacci . . . . . . . . . . . . . . . . . . . . . . . . 69
i
4.5.1 Complexidade do algoritmo de Euclides . . . . . . . . . . 75
4.6 Domínios Euclideanos: Inteiros Gaussianos e Polinômios . . . . 76
5 Primos 89
5.1 Fatoração Única em Z . . . . . . . . . . . . . . . . . . . . . . . . 90
5.2 Números de Mersenne e de Fermat . . . . . . . . . . . . . . . . . 93
5.3 Infinitos primos . . . . . . . . . . . . . . . . . . . . . . . . . . . . 98
5.4 4k + 1, 4k + 3 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 102
5.5 Fatoração Única em Dominios Euclideanos . . . . . . . . . . . . 106
6 Congruências 113
6.1 Relações de congruênca e aritmética modular . . . . . . . . . . 113
6.2 Aplicação: critérios de divisibilidade . . . . . . . . . . . . . . . . 123
6.2.1 Em bases diferentes . . . . . . . . . . . . . . . . . . . . . . 125
6.3 Congruências Lineares e Equações Diofantinas . . . . . . . . . . 126
6.4 O Teorema Chinês dos Restos . . . . . . . . . . . . . . . . . . . . 131
6.4.1 Módulos não co-primos . . . . . . . . . . . . . . . . . . . . 136
6.5 O Teorema Chinês dos Restos, novamente . . . . . . . . . . . . . 140
6.6 Congruências lineares em n variáveis . . . . . . . . . . . . . . . 144
6.7 Congruências polinomiais de qualquer grau . . . . . . . . . . . . 144
6.8 Sequência de Fibonacci módulo m . . . . . . . . . . . . . . . . . 151
ii
9.2.4 Demonstração de Gauss (a quarta, usando raízes da uni-
dade) . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 244
9.3 Método para resolução de congruências quadráticas . . . . . . . 249
9.3.1 Módulo primo . . . . . . . . . . . . . . . . . . . . . . . . . 249
9.3.2 Módulo potência de primo . . . . . . . . . . . . . . . . . . 250
9.3.3 Módulo composto . . . . . . . . . . . . . . . . . . . . . . . 251
9.3.4 Equação geral do segundo grau . . . . . . . . . . . . . . . 252
Parte II 275
iii
15 Frações Contínuas 339
15.1Frações Contínuas Finitas e Números Racionais . . . . . . . . . 339
15.2Frações Contínuas Infinitas e Números Irracionais . . . . . . . . 344
15.2.1Convergentes . . . . . . . . . . . . . . . . . . . . . . . . . 346
15.3Melhor aproximação . . . . . . . . . . . . . . . . . . . . . . . . . 350
15.4Frações Contínuas Periódicas . . . . . . . . . . . . . . . . . . . . 353
15.5Construção de R com frações contínuas . . . . . . . . . . . . . . 356
15.6 e é irracional . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 358
15.6.1Demonstração de Cohn, com frações contínuas . . . . . . 359
15.6.2Demonstração de Fourier, sem frações contínuas . . . . . 361
15.7 π é irracional . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 363
15.8 φ é irracional . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 365
15.9Exercícios . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 366
Apêndices 380
A Dicas e Respostas 383
iv
Sobre este texto
Kleiner, Israel. Excursions in the History of Mathematics. [S. l.]: Birkhauser, 2012.
Kleiner conta a história do desenvolvimento dos números complexos: Bhaskara teria escrito
O quadrado de um número positivo, também o de um número negativo, é
positivo; e a raiz quadrada de um número positivo é dupla, positiva e negativa;
v
cussões sobre inteiros Gaussianos, raízes da unidade, a demonstração da lei
da reciprocidade quadrática usando raízes da unidade – dada por Gauss –,
e formas modulares).
Apresentação moderna. Estruturas algébricas e outros conceitos são
apresentados tão cedo quando possível no texto, de maneira a tornar trans-
parente a forma como a teoria de Números está integrada com outras áreas
da Matemática, e também refletindo uma visão moderna do assunto. isto
não é feito de maneira a forçar abstrações abrutamente, e sim gradual-
mente, muitas vezes alternando conceitos abstratos com exemplos concre-
tos.
Enunciados em notas de rodapé. Não são usadas apenas para contex-
tualização histórica, claro. Além de comentários gerais que não cabem no
texto, os teoremas e lemas definidos anteriormente tem seu enunciado re-
produzido em notas de rodapé quando são citados. Por exemplo, quando
o Teorema de Wilson é usado, a nota de rodapé traz seu enunciado – com
isto o leitor iniciante na área, que não se lembre exatamente se o enunciado
mencionava “+1” ou “−1”, poderá resolver sua dúvida na mesma página.
Sistemas de escrita e transliterações. Os nomes de autores estrangei-
ros, quando em notas de rodapé, são apresentados em seus sistemas de
escrita nativos, e também transliterados. Para o Chinês, tanto o sistema
simplificado como o tradicional são usados, e a pontuação européia (sinais
como “:” e “?”) também – estas marcas não existiam em textos clássicos,
mas foram incorporadas à escrita chinesa nos Séculos XIX e XX. Em Latim
e Alemão, há uma tentativa e manter as letras não mais usadas, como o
esse longo ( ſ )4 e o “eszett” ( ß )5 – mas devido à complexidade de man-
ter um documento LATEX multilíngue com ligaduras, não houve esforço para
preservá-las.
ainda é usado.
vi
Nomenclatura
Neste texto usamos marcadores para final de definições (), exemplos (J)
e demonstrações ( ). Em alguns Capítulos, vetores são denotados por vari-
áveis em negrito (por exemplo, “v”).
vii
a
m Símbolo de Jacobi, página 227
a
p Símbolo de Legendre, página 227
viii
ζ raiz primitiva da unidade, página 217
ix
SL(n, F) grupo linear especial, página 312
x
Parte I
Capítulo 1
Introdução
3
por Pierre de Fermat em 1637, e permaneceu sem demonstração até 1994,
quando Andrew Wiles conseguiu finalmente – usando um ferramental mate-
mático longe de ser trivial – garantir que de fato a proposição é verdadeira.
comum entre Matemáticos que a demonstração de Fermat tivesse alguma falha sutil. Fermat
usualmente trocava cartas com outros matemáticos, e esta nota não estava em qualquer de
suas cartas – ela foi encontrada na margem de um livro, onde havia muitas outras anotações,
portanto um “lembrete para si mesmo”. Isso pode indicar também que Fermat poderia ter
tido uma idéia que anotou, mas que posteriormente verificou que era falha (e por isso nunca
chegou a apresentá-la a outros).
4
Capítulo 2
Números
Este Capítulo passa por uma carcterização de números naturais (não é uma
definição, apenas uma “caracterização” – ums descrição de propriedades
desses números). Esta abordagem foi escolhida porque leva naturalmente
à descrição da indução finita como método de demonstração. No entanto,
esta visão, com números sento definidos de forma abstrata, é recente na
História da Matemática. O conceito de número surgiu muito antes desta
formalização, e as definições/construções anteriores não são “erradas”. São
diferentes. Escolhemos uma visão por sua utilidade, não por uma suposta
superioridade.
Para se demonstrar o que quer que seja, precisamos partir de pressupostos
anteriores. Tomando um exemplo qualquer dentro da Matemática: quando
nosso foco de atenção é o Cálculo, demonstramos que a regra da cadeia
para derivação é válida – mas aquela demonstração presume como certo
que as operações que usamos ao demonstrar são bem definidas e que suas
propriedades valem. É interessante lançar o olhar sobre estas operações
e questionar o que estamos presumindo. Levando este raciocínio adiante,
chegamos ao estudo de conjuntos de números e operações sobre eles, a
que damos o nome de “estruturas algébricas”. Um passo mais e podemos
questionar se há alguma forma de definir rigorosamente o que chamamos
de “números naturais” (e inteiros, racionais, e reais). É evidente que em
algum momento teremos de parar e nos contentar em aceitar alguma quan-
tidade de fatos e entidades fundamentais, de forma a poder trabalhar as
demonstrações que precisamos. A estes fatos fundamentais damos o nome
de axiomas1 .
Neste Capítulo abordamos os Axiomas de Dedekind-Peano, que definem o
1 O que se toma como axioma e o que se define e demonstra varia conforme o objetivo. Em um
5
conjunto dos números naturais. A partir destes, é possível desenvolver tanto
as operações aritméticas básicas em N como os conjuntos Z, Q e, após de-
senvolver um ferramental mais elaborado, construir o conjunto dos reais e
operações aritméticas nele.
2.1 Naturais
Os Axiomas de Dedekind-Peano, descritos2 por Dedekind6 e Peano7 , são
uma maneira de definir os números naturais usando tres conceitos primiti-
vos (“número”, “zero” e “sucessor”) e cinco axiomas. Aqui reproduzimos os
Axiomas de Dedekind-Peano que nos interessam (há quatro deles que tra-
tam da relação de igualdade, mas presumimos aqui que esta já está bem
definida8 ). Este recorte é comum na apresentação destes axiomas.
2 No século XIX é que ganha força o interesse em axiomatizar a aritmética como fundamento
Dedekind, Richard. Was sind und was sollen die Zahlen? [S. l.], 1888. Publicado como
brochura.
Giuseppe Peano publicou uma versão simplificada dos axiomas de Dedekind, mas ainda enu-
merando nove axiomas (e não cinco, como fazemos hoje).
Peano, Giuseppe. Arithmetices principia, nova methodo exposita. [S. l.], 1889. Disponí-
vel em Latim, com tradução para Inglês em [Link]
Este idéia ganhou força, e houve muito interesse de Matemáticos no início do Século XX em
uma possível formalização completa da Matemática. Um dos expoentes dessa visão foi
Russel4 , e a essa escola de pensamento se dá o nome de Logicismo. Há um livro inrodutório
do próprio Russel sobre o assunto.
Russel, Bertrand. Introdução à Filosofia Matemática. [S. l.]: Zahar, 1974.
6
(i) 0 é um número natural9 ;
naturais como {1, 2, . . .}. É comum incluir o zero por ser o elemento neutro para a adição.
10 Ernst Zermelo (1871-1953), Alemão.
11 Abraham Fraenkel (1891-1965), Alemão-Ieraelita.
12 Thoralf Skolem (1887-1963), Norueguês.
13 Não juntos – Zermelo publicou seu trabalho inicialmente em 1908; Fraenkel e Skolem
Bernays, Paul; Fraenkel, Abraham. Axiomatic Set Theory. [S. l.]: North-Holland, 1958.
7
ZF houve várias construções do conjunto dos naturais. Um destes mode-
los, dado por John von Neumann, é apresentado aqui. Usamos apenas a
existência do conjunto vazio e a operação de união. Determinamos que
o número 0 é ∅
o número 1 é {0} = {∅}
o número 2 é {0, 1} = {∅, {∅}}
..
.
(i) pode-se traçar uma linha reta entre quaisquer dois pontos;
(iii) um círculo pode ser traçado com qualquer ponto como centro e com
qualquer raio;
(v) dado qualquer ponto P fora de uma reta R, é possível traçar uma única
reta paralela a R passando por P .
8
Geometria resultante é completamente diferente da Geometria Euclideana.
Ao trocar “uma reta paralela a R” por “ao menos duas retas paralelas a R”,
surgem os Axiomas da Geometria Hiperbólica17 .
Ao apresentar modelos diferentes que satisfazem todos os axiomas, exceto
um deles, provamos que aquele axioma não pode ser deduzido a partir dos
outros.
Os axiomas de Dedekind-Peano são independentes: nenhum deles pode ser
demonstrado a partir dos outros. Se removermos um deles, teremos algo
diferente dos números naturais.
(i) Para o primeiro axioma, o conjunto vazio. Note que o primeiro axioma
é o único que requer a existencia de um elemento – os outros são afir-
mações quantificadas com ∀, e portanto condicionais. Assim, para o
conjunto vazio todos os outros axiomas são verdadeiros por vacuidade,
e ∅ seria um modelo viável para os naturais;
(iv) Para o quarto axioma, o conjunto {0, 1}, sendo que um sucede tanto
zero como um: s(0) = s(1) = 1;
2.2 Indução
O quinto Axioma de Dedekind-Peano, chamado de “axioma da indução”, é,
mais que parte de uma definição, uma poderosa ferramenta para demons-
17 Gauss declarou ter construído um sistema sem o postulado das paralelas, e o chamou de
“Geometria não-Euclideana” – mas não o publicou. Franz Taurinus publicou alguns resultados
relacionados, e finalmente um sistema completo de geometria hiperbólica foi publicado
independentemente por Lobachevsky– Никола́ й Ива́ нович Лобаче́вский em Russo –18 e
por Bolyai19 . A história do postulado das paralelas é tratada detalhadamente por David Burton.
Burton, David. The History of Mathematics: An Introduction. In: 6. ed. [S. l.]: McGraw-Hill,
2006. 11 - Nineteenth-Century Contributions: Lobachevsky to Hilbert.
9
trações, e é usualmente apresentado como tal20 . A seguir o axioma é
20 É um princípio antigo, e há registros de seu uso desde pelo menos 1575. W. H. Bussey
afirma que:
Cantor em seu Vorlesungen iuber Geschichte der Mathematik diz que Pascal
foi quem originou o método da indução completa. Mas corrigiu essa afirmação
em uma breve nota no Zeitschrift fur Mathematischen und Naturwissenschaf-
tlichen Unterricht. Nessa nota ele aponta que foi informado por G. Vacca que
Maurolycus descreveu e usou o método em sua aritmética, que foi publicada em
1575,
O original:
Cantor in his Vorlesungen iuber Geschichte der Mathematik says that Pascal
was the originator of the method of complete induction. But he has corrected this
statement in a brief note in the Zeitschrift fur Mathematischen und Naturwis-
senschaftlichen Unterricht. In this note he says that he has been informed by G.
Vacca that Maurolycus described and used the method in his arithmetic which
was published in 1575.
Talvez seja razoável presumir que o princípio possa ter surgido também em diferentes con-
textos, possivelmente antes disso. Por exemplo, a demonstração de Euclides de que “há mais
números primos do que qualquer quantidade proposta” não é uma demonstração por indução,
da forma como entendemos hoje, mas é um passo de indução perfeitamente aceitável (a partir
de um conjunto de primos de tamanho n, determina-se um novo conjunto, de tamanho n + 1) –
a demonstração está na Seção 5.3, com comentários em uma nota de rodapé.
Quanto às demonstrações de Pascal por indução, é interessante observar que eram feitas
com muito menos rigor e formalidade que as produzidas a partir do Século XX. Por exemplo
em seu “Tratado do Triângulo Aritmético”21 , Pascal define o triângulo aritmético, e enuncia
várias “consequências do triângulo” (teoremas a respeito dele).
Pascal, Blaise. Traite du Triangle Arithmetique, avec quelques autres petits traitez
sur la mesme matiere. Paris: Guillaume Desprez, 1665.
10
apresentado novamente, desta vez como técnica e não como definição.
Dado um predicado P a respeito de número naturais, se
90 − 20 = 1 − 1 = 0, divisível por 7
triângulo de Yáng Hu (o chinês 杨辉 – Yáng Huī – viveu entre 1238 e 1298, e trabalhou em
diversos problemas, incluindo equações quadráticas e quadrados mágicos – mas o triângulo
foi registrado em mais de uma ocasião na história da Matemática chinesa, e poderia ter sido
descoberto por um antecessor de Yáng Huī , Jiǎ Xiàn (贾宪)); descrito por Omar Khayyam (ﻋﻤﺮ
ﺧّﯿﺎم, persa, viveu entre 1044 e 1123); e também pelo indiano Halayudha (हलायुध) no século X.
Martzloff, Jean-Claude. A History of Chinese Mathematics. [S. l.]: Springer, 2006.
Este livro contém uma grande quantidade de referencias a idéias que, apesar de serem usu-
almente citadas como européias, foram registradas anteriormente na China. Uma figura
descrevendo duas versões chinesas do triangulo de Pascal está na página 231.
Kennedy, Evelyn. Omar Khayyam. The Mathematics Teacher, v. 59, n. 2, p. 140–142,
1966.
Bag, Amulya Kumar. Binomial theorem in ancient India. Indian Journal of History of Sci-
ence, v. 1, n. 1, p. 68–74, 1966.
11
Passo:
u0 = 0
u1 = 1
un = un−1 + un−2
X
n
u2i = un un+1 .
i=1
u21 = u1 u2
11 = (1)(1)
Pk
Hipótese: i=1 u2i = uk uk+1 .
12
Passo:
X X
k+1 k
!
u2i = u2i + u2k+1
i=1 i=1
= uk uk+1 + u2k+1 (pela hipótese de indução)
= uk1 (uk + uk + 1)
= uk+1 uk+2 .
X
1−1
x1 − 1
xi = x0 = 1 = .
x−1
i=0
monstrações. Este exemplo específico é discutido por Albert B. Bennet em um artigo onde a
apresentação visual da série é usada.
Bennet Jr, Albert B. Visualizing the Geometric Series. The Mathematics Teacher, v. 82,
n. 2, p. 130–136, 1989.
Embora Bennet não tenha apresentado uma demonstração geométrica do Teorema, as ilustra-
ções das séries mostradas são bastante interessantes. Para x = 2, Bennet apresenta figuras
representando valores da série:
1 2 22 23 24
Em seguida, ilustra que a soma dos quatro primeiros termos é 24 − 1:
1+2+ = 24 − 1
22 + 23
13
Agora fazemos o passo de indução. A hipótese é que para n,
X
n−1
xn − 1
xi = .
x−1
i=0
Então, para n + 1,
X
[n+1]−1
X
n
xi = xi
i=0 i=0
X
n−1
= xn + xi
i=0
nxn − 1
=x + (usamos a hipótese de indução!)
x−1
(x − 1)xn + xn − 1
=
x−1
x[n+1] − 1
= .
x−1
Ou seja,
X
[n+1]−1
x[n+1] − 1
xi = ,
x−1
i=0
T1 = 1 T2 = 3 T3 = 6 T4 = 10
A partir da figura fica claro que Tn é igual a Tn−1 com mais uma linha
25 Uma interessante exposição é dada por John Hiscocks.
14
contendo n elementos, portanto os números triangulares são
T1 = 1,
Tn = Tn−1 + n.
n(n + 1)
Tn = .
2
Base: trivialmente, n = 1 é triangular.
Hipótese: k(k + 1)/2 é o k-ésimo número triangular.
Passo: sabemos que Tk é o k-ésimo número triangular (pela hipótese de
indução), e que
Tk+1 = Tk + (k + 1).
Usamos a hipótese de indução, e
k(k + 1)
Tk+1 = + (k + 1)
2
k(k + 1) + 2(k + 1)
=
2
(k + 1)(k + 2)
=
2
(k + 1)(k + 1 + 1)
= ,
2
que a forma do enunciado para k + 1. J
15
Exemplo 2.6. Provaremos que todo natural maior que onze pode ser escrito
como soma de múltiplos de 4 e de 5.
Agora mostramos que isso implica que n também pode ser escrito dessa
forma – ou seja, n = 4q + 5r.
n = (n − 4) + 4
= 4a + 5b + 4
= 4(a + 1) + 5b.
12 = 4 + 4 + 4 = 3(4) + 0(5)
13 = 5 + 4 + 4 = 2(4) + 1(5)
14 = 5 + 5 + 4 = 1(4) + 2(5)
15 = 5 + 5 + 5 = 0(4) + 3(5). J
Provaremos que
an = 3 − 2n.
A hipótese de indução é que, para todo k ≤ n, ak tem a forma acima.
Para o passo, mostraremos que isso implica que an também é dessa forma.
A partir da definição de an obtemos
an = 2an−1 − an−2
= 2(3 − 2(n − 1)) − (3 − 2(n − 2))
= 3 − 2n.
Como usanos an−1 e an−2 no passo, precisamos dos dois primeiros termos
16
na base. Asism, temos
a1 = 3 − 2(1) = +1
a2 = 3 − 2(2) = −1,
X
n
n≤ a2k ≤ n + 1 + (−1)n .
k=1
X
1
1≤ a21 ≤ 1 + 1 + (−1)1
k=1
1≤ a2k ≤ 1,
X
n
!
n+1≤ a2k + a2n+1 ≤ (n + 1) + 1 + (−1)n
k=1
n + 1 ≤ n + a2n+1 ≤ (n + 1) + 1 + (−1)n+1
1 ≤ +a2n+1 ≤ 1 + 1 + (−1)n+1
1 ≤ +a2n+1 ≤ 2 + (−1)n+1 .
Então a2n+1 é maior ou igual que um, mas também é menor ou igual que
2+(−1)n+1 , que pode ser 1 ou 3. De qulaquer maneira, como é um quadrado,
só pode ser um. J
2.2.2 Aritmética
Tendo caracterizado o conjunto dos números naturais, precisamos de ope-
rações para que possamos realizar operações com eles. Definimos a seguir
26 Este problema estava incluído na Hong Kong Advanced Level Examination em 1995.
17
soma e multiplicação para naturais, a partir somente de nossa construção
(usamos somente o conceito de número natural e o de sucessor).
n+0=n
n + s(m) = s(n + m)
n0 = 0
ms(n) = mn + m.
Será útil também dar nome ao número um, para tornar mais confortável
algumas demonstrações adiante:
Não presumimos nada, por mais intuitivo que seja, sem demonstrar – a se-
guir, por exemplo, provamos que s(a) = a + 1.
(v) ab = 1 ⇒ a = 1 e b = 1;
(vi) a + b = 0 ⇒ a = b = 0, e ab = 0 ⇒ a = 0 ou b = 0;
18
Demonstração. Demonstramos parte das propriedades; outra parte servirá
como exercício.
(a + b) + 0 = a + b ((· · · ) + 0 = · · · )
= a + (b + 0) (b = b + 0)
19
Passo:
2.2.3 Ordem
Além da aritmética, nos interessa definir alguma relação de ordem em N.
Isto pode ser feito de maneira bastante simples, mas não se pode esperar
que seja sempre possível em qualquer estrutura (por exemplo, não há como
definir para os números complexos uma relação de ordem que seja consis-
tente com as operações aritméticas27 ).
Definição 2.13 (menor ou igual). Definimos a relação ≤ (menor ou igual)
para naturais de forma que a ≤ b se e somente se existe algum m ∈ N tal
que a + m = b.
Damos exemplos: 4 ≤ 10 porque 4 + 6 = 10; também 0 ≤ 2 porque 0 + 2 = 2.
Vale observar que esta definição de ≤ depende da definição de soma – e
que nossa noção de ordem, portanto, está fundamentada na operação que
desenvolvemos para os naturais, e só faz sentido a partir dela.
27 Embora possamos ordenar os complexos, por exemplo, por norma, não podemos escolher
uma ordem que os torne um corpo ordenado. Se houvesse uma relação de ordem total ≺ para
C, teríamos necessariamente que i ≺ 0 ou que 0 ≺ i, mas não ambos. No entanto, nos dois
casos chegaríamos a contradições.
20
Definição 2.14 (relação de ordem parcial). Uma relação R em um conjunto
X é dita de ordem parcial não-estrita se para todos x, y, z ∈ X,
i) R é reflexiva (xRx);
Exemplo 2.15. Seja X = {a, b, c, d, e}, e seja ≺ uma relação em X tal que
a≺a
a≺b
b≺b b≺d
a≺c
c≺c b≺e
a≺d
d≺d d≺e
a≺e
e≺e
O grafo a seguir (chamado de diagrama de Hasse) representa a relação
(uma aresta de x a y significa que x ≺ y). Para maior clareza, não são
mostrados no grafo o relacionamento de elementos com eles mesmos (a ≺
a, b ≺ b) etc.
a b d e
• reflexiva, porque todo elemento se relaciona com ele mesmo (vide pri-
meira coluna na descrição da relação);
21
i) Reflexividade: A ⊆ A, trivialmente.
Princípio da boa ordem: Todo subconjunto não vazio dos naturais tem um
menor elemento – ou seja, se S ∈ N, então existe um n tal que ∀q ∈ S, n ≤ q.
ser verificada em textos sobre Teoria de Conjuntos. Uma discussão da usual confusão nas
demonstrações de equivalência dos princípios da boa ordem e da indução está no artigo
Öhman, Lars-Daniel. Are Induction and Well-Ordering Equivalent? The Mathematical In-
telligencer, v. 41, n. 3, p. 33–40, 2019.
22
Antes de mais nada, observamos que como 0 não é sucessor de ninguém,
não existem números a, b 6= 0 tal que a + b = 0. Logo ninguém é menor que
zero.
Suponha agora que haja algum S ∈ N onde não exista menor elemento.
Provaremos, por indução, que S é vazio.
Base: necessariamente 0 ∈/ S, porque se 0 estivesse em S, ele seria o menor
elemento de S (pelo Axioma (iii) de Dedekind-Peano).
Hipótese: supomos que nenhum k ≤ n está em S (n também está fora de S).
Passo: s(n) também não pode estar em S, porque pela hipótese de indu-
ção não há ninguém menor que s(n) em S, e portanto s(n) seria o menor
elemento de S.
Assim, S não tem elementos29 .
23
vez depende da definição de operações aritméticas, que tornariam a descri-
ção dos naturais demasiado grande – é portanto mais interessante manter
o axioma da indução.
Apesar de Fermat ter declarado ser o inventor do método, este parece ter sido usado já nos
Elementos, de Euclides, na demonstração da proposição 31 do livro sete:
Todo número composto é medido por um número primo.
Em Grego,
Απας σύνθεντος ἀριθμὸς ὑπὸ πρώτου τινὸς ἀριθμοῦ μετρεῖται.
(Apas sýnthentos arithmós ypó prótou tinós arithmoú metreítai. )
Em linguagem moderna, “todo número composto é divisível por algum número primo”. O
argumento de Euclides (de forma muito resumida) é: Se A é composto, algum número B < A o
divide. Se B é primo, terminamos. Senão, B é composto, e aplica-se a idéia novamente. Como
uma sequência de números cada vez menores será gerada, em algum momento um número
primo deverá ser encontrado, porque é impossível haver uma sequência infinita de inteiros,
24
O princípio da descida infinita é, essencialmente, o princípio da boa or-
dem, ligeiramente refraseado: “se algum processo iterativo gera, a partir
de n, números naturais menores que n, então esse processo deve necessa-
riamente parar”.
As demonstrações dos Teoremas que seguem nesta seção ilustram o método.
A primeira delas versa sobre triângulos retângulos, e necessita de um Lema
de Euclides.
Antes da demonstração, definimos tripla pitagórica 31 .
O Lema 2.21 determina que triplas pitagóricas sempre são compostas por
dois números (na verdade, pode-se ler o Lema como um método32 para obter
triplas a partir de dois números co-primos m, n).
a = m2 − n2 ,
b = 2mn,
c = m2 + n2 .
“Não era Teorema”, porque não foi demonstrado inicialmente pelos pitagóricos. E “não era
de Pitágoras”, porque também não foi descoberto nem por Pitágoras e nem pelos outros
pitagóricos (era conhecido bem antes deles).
A relação descrita no Teorema é descrita de diferentes maneiras em diferentes culturas, e
em particular, os pitagóricos pareciam tratar o assunto de um ponto de vista aritmético, e
não geométrico. Uma seção especificamente dedicada a isto é encontrada no livro de Tatiana
Roque.
Roque, Tatiana. História da Matemática: uma visão crítica, desfazendo mitos e len-
das. [S. l.]: Zahar, 2012.
32 Este é o método discutido por Diofanto e Proclus. Pitágoras descrevia outro método, que
gera algumas, mas não todas, as triplas primitivas: seja a ímpar, então a tripla é a2 , ((a −
1)/2)2 , ((a + 1)/2)2 .
33 Fermat descreveu de forma superficial a demonstração, mas ela pode ser reconstruída a
partir dali.
25
Teorema 2.22 (Fermat). Um triângulo retângulo com lados racionais não
pode ter dois lados cada um com comprimento igual a um quadrado ou duas
vezes um quadrado.
n = a2 p2
n
= a2
p2
E se n é dobro de quadrado,
n = 2a2 p2
n
= 2a2
p2
a = x 2 − y2 ,
b = 2xy,
c = x 2 + y2 .
c = x 2 + y2
a = 2xy
b = x 2 − y2
26
Mas b e c são ímpares, e não podem ser dobro de quadrado (e o enunciado
determina que o triângulo tem dois lados que são ou quadrado ou dobro de
quadrado). Temos portanto duas possibilidades:
i) b e c são quadrados;
x2
√
bc
y2
Isso porque, como b e c são quadrados, podemos extrair sua raiz para cons-
truir um cateto, e a partir daí temos
√ 2
bc + (y2 )2 = bc + y4 (quadrados dos catetos)
= x 4 − y4 + y4
= x4
= (x2 )2 . (quadrado da hipotenusa)
x √
c
y x
√
b y
e, trivialmente,
x2 + y2 = c.
27
Em todos os casos, a hipotenusa é menor:
x2 < c = x2 + x2
a < c = x 2 + y2
√
c<c
2n2 = (2M)2
2n2 = 4M2
n2 = 2M2
Agora, o lado direito é par, o que significa que o esquerdo também deve ser,
e n = 2N: como n = 2N e M = 2M,
√ m
2=
n
2M
=
2N
M
= .
N
Isso contradiz o que determinamos inicialmente – que m/n seria uma fração
reduzida. O argumento usado nesta demonstração é que para cada m, n,
28
podemos gerar M e N, tais que M < m e n < N, gerando uma quantidade
infinita de números naturais cada vez menores.
Pelo princípio da descida
√ infinita, essa sequência infinita não pode ser ge-
rada, e a hipótese de 2 ser racional deve ser rejeitada.
Ou, da mesma forma, pelo princípio da boa ordem, o conjunto de números
gerados neste processo é subconjunto de N, e deve ter um menor elemento.
Como o processo gera números cada vez menores, e não para, a hipótese
deve ser rejeitada.
A B
1+2=3 3 + 3 = 6,
1+3=4 2 + 3 = 5.
(0, x2 − x1 , . . . , x2n−1 − x1 ),
29
Por consequência, quaisquer dois números xi , xj devem ter a mesma pari-
dade, porque se não for o caso podemos trocar elementos entre os conjuntos
A e B obtendo somas com paridades diferentes.
Mas como x1 = 0 é par, então todos os xi são pares. Se dividirmos todos os
elementos por 2, a sequência manterá a propriedade.
Retomamos o processo, e a sequencia será dividida por 2 repetidamente.
Isso significa que os números serão divisíveis por 2, 22 , 24 , e por 2k para
qualquer k natural, gerando números pares cada vez menores. O único
número divisível por 2k para qualquer k (e que sempre geraria o zero, e
não um natural menor) é o próprio zero, mas como havia algum elemento
diferente de x1 , os xi não poderão jamais ser todos iguais a zero.
Assim, todos os elementos são iguais a xi .
i) todo Xi é subconjunto de X;
34 Algumas vezes chamados de “inteiros racionais”, para distinguí-los de inteiros de outros
30
ii) quando i 6= j, Xi ∩ Xj = ∅;
i) P ⊂ N, I ⊂ N;
iii) P ∪ I = N.
P1 = {0, 1, 2, 22 , 23 , 24 , . . . , 3, 32 , 32 , 34 , . . . , 5, 52 , 53 , 54 , . . .}
ii) Na partição P2 temos 6, 10, 12, 15, e os números com dois primos na
fatoração:
i) xRx (R é reflexiva);
31
A relação ∼, aqui definida, é de equivalência: para todos m, n, o ∈ N,
i) m ∼ m (é reflexiva);
a/b = x/y
b/c = y/z
a/c = x/y
i) A ∼ A;
ii) Se A ∼ B, então B ∼ A;
iii) Se A ∼ B e B ∼ C, então A ∼ C,
32
Podemos agora voltar ao trabalho da definição dos inteiros.
Z = (N × N)/ ∼+
(a, b) ⊕ (p, q) = (a + p, b + q)
(a, b) ⊗ (p, q) = (ap + bq, aq + bp)
33
tomarmos os inteiros positivos apenas, teremos classes de equivalência que
se comportam exatamente como os naturais – e portanto teremos uma outra
construção dos naturais, que depende da primeira, porque afinal de contas,
os pares ordenados contém os naturais-como-conjuntos de von Neumann.
• associatividade da soma;
• comutatividade da soma;
Isto significa que a demonstração deve valer sem mudanças para racionais,
matrizes quadradas, polinômios, funções reais e outras estruturas que te-
nham as propriedades acima36 .
Uma estrutura algébrica é um conjunto adicionado de operações sobre seus
elementos. Definimos estruturas algébricas para generalizar estruturas que
encontramos na Matemática, abstraindo aquilo que elas tem em comum.
36 Na verdade, nossa demonstração tratou de uma única operação, mas continuaremos tra-
balhando com estruturas com duas operações, para simplificar a exposição. No Capítulo 8 de-
finiremos grupo, estrutura algébrica com somente uma operação onde a demonstração acima
também vale.
34
Uma estrutura algébrica que tem as propriedades usadas na demonstração
acima – e outras que nos interessam para tratar de inteiros – é o anel.
35
Teorema 2.39. Sejam R um anel e 0 6= a ∈ R. Suponha que haja um único
b ∈ R tal que aba = a. Então ab = ba = 1, ou seja, a é unidade (tem inverso
multiplicativo igual a b).
Se olharmos apenas para o anel dos inteiros, o Teorema não parece interes-
sante, já que em Z somente o um tem inverso multiplicativo. Mas há outros
anéis, portanto seguimos com a demonstração.
Ou seja, a(b + x)a = a. Como dissemos que b é o único tal que aba = a,
então b + x = b, e x = 0.
Acima presumimos que ax = 0 e chegamos em x = 0 – ou seja, sempre que
ax = 0, teremos x = 0.
Agora, reescrevemos ax com x = (ba − 1):
a(ba − 1) = aba − a
=a−a
=0
36
Não usamos comutatividade em nenhum momento. Isto significa que a de-
monstração deve valer para anéis não comutativos, como os anéis de matri-
zes quadradas!
é um corpo. J
Exemplo 2.43. Embora Z seja um anel, não é um corpo, porque somente 1
tem inverso multiplicativo. J
Exemplo 2.44. O anel de matrizes quadradas de ordem n não é um corpo,
porque nem toda matriz quadrada tem inversa, e também porque a multi-
plicação não é comutativa. J
Exemplo 2.45. (Subanel do anel dado no Exemplo 2.44) O anel de matrizes
da forma
a b
,
b a
onde a, b ∈ Q (ou a, b ∈ R), com determinante não nulo é um corpo porque
além de ser um anel, nele a multiplicação é comutativa; e todas as matrizes
tem inversa (todas são unidade), exceto a matriz zero. J
Exemplo 2.46. Uma função racional é uma função da forma
p(x)
f(x) = ,
q(x)
tenha algo a ver com os trópicos. Geometria Tropical e Números Tropicais tem em seus nomes
uma homenagem a Imre Simon, pesquisador brasileiro que trabalhou nesses tópicos40 .
40 Trabalhou nos tópicos. E nos trópicos.
37
Seja
Rtrop = {−∞} ∪ R.
E defina as operações
a ⊕ b = max(a, b),
a ⊗ b = a + b.
Exercícios
Ex. 1 — Usando os Axiomas de Dedekind-Peano, prove que nenhum nú-
mero natural pode ser seu próprio sucessor.
Ex. 8 — Prove:
(a) ∀n ≥ 1, 3n − 1 é par.
(b) ∀n ≥ 1, n3 + 2n é divisível por 3.
(c) ∀n ≥ 4, n! > 2n .
(d) ∀n ≥ x, ∀x ∈ R, se x > −1, então (1 + x)n ≥ 1 + nx.
38
Pn n2 (n+1)2
(e) ∀n ≥ 1, i=1 i3 = .
Qn 1
4 n+1
(f) ∀n ≥ 2, i=2 1− i2
= 2n .
Ex. 9 — Determine uma forma fechada para a soma dos n primeiros cubos
(13 + 24 + · · · + n3 ), e demonstre sua validade usando indução.
Ex. 12 — Prove que exatamente um dos três números em uma tripla pita-
górica é múltiplo de 5.
39
(i) O conjunto de todas as matrizes quadradas de ordem n, com determi-
nante diferente de zero.
(j) O conjunto de todas as matrizes quadradas de ordem n, com determi-
nante igual a ±1.
(k) O conjunto de todas as matrizes quadradas com elementos inteiros.
(l) R, mas com a operação de soma a ⊕ b = (a + b)/2, onde ⊕ é a soma a
ser usada na estrutura, e + é a soma usual, que usamos apenas para
definir ⊕.
(m) Tendo fixado um conjunto qualquer X, a estrutura que é composta do
conjunto das partes de X, e das operações de diferença simétrica como
adição e de interseção como multiplicação.
40
Capítulo 3
Bases
Roque, Tatiana. História da Matemática: uma visão crítica, desfazendo mitos e len-
das. [S. l.]: Zahar, 2012.
Capítulo 3: Mesopotamia.
2 Não é verdade que os Romanos repetiam apenas 3 vezes o mesmo dígito. Era comum
dedos nas duas mãos, embora haja estudos mostrando que houve outros sistemas na História.
Alguns povos nativos da América do Norte usavam base dois, três, cinco e vinte, por exemplo;
41
A representação de números em bases diferentes é relevante para Enge-
nharias e Ciência da Computação, onde as bases 2 e 16 são extensamente
usadas, mas também pode ser útil em demonstrações de teoremas4 .
3.1 Naturais
Mantendo o sistema posicional, podemos usar qualquer base maior ou igual
a dois5 para representar números naturais. Por exemplo, o número 10011
representa, na base dois, o natural dezenove:
Teorema 3.1. Seja b um número natural maior que um. Então todo número
natural n pode ser descrito unicamente como
n = a0 b0 + a1 b1 + · · · + ak bk ,
Capítulo 1.
O Capítulo 1 do livro de Oystein Ore é uma boa fonte para a história dos sistemas de
numeração.
4 Por exemplo, a unicidade da representação em uma base pode ser usada para provar que
o quociente e o resto da divisão de naturais são únicos. George Andrews faz isto no Capítulo 2
de seu livro.
Andrews, George. Number Theory. New York: Dover, 1994.
A representação em base 13 pode ser usada para provar que a recíproca do Teorema do valor
intermediário não vale (como mencionado neste Capítulo).
A história da representação de números é contada, de forma resumida, por Oystein Ore.
Ore, Oystein. Number Theory and Its History. New York: Dover Publications, 1976.
Capítulo 1.
5 Mas veja o Exercício 21.
6 A resposta é a mesma para inteiros e racionais.
42
Demonstração. Primeiro demonstramos a existência de representação de n
na base b; depois trataremos da unicidade dessa demonstração.
A existência de representação de n na base b é realizada por indução em n.
A base se dá com n = 1,
A hipótese de indução é
z = a0 b0 + a1 b1 + · · · + ak bk , para z = 1, 2, . . . , n − 1.
Como presumimos que b > 1, então b0 < b1 < b2 < · · · , e todo natural
maior que um está entre duas potências de b. Assim, seja n > 1 natural.
Então existe um único q tal que
bq ≤ n < bq+1 .
n = aq bq + r, 0 ≤ r ≤ bq . (3.1)
Observamos que
aq > 0, porque aq bq = n − r > 0.
aq < b, porque
r = d0 b0 + d1 b1 + d2 b2 + . . . + dt bt ,
n = r + aq bq ,
= d0 b0 + d1 b1 + d2 b2 + . . . + dt bt + aq bq ,
7 Por ora presumimos que quociente e resto inteiros existem, e que o resto é menor que n. A
43
todos os casos.
n = f0 + f1 b + f2 b2 + . . . + fg fg , + . . . + fh−1 bh−1 + fh bh ,
w0 + w1 b + w22 + . . . + wh bh = 0. (3.2)
Considere o maior índice s tal que es 6= fs (ou seja, descarte a parte direita
da soma onde os coeficientes são idênticos).
44
Agora verificamos que
bh ≤ wh bh
= w0 + w1 b + · · · + wh−1 bh−1
≤ |w0 | + |w1 b| + · · · + wh−1 bh−1
≤ (b − 1) + (b − 1)b + · · · + (b − 1)bh−1 (por 3.3)
h−1
= Z + Zb + · · · + Zb (seja Z = b − 1)
Z(1 − bh )
= (soma de p.g.!)
1−b
b−1
= (1 − bh )
1−b
= bh − 1,
Por exemplo,
1 1
(2)102 + 0(101 ) + 3(10) + (5)10−1 + (1)10−2 = 200 + 0 + 3 + (5) +
10 100
= 203, 51
20351
=
100
45
Na base dois8 , o número 110, 01 representa
1 1
(1)22 + (1)21 + (0)20 + (0)2−1 + (1)2−2 = 4 + 2 + 0 + (0) +
2 4
= 6, 25
625
=
100
25
=
4
0 ×30 = 0
+1 ×3−1 = 1/3
dois com ponto fixo, porque o uso de ponto flutuante era caro demais (muito lento quando
feito em software, e muito caro para adicionar ao hardware). Hoje todas as CPUs trabalham
nativamente com representação em ponto flutuante, seguindo um padrão.
46
valor intermediário9 . Ela foi inventada com este propósito10 por Conway11 .
A função base 13 não é contínua. Mas se f(a) < f(b), então para todo x
entre f(a) e f(b), sempre haverá um valor c tal que f(c) = x. Na definição da
função fica claro que é usada a representação de reais em base 13. Embora
não tenhamos abordado mudança de base para números reais, deve ficar
evidente que a representação destes em diferentes bases se dá da mesma
maneira que a representação de racionais, exceto que os irracionais tem
expansão infinita12 .
f(x) = d1 d2 . . . dn e1 e2 . . . ,
Bd1 d2 . . . dn Ce1 e2 . . . ,
f(x) = −d1 d2 . . . dn e1 e2 . . . ,
Grag Oman.
Oman, Greg. The Converse of the Intermediate Value Theorem: From Conway to Cantor to
Cosets and Beyond. Missouri Journal of Mathematical Sciences, v. 26, n. 2, p. 134–150,
2014.
11 John Conway (1937-2020), Britânico.
12 Uma construção dos reais é dada no Capítulo 15.
47
As demonstrações de que esta função de fato é um contraexemplo para a
recíproca do Teorema do valor intermediário são pedidas nos Exercícios 39
e 40.
Exercícios
Ex. 19 — Escreva o número 543 na base 4 e o número 111 na base 5.
dk dk−1 . . . d2 d1 d0 .
Ex. 26 — Que outros números, além de 7, não tem inverso com represen-
tação finita na base 60?
Ex. 27 — De maneira geral, que números não tem inverso com represen-
tação finita na base b?
Ex. 28 — Prove que qualquer número palíndromo na base dez, com quan-
tidade par de dígitos, é divisível por onze.
48
Ex. 30 — Demonstre o Teorema 3.2.
(a) Escreva os números −3, −8, +8, +11 em representação ternária balan-
ceada.
49
Ex. 34 — Que números são representáveis, usando o sistema posicional,
por uma base racional (e não inteira) m/n, com m, n ∈ Z? Por exemplo, se
a base é 2/3, números seriam da forma
2 3
2 2 2
a0 + a1 + a2 + a3 + ···
3 3 3
11111111111111111111111111111111111
| {z }
35 uns
é o palíndromo
Isso pode ser generalizado para qualquer base? Se não for verdade, mostre
contraexemplo. Se for verdade, formalize e demonstre.
50
dele. O número
51
Newcomb-Benford13
1
Pr(d) = log10 1+ ,
d
ou seja,
Pr(1) ≈ 0.301
Pr(2) ≈ 0.176
Pr(3) ≈ 0.125
Pr(4) ≈ 0.097
..
.
logaritmos tinham páginas iniciais muito mais desgastadas do que as finais, e que portanto os
números iniciando com 1 eram mais frequentemente buscados – e portanto ocorriam mais fre-
quentemente. Newcomb chegou a determinar as probabilidades para os primeiros e segundos
dígitos de números, e terminou seu artigo mencionando que
É curioso observar que esta lei nos permitiria decidir se uma grande coleção de
resultados numéricos independentes foi composta por números naturais ou loga-
ritmos.
No original,
It is curious to remark that this law would enable us to decide whether a large
collection of independent numerical results were composed of natural numbers or
logarithms.
Newcomb, Simon. Note on the Frequency of Use of the Different Digits in Natural Numbers.
American Journal of Mathematics, v. 4, n. 1, p. 39–40, 1881.
Este fenômeno ficou conhecido como “Lei de Benford” porque observações semelhantes foram
feitas em 1938 por Benford15 , com números de diferentes origens.
Benford, Frank. The Law of Anomalous Numbers. Proceedings of the American Philo-
sophical Society, v. 78, n. 4, p. 551–572, 1938.
16 isto é relevante em detecção de fraudes. Um conjunto de dados respeitar a Lei de Benford
Gueron, Eduardo; Pellegrini, Jerônimo. Application of Benford – Newcomb law with base
change to electoral fraud detection. v. 607, 2022. Preprint disponível em https : / / arxiv .
org/abs/2207.05524v2.
Uma análise das eleições brasileiras desde o início do uso da urna eletrônica mostra que as
eleições passaram a respeitar Benford em todas as bases.
52
Ex. 39 — Prove o Teorema 3.5.
53
54
Capítulo 4
Divisibilidade
4.1 Divisão
A noção de divisibilidade é fundamental em Teoria dos Números.
Da definição concluímos que zero divide zero (0 | 0), porque existem infinitos
c tal que 0c = 0. No entanto, justamente por haver infinitas possibilidades
para c, não definimos a operação de divisão de zero por zero. Isto pode
ficar mais claro se não lermos “a | b” como “a divide b”, mas como “a tem
múltiplo b”.
Como exemplo em Z, 3 | 15 porque 3(5) = 15; já 4 - 10, porque não existe
inteiro k tal que 4k = 10.
Para um exemplo no anel R[x] (polinômios na variável x com coeficientes em
R), temos (x − 1) | (x3 − x2 ), porque
(x − 1)x2 = x3 − x2 .
55
Em Z, 4 | 20, porque 4(5) = 20.
O seguinte Teorema trata de alguns fatos básicos a respeito de divisibili-
dade, e é deixado como exercício.
Teorema 4.2. Para todos a, b, c:
(i) Se a | b então a | bc.
xb + yc = x(ma) + y(na)
xb + yc = a(xm + yn)
a | (xb + yc)
56
e portanto (a − b) | (an+1 − bn+1 ).
a = qb + r, a = q 00 b + r 00 .
r = a − qb, r 00 = a − q 00 b.
57
mas o único múltiplo de b que poderia ser r 00 − r é zero (ou seja, o único
K ∈ Z possível é zero). Logo, r 00 = r e q 00 = q.
Tendo provado que sempre é possível dividir dois inteiros (ou dois elementos
de um anel comutativo), podemos definir a operação de divisão.
(ii) d | a, d | b;
(iii) se k | a e k | b, então k | d.
Exemplo 4.9. Em Z, temos mdc (28, 12) = 4, porque 4 | 28, 4 | 12, mas os
únicos outros números que dividem 28 e 12 são 1 e 2 – e ambos dividem
4. J
Note que o final da demonstração não é válido para qualquer anel: em R[x],
considere os polinômios x e 2x. Temos x | 2x, também 2x | x, e x 6= 2x. Neste
caso, não valerá a unicidade do MDC.
Nesta demonstração excluímos a possibilidade de a = b = 0. O Exercício 55
pede para elaborar o motivo dessa restrição.
58
O próximo resultado relevante a examinar é o Lema de Bézout1 . Definimos,
para isso, o conceito de combinação linear inteira 2 .
Lema 4.12 (de Bézout). Para todos a, b ∈ Z, mdc (a, b) é combinação linear
inteira de a e b – ou seja, existem x, y ∈ Z tais que mdc (a, b) = xa + yb.
r = b − qz
= b − q(xa + yb)
= b − qxa − qyb
= (1 − qy)b − (qx)a
∈ S.
1 Na verdade Bézout provou a afirmação para polinômios.
Bézout, Etienne. Théorie Générale des Équations Algébriques. [S. l.], 1779. Disponível
em [Link]
Quem demonstrou este lema para números inteiros foi Claude Gaspar Bachet, em 1612.
Bachet, Claude Gaspar (Sr de Meziriac). Problèmes plaisans et deléctables, qui se font
par les nombres. [S. l.], 1612. Disponível em https : / / archive . org / details / bub _ gb _
Zy0PAAAAQAAJ.
Na página 129,
Sendo dados dois números primos entre eles, encontre um múltiplo de qual
deles você deseja, que supere o outro pela unidade, ou algum múltiplo do outro.
O original de Bachet é:
Deux nombres premiers entre eux estant donnez, trouver un multiple daquel
d’iceux qu’on voudra, qui surpasse l’autre de l’unité, ou quelque multiple de
l’autre.
Isto equivale a resolver a = by + 1, ou a − by = 1, para a e b coprimos.
Em 1612 Bachet já listava “teoremas” e “demonstrações”. O livro contém uma lista de teore-
mas, seguida de uma lista de problemas, que são expostos à maneira da época – por exemplo,
PROBLEMA I: Adivinhar o número que alguém tiver pensado.
O original é:
PROBLEME I: Deviner le nombre que quelcun aura pensé.
Aqui, por exemplo, Bachet propõe uma brincadeira simples, onde pede que alguém pense em
um número e faça operações. A partir do resultado, pode-se determinar o número original. Na
segunda edição do livro, Bachet demonstra o teorema.
2 Em um espaço vetorial, a combinação linear au + bv de vetores resulta em outro vetor w.
59
Mas como r ∈ S, e r < z, temos uma contradição, porque havíamos tomado
z como o menor elemento positivo de S. Desta forma negamos nossa su-
posição e concluímos que z | b. O argumento que fizemos para b pode ser
repetido para a, obtendo z | a.
Agora temos um elemento (z) que divide tanto a como b, e que é não nega-
tivo. Falta mostrar que se k | a e k | b, então k | z, o que segue imediata-
mente porque z = xa + yb.
(−23)93 + (+7)306 = 3,
Corolário 4.14. mdc (a, b) é o menor valor positivo dentre todas as combi-
nações lineares inteiras de a e b:
60
portanto
Demonstração. Do enunciado,
mdc (b, c) = 1
a mdc (b, c) = a
mdc (ab, ac) = a (Teorema 4.16)
O enunciado determina que c | ab; temos também que c | ac, pela definição
de divisibilidade; logo, c é divisor de ab e ac. Mas mdc (ab, ac) é a, e pela
definição de MDC, todos os outros divisores de ab dividem a. Logo, c | a.
Euclid. The Elements. [S. l.]: Green Lion Press, 2002. Edição bilíngue Inglês/Grego.
61
portanto d só pode ser 1 ou p. Se d = p, então teríamos, pela definição
de MDC, d | a, ou seja, p | a – mas já presumimos que p - a, portanto
d = mdc (a, p) = 1.
Assim, tendo presumido que p - a, pelo Teorema 4.18, p | b.
Lema 4.21. Se mdc (a, b) = 1, então mdc (a, bc) = mdc (a, c).
aX + bY = 1
aXc + bYc = c
62
4.3 Algoritmo de Euclides para cálculo do MDC
Passamos agora ao algoritmo de Euclides, usado para calcular o MDC de
dois (ou mais) números5 .
O Lema 4.22 motiva diretamente a construção do algoritmo de Euclides (a
demonstração, simples e quase a mesma do Teorema 4.23 (algoritmo de
Euclides), é pedida no Exercício 80).
Note que usamos o valor absoluto de b, que pode não fazer sentido em
qualquer anel (mas é definido em Z).
d = mdc (b, r)
temos
(I) d | b e d | r;
5 Euclides apresentou o algoritmo na proposição 2 do livro sete de sua compilação (o livro
Elementos ) mas, como se deve esperar, há evidências de que o algoritmo era conhecido muito
antes de Euclides. A proposição inicia com:
Dados dois números não primos entre si, encontrar sua máxima medida.
O original é:
Δῦο ἀριθμῶ δοθέντων μὴ πρώτων πρὸς ὰλλήλους τὸ μέγιστον αὺτῶν αὐτῶν χοινὸν
μέτρον εὑρεῖν.
(Dýo arithmó dothénton mí próton prós állílous tó mégiston aftón choinón métron
evreín.)
Euclides formulou suas proposições em termos de medidas, tratando os números como
medidas em geometria. Um número “mede” outro se é divisor daquele. A “máxima medida”
dos dois números é o maior número que “mede” (em nossa linguagem, “divide”) os dois – o
MDC.
A proposição seguinte no livro (a de número 3) trata do MDC de três números.
Euclid. The Elements. [S. l.]: Green Lion Press, 2002. Edição bilíngue Inglês/Grego.
63
(II) se k | b, k | r, então k | d.
Agora analisamos:
k | (qb + r)
kS = qb + r (definição de |)
kS = q(kT ) + r (k | b)
k(S − qkT ) = r
k|r (definição de |)
Os itens (i) e (ii) acima mostram que mdc (b, r) será igual a mdc (a, b).
Há outro algoritmo para cálculo do MDC, que não usa a operação de divisão.
64
Exemplo 4.27. Calculamos o MDC de 624 e 162 usando o algoritmo com
subtrações.
O Lema 4.12 (Lema de Bézout6 ) afirma que se mdc (a, b) = d, então existem
inteiros x e y tais que ax + by = d. Uma modificação no algoritmo de
Euclides para cálculo do MDC pode identificar os coeficientes x e y, como
vemos a seguir.
r0 = a,
r1 = b,
65
calculamos
r 0 = q 1 r1 + r2
r 1 = q 2 r2 + r3
r 2 = q 3 r3 + r4
..
.
rn−2 = qn−1 rn−1 + rn
rn−1 = qn rn + 0.
108 = 3(33) + 9
33 = 3(9) + 6
9 = 1(6) + 3
6 = 2(3) + 0
3 = 9 − 1(6)
3 = 9 − 1(6)
= 108 − 3(33) − 1(6)
= 108 − 3(33) − 1[33 − 3(9)]
= 108 − 3(33) − 33 + 3(9)
= 108 − 4(33) + 3[108 − 3(33)]
= 4(108) − 13(33).
4(108) − 13(33) = 3.
66
que sempre podemos escrever o i-ésimo resto, ri , em função de valores
obtidos anterioremente.
ri+1 = ri−1 − qi ri
= (axi−1 + byi−1 ) − qi (axi + bxi )
= axi−1 − qaxi + byi−1 − qbyi
= a(xi−1 − qi xi ) + b(yi−1 − qyi )
= axi+1 + byi+1
r0 = a = 1a + 0b (x0 = 1, y0 = 0)
r1 = b = 0a + 1b (x1 = 0, y1 = 1)
6(48) − 11(26) = 2.
Este cálculo pode ser simplificado em uma tabela como a próxima, que mos-
tra o índice das cinco iterações, i, e os valores ri , qi , xi e yi .
67
−→
i 0 1 2 3 4 5
ri 48 26 22 4 2
qi 1 1 5 2
xi 1 0 1 −1 6
yi 0 1 −1 2 −11
Excluímos o zero porque de outra forma, ele seria o mínimo múltiplo comum
de todos os pares de números: 0 sempre é divisível por a e b, e é o menor
natural.
68
O Teorema 4.31 determina uma relação importante entre o MDC e o MMC
de dois números. Sua demonstração é pedida no Exercício 73.
8 O primeiro nome é Leonardo (ou “Lionardo”, na grafia da época). Outros nomes aparecem,
mas não há certeza sobre a natureza ou origem deles (Leonardo Bigollo, Leonardo Pisano,
Leonardo Bonacci, ou ainda, “Fibonacci”, possivelmente significando “filho de Bonacci”). Ë
mais comum a referencia a “Leonardo de Pisa”, ou “Leonardo Pisano”.
9 O fato da descrição usar coelhos e presumir que nunca morrem garante a denominação
alternativa “coelhos imortais de Fibonacci”. Este livro parece ter sido o primeiro a introduzir
a notação posicional com base dez e os numerais arábicos na Europa. A obra foi publicada
inicialmente em 1202,em Latim, mas não há cópia escrita dessa edição. Uma nova edição, de
1227 traz, no Capítulo doze, o problema:
Um certo homem tinha um casal de coelhos juntos em un certo lugar fechado,
e queremos saber quantos são criados desse casal em um ano quando é da natu-
reza deles em um mês gerar um novo casal, e no segundo mês esses que nasce-
ram gerarem outros também. (...)
69
números dando as quantidades de casais em cada mês é a chamada sequên-
cia de Fibonacci, embora tenha sido conhecida na Índia, antes de Fibonacci
nascer10
u1 = 1,
u2 = 1,
un = un−1 + un−2 .
Números de Fibonacci podem ser descritos por uma forma fechada, usando
a razão áurea, através da fórmula de Euler-Binet.
800 na Índia por Virahāṅka (िवरहाङ् क), além de outros, antes do nascimento de Fibonacci.
Singh, Paramand. The So-called Fibonacci Numbers in Ancient and Medieval India. Histo-
ria Mathematica, v. 12, n. 3, p. 229–244, 1985.
11 Alguns autores definem de forma alternativa, mas equivalente: u 0 = 0; u 1 = 1; u n =
un−1 + un−2 .
70
A segunda raiz da equação é negativa, e denotada φ̂:
√
1− 5
φ̂ = .
2
1
φ̂ = 1 − φ = − .
φ
Então
φn − φ̂n
un = √ .
5
φ0 − φ̂0 1−1
√ = √ = u0
5 5
φ1 − φ̂1 φ − φ̂
√ = √
5 5
√ √
1+ 5
2− 1− 5
= √ 2
5
= 1 = u1
φi − φ̂i
ui = √ , ou
5
√
ui 5 = φi − φ̂i .
φ2 = 1 + φ,
φ̂2 = 1 + φ̂.
71
Agora verificamos que
finalizando a demonstração.
72
um un+1 + um−1 un = um u1+1 + um−1 u1
= um (1) + um−1 (1) (u1 = 1, u2 = 1)
= um + um−1
= um+1
= um+n .
73
Então
Se, neste processo, olharmos apenas para os índices (que seria como subs-
tituir um → m, un → n, uq → q, ur → r), perceberemos que esses índices
se comportam como em iterações do algoritmo de Euclides, que eventual-
mente terminará com o último resto igual ao MDC dos dois números: haverá
um passo em que
mdc (ua , ub ) = mdc (ud , u0 ),
mas u0 = 0 (pela definição de números de Fibonacci), e
i) ud | um , ud | un
ii) se ue | um , e | un , então ue | ud .
e portanto
e | umx−1 uny + umx uny+1
e
e | umx+ny .
74
exclusivamente da representação de inteiros como soma de dois, três ou
quatro quadrados).
a = qb + r.
a ≥ uk+1 ,
b ≥ uk .
r0 = a ≥ r1 = b ≥ r2 ≥ . . . ≥ rk ≥ 1,
13 A “Complexidade de tempo” do algoritmo é uma medida de crescimento assintótico da
75
com
ri−2 = qi ri−1 + ri , qi ≥ 1
par todo i > 1.
Usando o Lema 4.47 e a fórmula de Euler-Binet (Teorema 4.39) é possível
demonstrar o Teorema 4.48, que determina a complexidade do algoritmo de
Euclides.
Im
2
z
0 1 2 Re
76
logo
= rei(θ+π/2) .
Nada dissemos sobre o efeito sobre a norma, porque não usamos norma
euclideana, como será esclarecido adiante.
Usaremos, a partir de agora, inteiros Gaussianos 14 .
Im Im
−1 0 +1 Re −1 0 +1 Re
=⇒
teorema e a demonstração seriam mais facilmente descritos usando números do tipo “número
complexo inteiro” (numerum integrum complexum é o termo usado).
Gauss, Johannes Carl Friedrich. Theoria residuorum biquadraticorum. Commentatio se-
cunda. Comm. Soc. Reg. Sci. Göttingen, v. 7, p. 89–148, 1831.
77
A noção de divisibilidade em Z[i] é a mesma para qualquer anel – podemos
manter a definição que já temos. Daremos, no entanto, alguns exemplos.
15 2
√ Usualmente, para vetores em R e para números complexos, define-se a norma como
a2 + b2 , para que o valor da norma coincida com a distância da origem até o ponto asso-
ciado ao vetor. No entanto, em Teoria de Números é mais importante que a norma seja um
valor inteiro – daí a ausência da raiz quadrada.
78
Exemplo 4.54. Sejam z = −3 + 4i e w = 2 − 8i. Então zw = 26 + 32i.
(1)(1) = 1,
(−1)(−1) = 1,
(−i)(i) = 1.
16 Para outros valores, a norma não é a distância até a origem, porque abrimos mão da norma
Euclideana!
79
Então
(1)(2 − 3i) = 2 − 3i
(−1)(2 − 3i) = −2 + 3i
(i)(2 − 3i) = 3 + 2i
(−i)(2 − 3i) = −3 − 2i
Demonstração. (informal)
Os múltiplos do inteiro gaussiano β formam um reticulado, que podemos vi-
sualizar como infinitos retângulos. Se β = a + bi, os lados destes retângulos
tem comprimento a e b. A figura a seguir mostra os múltiplos de um inteiro
Gaussiano β (2 + 3i).
80
O inteiro Gaussiano α tem coordenadas inteiras, mas não necessariamente
no reticulado gerado por β. Identificamos no reticulado de β um ponto mais
próximo de α, e como este ponto está no reticulado de β, ele representa um
ponto γβ. A figura a seguir ilustra a divisão de 1 + 2i por 2 + 3i.
81
e y ≤ b/2, logo
N(ρ) = x2 + y2
a 2 b 2
≤ +
2 2
a2 b2
= +
4 4
N(β)
= .
4
Corolário 4.59. Podemos realizar algo semelhante a divisão em Z[i] de
maneira simples usando aritmética racional: para dividir α = a + bi por
β = c + di, calculamos os inteiros mais próximos de a/c e d/b:
a + bi ÷ c + di = q(c + di) + r
jam b
q= +
c d
r = α − qβ,
O que fizemos com os inteiros Gaussianos foi usar uma norma que nos per-
mitiu usar o algoritmo de Euclides. O mesmo algoritmo funcionará em qual-
quer anel que, mesmo não sendo totalmente ordenado, admita uma função
λ com papel semelhante a esta norma, para que possamos definir a divisão
como a = qb + r, com λ(r) menor que λ(b). Isto é a definição de um do-
mínio Euclideano – que é, informalmente, um anel onde é possível usar o
algoritmo de Euclides.
82
Além dos inteiros Gaussianos, o anel R[x] pode ser tratado como Domínio
Euclideano, se usarmos uma norma apropriada.
83
É interessante que uma tentativa de usar “tanto o grau do polinômio como
o coeficiente líder” levaria a uma situação semelhante à de C, onde essen-
cialmente estaríamos tentando obter ordem total para o produto cartesiano
de dois conjuntos infinitos ordenados (R × R para complexos, Z × R para
R[x], porque o grau é inteiro e o coeficiente líder é real) – estas relações de
ordem, no entanto, não existem.
Retomando o MDC para inteiros, observamos que temos na definição uma
exigência de que o MDC de dois números seja positivo. Esta restrição ga-
rante a unicidade do MDC – de outra forma, teríamos mdc (8, 12) = ±4, já
que ±4 | 8, ±4 | 12, e se houver algum c que divida 8 e 12, (por exemplo, 2)
então c | ±4.
Exercícios
Ex. 41 — Prove que, quando restrita a inteiros não-negativos, “divide” ( | )
é uma relação de ordem. Explique o que acontece se incluirmos os negati-
vos.
Ex. 42 — Mostre que para qualquer inteiro não negativo n, o número n(2n+
1)(n + 1)/6 é inteiro.
(a) 3 | (10n − 7n )
(b) 9 | (10n − 1)
(c) 8 | (32n + 7)
Ex. 48 — Prove que todo racional pode ser escrito como soma de frações
onde o numerador é um.
Ex. 49 — Mostre que todo número natural tem algum múltiplo positivo
que, quando escrito na base dez, tem somente dígitos um e zero.
84
Ex. 50 — O Exemplo 2.4518 apresentou o corpo das matrizes quadradas da
forma
a b
,
b a
com a, b ∈ Q (ou a, b ∈ R), com determinante não nulo. (É um corpo porque
além de ser um anel, nele a multiplicação é comutativa e toda matriz tem
inversa). Prove que com a, b ∈ Z a estrutura já não é mais um corpo.
Ex. 52 — Calcule mdc (294, 306), mdc (96, 36) e mdc (45, 67).
Ex. 53 — Determine todos os 152 ≥ n ∈ N tais que mdc (n, 152) = 8. Expli-
que seu método.
Ex. 54 — Sabendo que b|(a − 1), calcule mdc ab-b2 , a2 -2ab + b2 + a-b .
85
Ex. 61 — Prove o Teorema 4.16. Dica: use o Corolário 4.14.
φn − φ̂n
un = √
5
√ √
(1 + 5)n − (1 − 5)n
= √ .
2n 5
86
Ex. 75 — Prove que n3 − n é divisível por 6 para todo inteiro n.
•a | b
•mdc (a, b) = |a|
•mmc(a, b) = |b|
mmc(a, b) = 360
mdc (a, b) = 30
87
Ex. 90 — Prove que todo corpo é um domínio Euclideano.
∞
X ∞
X ∞
X
! ! !
i i k
ai x · bi x = ck x ,
i=0 i=0 k=0
onde X
ck = ai bi .
0<i,j<k
i+j=k
88
Capítulo 5
Primos
Euclid. The Elements. [S. l.]: Green Lion Press, 2002. Edição bilíngue Inglês/Grego.
89
5.1 Fatoração Única em Z
Esta seção trata do Teorema Fundamental da Aritmética, que afirma a exis-
tência da fatoração em primos para todos os inteiros. Este é um fato conhe-
cido pelo menos desde a antiga Grécia, mas o enunciado da unicidade só
foi proposto2 por Gauss, no Disquisitiones, séculos depois de ter sido usado
como uma afirmação “óbvia”.
Lema 5.3. Todo inteiro diferente de zero pode ser escrito como produto de
primos e uma unidade (+1 ou −1).
2 Euclides conhecia o conceito de fatoração, mas não enunciou o teorma como o conhecemos
A existência de uma demonstração anterior à de Gauss foi por muito tempo ignorada. Por
exemplo, Jay Goldman expõe a história do Teorema mencionando Fermat, Legendre e outros
matemáticos europeus, sem menção a al-Fārisī.
Goldman, Jay R. The Queen of Mathematics: A Historically Motivated Guide to Num-
ber Theory. Natick, MA: A. K. Peters, 1998.
Página 5. Goldman observa, interessantemente, que a unicidade era aparentemente tida como
óbvia para todos os antecessores de Gauss (que inclusive a usaram, sem enunciá-la como lema
ou teorema), e por isso a demonstração não havia sido feita (e como mostrado por Agargün
e Fletcher, al-Fārisī também não a produziu). Tudo indica que o primeiro a reconhecer a
importância da unicidade foi, de fato, Gauss.
90
Damos duas demonstrações, uma usando o princípio da boa ordem, e uma
por indução (forte).
Seja n o menor inteiro positivo que não seja primo, mas que não possa ser
escrito como produto de primos (é um subconjunto de N, e pelo princípio
da boa ordem este elemento existe). Então, como n não é primo, n = ab,
e necessariamente 0 < a, b < n. Mas, como n é o menor inteiro (a boa
ordem é usada aqui!) positivo que não pode ser decomposto em primos,
então a e b podem. Mas se a e b podem ser decompostos em primos,
n = ab também pode, porque o produto das fatorações de a e de b é uma
fatoração de n (ainda não provamos unicidade) – o que contradiz o que
presumimos no início da demonstração.
Demonstração. Que existe uma fatoração o Lema 5.3 garante. Falta mos-
trar que é única. Suponha, portanto, que haja mais de uma fatoração para
91
um inteiro n. Retiramos das fatorações os elementos primos comuns às
duas, e temos
M = p1 p2 . . . pk = q1 q2 . . . qr ,
onde não há qualquer elemento comum nos dois lados. Mas pelo Lema de
Euclides (Lema 4.20), como p1 | M, teríamos p1 | q1 q2 . . . qr , e um dos qi
teria que ser igual a p1 , portanto temos uma contradição.
396000 = 25 32 53 11,
92
que reescrevemos
Teorema 5.10. Uma fração irredutível m/n (com n > 0) tem expansão
finita em base b se existe k ∈ N tal que n | bk .
Se, no entanto, não houver k natural tal que n | bk , então a expansão de
m/n será infinita e periódica.
93
Como (a − 1) | ab − 1 e ab − 1 é primo, então necessariamente a − 1 = 1, e
a = 2.
Agora suponha que b seja composto; b = cd. Então 2cd = (2c )d , e
2b − 1 = (2c )d − 1
h i
= (2c − 1) (2c )d−1 + · · · + 1 ,
e (2c −1) dividirá 2b −1, que é primo – portanto b não pode ser composto.
3 Marin Mersenne, frade da Ordem dos Mínimos. Mersenne começou a investigar estes
números devido a conexão com números perfeitos. Em 1644, compilou uma tabela de primos
da forma 2p − 1, mas a lista de Mersenne continha erros (listava números que Mersenne
pensava serem primos, mas são compostos; também omitia alguns que são primos). A lista
está em seu livro:
Mersenne, Marini. Cogitata Physica-Mathematica. [S. l.], 1644. [Link]
details/fmarinimersennic00mers.
4 Números perfeitos foram descritos no livro sete dos Elementos, de Euclides:
Euclid. The Elements. [S. l.]: Green Lion Press, 2002. Edição bilíngue Inglês/Grego.
94
potência de dois e os outros divisores próprios:
A = {1, 2, 22 , . . . , 2p−1 },
B = {q, 2q, 22 q, . . . , 2p−2 q}.
A soma de B é
X
= q + 2q + 22 q + · · · + 2p−2 q
b∈B
= q(1 + 22 + · · · + 2p−2 )
p−1
2 −1
=q
2−1
= q(2p−1 − 1).
q + q(2p−1 − 1) = q + q(2p−1 ) − q
= q(2p−1 ),
e r é perfeito.
95
Já mostramos no Exemplo 5.14 que 6 e 28 são perfeitos. Os divisores de 8128
são
1, 2, 4, 8, 16, 32, 64, 127, 254, 508, 1016, 2032, 4064.
A soma destes é
com x = ac , y = −1 e n = q, temos
h i
(ac )q − (−1)q = (ac − (−1)q ) (ac )q−1 + · · · + (−1)q−1
h i
(ac )q − (−1)q = (ac + 1) (ac )q−1 + · · · + (−1)q−1 (q ímpar)
h i
acq + 1 = (ac + 1) (ac )q−1 + · · · + (−1)q−1 (q ímpar)
h i
an + 1 = (ac + 1) (ac )q−1 + · · · + (−1)q−1 ,
641 = 24 + 54
= 5 · 27 + 1,
96
portanto 24 = 641 − 54 . Agora, F5 = 232 + 1. e
232 = 228 · 24
= 228 · (641 − 54 )
= 228 641 − 228 54
= 228 641 − (27 5)4
= 228 641 − (641 − 1)4
= 641Q − 1,
e 641 | 232 + 1.
5
Tendo um fator, dividimos F5 por ele e obtemos F5 = 22 + 1 = 4294967297 =
641 · 6700417 (interessantemente, o outro fator, 6700417, é primo)5 .
n
Definição 5.18 (Números de Fermat). Um número natural da forma 22 +1,
com n ∈ N, é um número de Fermat e denotado Fn . Quando Fn é primo, é
chamado de primo de Fermat.
F0 · · · Fn + 2 = F0 · · · Fn−1 Fn + 2
= (Fn − 2) · Fn + 2 (hipótese de indução)
2n 2n
= (2 − 1)(2 + 1) + 2
2n+1
= (2 − 1) + 2
= Fn+1 .
97
Demonstração. Presuma m < n, e seja d um divisor comum de Fm e Fn .
Se d | Fm , pelo Teorema 5.19,
d | F0 · · · Fn−1 + 2.
Note que, como m < n, Fm está no produto, por isso a afrimação vale.
Mas se d divide Fm , então temos
d | F0 · · · d · · · Fn−1 + 2
d | (F0 · · · Fn−1 )d + 2
d | 2. (subtraímos múltiplo de d)
É interessante que o que Euclides fez foi enunciar e demonstrar um passo de indução. Não
provou uma base, porque não via sentido nisso. Usamos cuidado ao ler o enunciado, no
98
e leva a concluir que (usando o Teorema Fundamental da Aritmética) deve
haver mais um novo primo na fatoração desse outro número (mas não pode-
mos concluir que s é primo – somente que tem um fator primo que não está
no conjunto!).
A demonstração de Hermite tem semelhanças com a de Euclides.
Assim, todo inteiro positivo n seria menor ou igual que 22k , e os naturais
seriam finitos.
entanto: a demonstração garante que existe algum conjunto, maior do que qualquer conjunto
finito proposto. Isso nos garante que existe um conjunto infinito de primos (e nada é dito sobre
este conjunto infinito ser ou não ser o conjunto de todos os primos). Euclides não falava de
conjuntos infinitos.
99
Demonstração. Considere a sequência de inteiros consecutivos (com n > 1):
(n + 1)! + 2,
(n + 1)! + 3,
..
.
(n + 1)! + n,
(n + 1)! + (n + 1),
k (n + 1)! + k
2 122
3 123
4 124
5 125
Todos são compostos (2 | 122, 3 | 123, 4 | 124, 5 | 125). Observe que 120, 121
(antecessores da sequencia) e 126 (sucessor) também são compostos, em-
bora isto não fosse garantido pelo enunciado do Teorema.
Terminamos esta seção com um Teorema a respeito da série 1/p (soma dos
recíprocos dos primos).
diverge.
100
onde pi é p i-ésimo primo.
Mx = {n ≤ x : se p > k, pk - n}
dos números menores ou iguais a x, que não são divisíveis por primos mai-
ores que pk .
n = m2 r,
Ni,x = {n ≤ x : ∃j > k, pj | n} .
Então [
{1, 2, . . . , x} \ Mx = Ni,x ,
i>k
e
x
|Ni,x | ≤ .
pi
X X x
x − |Mx | ≤ |Ni,x | <
pi
i>k i>k
X x
x − |Mx | <
pi
i>k
X 1
x − |Mx | < x
pi
i>k
1
x − |Mx | < x (da nossa hipótese)
2
x
x < + |Mx |
2
x
< |Mx |.
2
101
Então, das duas desigualdades que obtivemos,
x √
< |Mx | ≤ 2k x
2
x √
< 2k x,
2
mas para x > 22k+2 ,
x
x > 22k+2 > 2xk+1 .
2
P 1
Como chegamos a uma contradição, concluímos que a série pi diverge.
5.4 4k + 1, 4k + 3
O único inteiro primo par é o número dois, portanto todos os outros primos,
quando divididos por quatro, devem resultar em resto um ou três. Dizemos
que estes primos são da forma 4n + 1 ou da forma 4n + 3.
Inicialmente observamos que os números (não apenas primos) da forma 4n+
1 são fechados para multiplicação:
q = 4(p1 p2 . . . pr ) + 3.
3 | 4(p1 p2 . . . pr ),
102
o que não é possível, porque 3 foi explicitamente excluído do produto, e o
que temos são 4 = 22 e os outros pi . Já temos 3 - q. Verificamos os outros
primos da forma 4k + 3 (ou seja, os pi ). Seja pj um primo da forma 4k + 3
que divide q: pj 6= 3 e pj | q. Então
pj | 4p1 p2 . . . pr + 3
pj | 4p1 p2 . . . pr + 3
pj | 4p1 p2 . . . pj . . . pr + 3
h i
pj 4p1 p2 . . . pi−1 pi+1 . . . pr pj + 3
pj | 3,
103
A demonstração dada é por contradição, e seria interessante se houvesse
outra, construtiva, de onde pudéssemos extrair um método para construir
primos da forma 4k + 1.
Há uma demonstração construtiva pra o Teorema 5.27, publicada em 1992
por Neville Robbins. Esta demonstração, no entanto, depende do Lema 5.28,
que apresentamos por ora sem demonstração (que será dada no Capítulo 10).
i) sn > 1 quando n ≥ 1;
Então cada sn tem um fator primo da forma 4k+1, que não está na fatoração
dos outros elementos sj da sequência.
104
Repetimos agora o enunciado do Teorema 5.27, e passamos às duas de-
monstrações.
Ambas constróem a sequência sn = a2n + b2n , com mdc (a, b) = 1 e a e b
tendo paridades diferentes. A demonstração usando números de Fibonacci,
também usamos o Lema 5.30 (Exercício 102).
p + 1 p-1
mdc , = 1.
2 2
i) Fn > 1;
105
Agora, embora os qi sejam primos, precisamos garantir que os dois números
elevados ao quadrado em 5.2 são co-primos.
Como pelo Lema 5.30 mdc ((qn -1)/2, (qn + 1)/2)) = 1, então por (II),
mdc
u qn -1 , u qn + 1 = 1.
(5.3)
2 2
iii) mdc (uqm , uqn ) = 1, porque os qi são co-primos, e mdc (um , un ) = umdc(m,n)
(Teorema 4.447 ).
Pelo Lema 5.29, a sequência (qn ) nos dá infinitos primos da forma 4k+1.
x2 + x = x(x + 1)
7 Teorema 4.44: mdc (um , un ) = umdc(m,n) .
106
e portanto x | x2 + x, e (x + 1) | x2 + x.
Já x2 + 1 é irredutível em R[x], no anel de polinômios com coeficientes reais,
porque seus divisores são somente os polinômios constantes e os múltiplos
deste mesmo polinômio.
A redutibilidade de um polinômio depende do anel onde trabalhamos. Po-
demos deixar de lado o anel dos polinômios com coeficientes reais e passar
para o anel dos polinômios com coeficientes inteiros8 . Um polinômio que
é fatorável em R[x] pode ser irredutível em Z[x]. Por exemplo, o polinômio
x2 +x−1 tem duas raízes racionais, logo é fatorável na forma (x−r1 )(x−r2 ):
√ ! √ !
2 5−1 5−1
x +x−1= x− x+ .
2 2
(1 − i)(2 + i) = 3 − i.
A seguir iniciamos com uma demonstração, para R[x], de que todos elemen-
tos podem ser escritos como produto de irredutíveis; em seguida generali-
zamos o enunciado para domínios Euclideanos.
Lema 5.33. Todo polinômio diferente de zero pode ser escrito como pro-
duto de polinômios irredutíveis.
107
Para inteiros Gaussianos, pode-se repetir a demonstração por indução na
norma. No entanto, podemos fazer melhor: uma demonstração que valha
para qualquer domínio Euclideano.
108
Os inteiros Gaussianos são, também, um domínio Euclideano. Os coefi-
cientes do polinômio (2 + i)x2 − 3x são inteiros Gaussianos, e o polinô-
mio é primitivo, porque seu conteúdo é mdc (2 + i, 3) = 1. Já o polinômio
(5i−1)x3 +(4+2i)x tem conteúdo mdc (5i, 4 + 2i) = {2+i, −2−i, −1+2i, 1−2i}
– não é, portanto, primitivo. J
e = c(e)E
h = c(h)H.
Então
Exercícios
Ex. 94 — Prove a segunda parte do Lema 5.2.
109
Ex. 98 — Prove que todo primo da forma 3n + 1 também é da forma 6k + 1.
√
k
Ex. 99 — Prove que se k e n são inteiros positivos e n é racional, então
√
k
n é inteiro.
Ex. 100 — Suponha que ab = cn , e que mdc (a, b) = 1. Prove que existem
d, e inteiros tais que
a = dn , b = en .
Ex. 101 — Prove que a soma de dois primos consecutivos nunca é o dobro
de um primo.
Ex. 103 — Prove que todo número de Fermat Fn com n > 1 tem o último
dígito igual a 7.
n−1
Ex. 105 — Prove que para n > 1, Fn = Fn−1 + 22 · F0 · F1 · · · Fn−2 .
Ex. 106 — Use o Teorema 5.20 para provar que há infinitos primos.
Ex. 107 — Prove que o 3 é o único natural que é número de Fermat e tam-
bém é número de Mersenne.
Ex. 108 — Mostre que todo inteiro positivo pode ser escrito como soma de
números de Fibonacci.
110
i) Mostre que
X1 Y 1
= 1
n
n p primo 1 − p
iii) Conclua que isto é impossível, observando que a série harmônica di-
verge.
1
1 1
2a → 1 2 1
3a → 1 3 3 1
1 4 6 4 1
5a → 1 5 10 10 5 1
1 6 15 20 15 6 1
7 →
a
1 7 21 35 35 21 7 1
(Note que a linha 2, (1, 2, 1), contém somente o dois, que é ele mesmo di-
visível por dois; a linha 3 contém duas vezes o 3, divisível por 3; a linha
5, (1, 5, 10, 10, 5, 1), contém múltiplos de 5; a linha sete também – contém
múltiplos de sete.)
m = mk mk−1 · · · m1 m0
n = nk nk−1 · · · n1 n0
Então
Yk
m mj
≡ (mod p).
n nj
j=1
Mostre como este Teorema poderia ter sido usado para resolver o Exercí-
cio 114.
10 Ver nota de rodapé 20 na página 10.
11 Édouard Lucas foi o primeiro a enunciar este teorema.
111
Ex. 116 — A respeito do Teorema de Lucas (Exercício 115): explique deta-
lhadamente porque, apesar de estarmos usando um sistema posicional, em
que os dígitos tem significados diferentes dependendo de sua posição na
representação, a ordem deles não é relevante no enunciado (simplesmente
toma-se o produtório sobre todos os dígitos!)
Ex. 117 — Prove que todo inteiro positivo pode ser representado como pro-
duto de um número ímpar e uma potência de dois (mesmo que seja 20 ).
100
Ex. 120 — Para quantos n o coeficiente binomial n é ímpar?
Ex. 121 — Quantas divisões sucessivas por 1344 podemos fazer com o nú-
mero 50! ?
Ex. 128 — O Teorema 5.35 afirma que em domínios Euclideanos todo ele-
mento pode ser fatorado em irredutíveis, mas não afirma que a fatoração é
única. Prove que em todo domínio Euclideano, a fatoração é única a não ser
por ordem e por multiplicação por unidades. Para isto, use a Definição e o
Lema a seguir.
Definição 5.39 (primo em domínio Euclideano). Em um domínio Euclide-
ano, um elemento p é primo se e somente se vale para ele o Lema de Eucli-
des (Lema 4.20, p | ab implica que p | a ou p | b).
Lema 5.40. Em um domínio Euclideano, todo elemento primo é irredutível.
112
Capítulo 6
Congruências
Arithmeticae.
Gauss, Johann Carl Friedrich. Disquisitiones Arithmeticae. [S. l.], 1801.
E definir congruência é a primeira coisa que faz no texto, na Seção I, “Números Congruentes
em Geral”. Artigo 1.
O conceito, no entanto, existiu por séculos antes disso. Maarten Bullynck oferece uma visão
bastante extensa do assunto.
Bullynck, Maarten. Modular arithmetic before C.F. Gauss: Systematizations and discussions
on remainder problems in 18th-century Germany. Historia Mathematica, v. 36, p. 48–72,
2009.
Bullyink comenta que métodos para aritmética com restos são conhecidos há muito tempo,
mas foi Bachet, em 1624 (ou 1612, se considerarmos a primeira edição de seu livro) quem
observou a conexão destes métodos com o algoritmo de Euclides para divisão. Também
reporta que métodos para resolver problemas deste tipo eram conhecidos na China e Índia,
tres ou quatro séculos a.C.
113
Se a e b deixam o mesmo resto quando divididos por m, então
a = sm + r,
b = tm + r.
Ao subtrairmos a − b, teremos
a − b = sm + r − tm − r
= sm − tm
= (s − t)m,
ii) m | a − b.
Hoc signum propter magnam analogiam quae inter aequalitatem atque con-
gruentiam invenitur adoptavimus. Ob eandem caussam ill. Le Gendre in com-
ment. infra saepius laudana ipsum aequalitis signum pro congruentia retinuit,
quod nos ne ambiguitas oriatur imitari dubitavimus.
3 Não é a única notação que existe para congruência. Há autores que usam a ≡ b para dizer
m
que a é congruente a b módulo m.
114
Usualmente trataremos somente de módulos positivos, sem qualquer preju-
ízo, já que m | (a − b) e −m | (a − b) são equivalentes.
i) a + c ≡ b + d (mod m),
115
Exemplo 6.7. Sabemos que 17 ≡ 32 ≡ 2 (mod 15), e escolhemos um poli-
nômio, p(x) = x2 − 3x + 2. Então
J
Exemplo 6.8. Se n ≡ 0 (mod 2), então n é par; se n ≡ 1 (mod 2), é ímpar; e
de maneira geral, n ≡ 0 (mod k) é uma forma de expressar que n é divisível
por k. J
Exemplo 6.9. Os números primos ímpares podem ser de duas formas: p ≡
1 (mod 4) (os da forma 4k + 1), e p ≡ 3 (mod 4) (os da forma 4k + 3). J
Teorema 6.10. Para todos a, b, c, d ∈ Z e 1 < m ∈ Z,
ab ≡ ac (mod 10)
(15)(10) ≡ (15)(2) (mod 10)
150 ≡ 30 (mod 10). (ok!)
ab ≡ ac (mod 10)
b≡c (mod 10)
10 ≡ 2 (mod 10). (não!)
116
Teorema 6.11 (lei de cancelamento). Em congruências, o cancelamento de
fatores se dá de acordo com a seguinte regra:
m
ab ≡ ac (mod m) se e somente se b ≡ c mod .
mdc (a, m)
ab ≡ ac (mod m)
ab − ac = km
a(b − c) = km
a m
(b − c) = k
mdc (a, m) mdc (a, m)
m a
b−c= k
mdc (a, m) mdc (a, m)
Mas a/ mdc (a, m) e m/ mdc (a, m) não tem fator comum (isto decorre da
definição de MDC), portanto a/ mdc (a, m) deve dividir k (e este passo não
seria possível se não tivéssemos feito a divisão por mdc (a, m)! ). Seja
k
k0 = .
a/ mdc (a, m)
Então
m
b − c = k0
mdc (a, m)
m
b≡c mod
mdc (a, m)
117
Demonstração. Se a ≡ b (mod mi ) para i = 1, . . . , k. Então
m1 | b − a,
m2 | b − a,
..
.
mk | b − a,
mmc(m1 , m2 , . . . , mk ) | b − a
a ≡ b (mod mmc(m1 , m2 , . . . , mk )).
O Lema 6.14, embora muito simples, nos permitirá trabalhar com inteiros
negativos (em especial, −1) em congruências. Isto será útil em algumas
demonstrações.
(−1) − (m − 1) = −1 − m + 1
= −m
Lema 6.15. Se p é primo, então todo número a tem inverso único módulo
p, ou seja, existe a tal que aa ≡ 1 (mod p).
Xp + Ya = 1
Ya = −Xp + 1 (Ya ÷ p deixa resto 1)
Ya ≡ 1 (mod p),
e Y é o inverso de a módulo p.
118
Suponha que haja dois inversos de a, b e c (ab ≡ 1 (mod p), e ac ≡ 1
(mod p)). Então
ab ≡ 1 ≡ ac (mod p)
ab ≡ ac (mod p)
b ≡c (mod p) (lei do cancelamento, mdc (a, p) = 1)
9(4) − 1(35) = 1.
9(4) − 1(35) = 1
−1(35) = 1 − 9(4)
35 | 1 − 9(4)
1 ≡ 9(4) (mod 35)
5(90) − 2(220) = 10
5(90) − 10 = 2(220)
220 | 5(90) − 10
5(90) ≡ 10 (mod 220),
primeira vez. O que se conhece hoje como “Teorema de Wilson” foi usado por Ḥasan Ibn
Al-Haytham ( اﻟﺤﺴﻦ ﺑﻦ اﻟﺤﺴﻦ ﺑﻦ اﻟﻬﻴﺜﻢ،)أﺑﻮ ﻋﻠﻲ, sem demonstração:
119
Lema 6.16. Se p é primo, a2 ≡ 1 (mod p) se e somente se a ≡ ±1 (mod p).
Rashed, Roshdi. Ibn Al-Haytham et le théorème de Wilson. Archive for History of Exact
Sciences, v. 22, n. 4, p. 305–321, 1980.
Pág. 85. Depois anunciado por Edward Waring, que afirmou em seu livro, Meditationes Alge-
braicae, que seu aluno John Wilson o havia descoberto (mas sem apresentar nenhuma prova).
Waring, Edward. Meditationes Algebraicae. 1. ed. [S. l.]: J. Archdeacon, 1770. Disponível
em [Link]
waring-edward-lucasian_1782. Existem traduções para o Inglês.
Na página 218:
120
Demonstração.
a2 ≡ 1 (mod p)
p|a −12
p | (a + 1)(a − 1)
p | (a + 1) ou p | (a − 1) (porque p é primo)
a ≡ −1 (mod p) ou a ≡ +1 (mod p).
O teorema foi finalmente provado por Joseph-Louis Lagrange em 1770. Doze anos depois disso
Waring publicou, em 1782, nova edição do Meditationes, desta vez creditando Lagrange.
Waring, Edward. Meditationes Algebraicae. 3. ed. [S. l.]: J. Archdeacon, 1782. Disponível
em https : / / archive . org / details / bim _ eighteenth - century _ meditationes - algebraic _
waring-edward-lucasian_1770. Existem traduções para o Inglês.
No original (Waring usa a grafia “Le Grange”, versão latinizada de acordo com as regras da
época. Lagrange era italiano descendente de franceses, nascido em Turim, com o nome Giu-
seppe Luigi Lagrangia,e posteriormente mudou para a França, adotando o nome Joseph-Louis
Lagrange):
Nessa terceira edição, no entanto, Waring ainda manteve a menção a Wilson como o “primeiro
a descobrir o teorema” (o texto que se refere a Wilson foi mantido, sem mudanças). Um breve
comentário sobre a história do teorema é dado por Oystein Ore:
Ore, Oystein. Number Theory and Its History. New York: Dover Publications, 1976.
121
Um exemplo simples: para p = 11, os quadrados são
x x2 (mod 11)
0 0 0
1 1 1
2 4 4
3 9 9
4 16 5
5 25 3
6 36 3
7 49 5
8 64 9
9 81 4
10 100 1
(n − 1)! ≡ −1 (mod n)
(n − 1)! = rn − 1 (para algum r ∈ Z)
= rkq − 1
= q(rk) − 1
(n − 1)! ≡ −1 (mod q)
≡1 ≡1 ≡1
z }| { z }| { z }| {
(a1 a1 ) (a2 a2 ) · · · (ak ak ) ≡1 (mod p)
2 · 3 · 4 · · · (p − 2) ≡1 (mod p) (ak são 2 · 3 · · · n − 2)
1 · 2 · 3 · 4 · · · (p − 2) ≡1 (mod p) (×1)
1 · 2 · 3 · 4 · · · (p − 2)(p − 1) ≡p − 1 (mod p) (×[p − 1])
(p − 1)! ≡ −1 (mod p) (p − 1 ≡ −1 (mod p))
122
Isto completa a demonstração.
Demonstração.
10 ≡ 0 (mod 2)
k k
10 ≡ 0 ≡ 0 (mod 2)
Portanto
Demonstração.
10 ≡ 1 (mod 3)
k k
10 ≡ 1 ≡ 1 (mod 3)
babilônios (com seu sistema de base 60) tinham critérios de divisibilidade por 2, 3, 4, 5 e 6. Os
egípcios (com base dez), por 2, 3, 4, 5 e 10. Há registros também de que na Índia, Āryabhaṭa
(आर्यभटः, 476-550) e Brahmagupta (ब्रह्मगुप्तः, 598-668) teriam desenvolvido critérios de divisi-
bilidade por 7, 8 9 e 11. O uso de congruências torma sistemática a descrição desses critérios,
resumindo muitas regras específicas em uma teoria compacta e simples, aplicável a diferentes
bases numéricas.
123
Portanto
Demonstração.
10 ≡ −1 (mod 11)
k k
10 ≡ (−1) (mod 11)
Portanto
Para divisores que sejam números compostos por estes estudados nesta se-
ção, basta usar simultaneamente critérios de divisibilidade: um número é
divisível por 12 se e somente se é divisível por 3 e por 4, logo a soma de seus
dígitos deve ser divisível por 3, e seus dois últimos dígitos devem represen-
tar um número divisível por 4.
124
Questionamos, evidentemente, sobre um critério de divisibilidade por sete.
O método acima pode nos dar um critério, mas ele não é prático.
10 ≡ 3 (mod 7)
k k
10 ≡ 3 (mod 7)
2 n
x ≡ d0 + 3d1 + 3 d2 + · · · + 3 dn (mod 7)
Demonstração.
(i)
8≡0 (mod 8)
k
8 ≡0 (mod 8)
Portanto
x ≡ d0 + 8d1 + 82 d2 + · · · + 8n dn (mod 8)
≡ d0 (mod 8)
125
(ii)
8≡1 (mod 7)
k
8 ≡1 (mod 7)
Portanto
x ≡ d0 + 8d1 + 82 d2 + · · · + 8n dn (mod 7)
≡ d0 + d1 + d2 + · · · + dn (mod 7)
(iii)
8 ≡ −1 (mod 9)
k k
8 ≡ (−1) (mod 9)
Portanto
x ≡ d0 + 8d1 + 82 d2 + · · · + 8n dn (mod 9)
n
≡ d0 + (−1)d1 + (1)d2 + · · · + (−1) dn (mod 9)
n
≡ d0 − d1 + d2 − · · · + (−1) dn (mod 9)
que estudou estas equações. Um livro com os estudos de Diofanto, com título “Arithmetica”
(Αριθμητικά ), tornou-se estímulo para muitos matemáticos europeus nos séculos seguintes.
Tome, por exemplo, a conhecida história do último teorema de Fermat: a margem que Fermat
declarou que era muito pequena para conter sua demonstração era de um exemplar deste
livro. Boa parte dos treze livros de Diofanto, infelizmente, se perderam: há livros faltando, e
o texto original, em grego, se perdeu, e o que se conhece hoje é uma tradução do Grego para
o Árabe, que depois foi traduzido de volta para Grego e Latim. O volume que Fermat usava é
uma edição publicada por Bachet em 1621.
Os dois volumes a seguir, em Latim e Grego e publicados por Paul Tannery em 1895, con-
tém parte dos volumes originais (sabe-se que há tres volumes faltando, mas não se sabe quais):
Diophantus. Diophanti Alexandrini opera omnia cum Graecis commentariis. Edição:
P. Tannery. [S. l.]: Stutgardiae Teubner, 1895. v. 1. Disponível em https : / / archive . org /
details/diophantialexan03plangoog/.
126
muito conhecida é an + bn = cn , que de acordo com o último Teorema de
Fermat não tem soluções inteiras. Nesta seção desenvolvemos uma técnica
simples para determinar soluções para o tipo mais simples de equações
Diofantinas – as lineares.
a b c
Ax + By = C, A= ,B = ,C =
mdc (a, b) mdc (a, b) mdc (a, b)
Ar + Bs = 1.
ArC + BsC = C,
Exemplo 6.24. Resolveremos a equação 15x+51y = 42. Como mdc (15, 51) =
3 e 3 | 42, as soluções que procuramos são as mesmas de
5x + 17y = 14.
127
Temos as soluções x 0 = 7, y 0 = −2. Multiplicando por 14 obtemos
x = 98, y = −28.
Exemplo 6.26. Queremos todas as soluções para 6x + 10y = 164, com uma
restrição adicional: x, y ≥ 9.
As soluções serão as mesmas para
3x + 5y = 82,
3(2) + 5(−1) = 1
Esta solução ainda não é uma das que queremos, porque y = −82 < 9. A
forma geral é, no entanto,
128
e as soluções que queremos são
164 + 5k ≥ 9 (i)
−82 − 3k ≥ 9 (ii)
Resolvemos (i):
5k ≥ 9 − 164
155
k≥− = −31
5
E agora, (ii):
−3k ≥ 82 + 9
91
k≤− ≈ −30.333
3
Assim, somente podemos usar k = −31. J
a b m
Ax ≡ B (mod M), A= ,B = ,M = .
d d d
Como agora A e M são co-primos, existe um único inverso para A módulo
M, que denotaremos A. Temos portanto AA ≡ 1 (mod M). Suponha que
129
tenhamos uma solução x0 :
Ax0 ≡ B (mod M)
AAx0 ≡ AB (mod M) (A unicamente determinado)
x0 ≡ AB (mod M)
M | AB − x0
kM = AB − x0 (k unicamente determinado)
x0 = AB − kM,
uma única solução para Ax ≡ B (mod M). Passamos agora para módulo m.
Suponha que a solução para Ax ≡ B (mod M) seja x0 . As soluções para esta
congruência seriam
x0 + tM, com t = 0, 1, . . . , M − 1.
x0 + tM, com t = 0, 1, . . . , m − 1.
Temos 9 valores de k que são incongruentes módulo 27. Estes nos darão as
130
9 soluções:
k 9k + 648 (mod 27)
0 648 0
1 651 3
2 654 6
3 657 9
4 660 12
5 663 15
6 666 18
7 669 21
8 672 24
9 675 0
10 678 3
.. .. ..
. . .
x ≡ a1 (mod m1 )
x ≡ a2 (mod m2 )
..
.
x ≡ ar (mod mr )
7 Āryabhaṭa (आर् यभटः, 476-550), Al-Khwarizmi (ﺧﻮارزﻣﯽ8 , 780-850), Ibn Yunus Ibn Yunus
(اﺑﻦ ﻳﻮﻧﺲ, 950-1009), Ibn al-Haytam ( اﺑﻦ اﻟﻬﻴﺜﻢ965-1040), Bhāskara (भास्करा, 1118-1185), Yī
Xíng (一行, 683-727), Qín Jiǔsháo 9 (秦九韶, 1202-1261) e muitos europeus escreveram sobre
o mesmo problema – uma longa lista de matemáticos é dada por Dickson.
Dickson, Leonard Eugene. History of The Theory of Numbers. New York, N.Y.: Chelsea
Publishing Company, 1971. v. 2.
9 O nome completo é Abū Jaʿfar Muḥammad ibn Mūsā al-Khwārizmī , اﺑﻮ ﺟﻌﻔﺮ ﻣﺤﻤﺪ ﺑﻦ ﻣﻮﺳﯽ
ﺧﻮارزﻣﯽ.
131
Matemático do Mestre Sūn ”)10 , escrito por Sūnzǐ 14 (孫子, “Mestre Sūn ”),
que no Século IV teria proposto problemas como o que segue, apresentando
10 O livro tem três capítulos, e o Teorema que descrevemos aqui é apresentado (de maneira
bastante diferente, mais limitada e na forma de solução para problema concreto) no capítulo
3. Há uma tradução para o Inglês, de Lam Lay Yong e An Tian Se.
Yong, Lam Lay; Se, An Tian. Fleeting Footsteps. [S. l.]: World Scientific Publishing Com-
pany, 2004.
O livro traz, além da tradução do clássico do Mestre Sūn , comentários sobre o contexto em
que surgiu – aspectos socioeconômicos e considerações sobre a possibilidade do sistema
Hindu-Árabe de numerais ter tido origens na China. O original do Mestre Sūn é escrito na
forma problema-resposta-método. Por exemplo, o quarto problema do terceiro livro é
Agora, há um livro sobre Budismo com um total de 29 Capítulos. Cada Capítulo
tem 63 caracteres. Encontre o número total de caracteres.
Resposta: 1827.
Método: Tome 29 capítulos e multiplique por 63 caracteres para obter a resposta.
Este é um problema básico, mas exemplifica o estilo. Aspectos culturais se entrelaçam com
a Matemática (a separação das Ciências Exatas do resto da cultura é um fenômeno essencial-
mente europeu, consequência do Iluminismo). O último problema do livro é:
Agora, há uma mulher grávida cuja idade é 29. Se o período de gestação é de
nove meses. determine o sexo da criança que nascerá.
Resposta: masculino.
Método: Tome 49, some o período da gestação e subtraia a idade. Do resto
remova 1 representando o céu, 2 a terra, 3 o homem, 4 as quatro estações, 5 as
5 fases11 , 6 as seis flautas de afinação12 , 7 as sete estrelas13 , 8 os oito ventos
e 9 as nove divisões (da China sob Yu, o Grande)14 . Se o resto for ímpar, será
masculino, e se o resto for par, será feminino.
Para além das crenças presentes no método, é interessante que Mestre Sūn não tenha simpli-
ficado a conta, já que 49 − 1 − 2 − 3 − 4 − 5 − 6 − 7 − 8 − 9 = 4, que é par, e não modifica a paridade
da idade – a resposta poderia ser “Se a idade prevista para o nascimento (29 mais o período
de gestação) é ímpar, será masculino; se é par, será feminino”. Os elementos citados (céu,
terra, etc) tinham grande peso cultural, e aparentemente este problema foi concebido mais
para apresentar (ou citar) estes elementos do que realmente para tratar de algum método
matemático.
11 Cinco fases são os cinco elementos, madeira, fogo, terra, metal e água, de grande impor-
regiões. Na tradição chinesa, diz-se que Yu, o Grande (大禹) teria dividido a China em nove
províncias (zhōu , 州, literalmente “terra”). Não há evidências de que o Grande Yu de fato
tenha existido.
12 As seis flautas de afinação eram um conjunto de tubos de bambu ou metal, que produziam
seis notas musicais, e além de serem fundamentais para a música tradicional chinesa, tinham
um significado filosófico, representando harmonia e equilíbrio.
13 As sete estrelas da constelação Ursa Maior.
14 Homônimo, mas absolutamente não o mesmo Sūnzǐ (544 a.C - 496 a.C) que escreveu “A
Arte da Guerra” (e cujo nome é usualmente transliterado como “Sun Tzu”, e cuja existência é
questionada por historiadores).
Sun Tzu. A Arte da Guerra. [S. l.]: Edipro, 2021. Sun é nome; Tzu é título (mestre). Edi-
ção bilíngue. Há também uma tradução para o Inglês, livremente disponível em https : / /
[Link]/details/[Link].18750/page/115/mode/2up.
O Sūnzǐ que expôs o Teorema Chinês viveu muito mais tarde que o autor do clássico livro
sobre a Guerra (presumindo que este existiu!). Infelizmente não sabemos muito sobre o
Matemático Mestre Sūn , a não ser que viveu entre os séculos III e V, na dinastia Tang.
132
também um “método” para resolvê-lo:
O problema dado por Sūnzǐ circulou por toda a China, e havia interesse
dos matemáticos em uma solução geral para problemas do mesmo tipo (iso-
ladamente, o problema era somente um quebra-cabeças interessante). A
primeira vez em que o teorema foi de fato provado na China foi em 1247,
por Qín Jiǔsháo (秦九韶) no “Tratado Matemático em Nove Seções” (Shùshū
Jiǔzhāng , 数书九章)16 . O problema de resolver sistemas de equações en-
volvendo restos está também presente no tratado Brāhmasphuṭasiddhānta
15 Este é o vigésimo-sexto problema da terceira parte do livro de Sūnzǐ .
Yong, Lam Lay; Se, An Tian. Fleeting Footsteps. [S. l.]: World Scientific Publishing Com-
pany, 2004.
Resposta: 23.
Método: Se contarmos aos três e restam 2, tome 140. Se contarmos aos cinco e
restam 3, tome 63. Se contarmos aos sete e restam 2, tome 30. Some-os para obter
233, e subtraia 210 para obter a resposta.
O texto original, com a resposta e o método:
今有物,不知其數。三、三數之,賸二;五、五數之,賸三;七、七數之,賸二。問物
幾何 ?
答曰:二十三。
術曰:「三、三數之,賸二」,置一百四十;「五、五數之,賸三」,置六十三;「七、七
數之,賸二」,置三十。并之,得二百三十三。以二百一十減之,即得。凡三、三數之,
賸一,則置七十;五,五數之,賸一,則置二十一;七、七數之,賸一,則置十五。一
百六以上,以一百五減之,即得。
(Jīn yǒu wù, bùzhī qí shù. Sān, sān shù zhī, shèng èr; wǔ, wǔ shù zhī, shèng sān; qī, qī shù
zhī, shèng èr. Wèn wù jǐhé?
dá yuē: Èrshísān
shù yuē:`Sān, sān shù zhī, shèng èr', zhì yībǎi sìshí;`wǔ, wǔ shù zhī, shèng sān', zhì
liùshísān;`qī, qī shù zhī, shèng èr', zhì sānshí. Bìng zhī, dé èrbǎi sānshísān. Yǐ èrbǎi yīshí
jiǎn zhī, jí dé. Fán sān, sān shù zhī, shèng yī, zé zhì qīshí; wǔ, wǔ shù zhī, shèng yī, zé zhì
èrshíyī; qī, qī shù zhī, shèng yī, zé zhì shíwǔ. Yībǎi liù yǐshàng, yǐ yībǎi wǔ jiǎn zhī, jí dé.)
16 A primeira das nove seções se chama “Dayan lei” (大衍類 ou 大衍类). Um tratado sobre
Detalhes do método desenvolvido por Qín Jiǔsháo são dados no livro de Ulrich Libbrecht e no
capítulo de Dauben.
Libbrecht, Ulrich. Chinese Mathematics in the Thirteenth Century: the Shu-shu chiu-
chang of Ch’in Chiu-shao. [S. l.]: MIT, 1973.
Dauben, Joseph W. Mathematics of Egypt, Mesopotamia, China, India, and Islam: A Source-
book. In: edição: Victor Katz. [S. l.]: Princeton University Press, 2007. Chinese Mathema-
tics.
133
(बा्रह्मस्फुटिसद्धान्तः), do Indiano Brahmagupta (ब्रह्मगुप्तः, 598-668)17 , que
era astrônomo – problemas deste tipo surgem naturalmente ao se tratar
de corpos celestiais com órbitas de períodos diferentes18 .
Enunciamos o Teorema a seguir, e damos uma demonstração construtiva (o
método que derivamos da demonstração é bastante diferente do de Sūnzǐ ).
x ≡ a1 (mod m1 )
x ≡ a2 (mod m2 )
..
.
x ≡ ar (mod mr )
M
Mk = .
mk
a i Mi Mi ≡ 0 (mod mj )
ai Mi Mi 6≡ 0 (mod mi )
Colebrooke, Henry Thomas. Algebra, with Arithmetic and mensuration, from the Sans-
crit of Brahmegupta and Bháscara. [S. l.]: London J. Murray, 1817. Disponível em https:
//[Link]/details/algebrawitharith00brahuoft.
134
onde i 6= j porque mj | Mi , e portanto ai Mi Mi ≡ (ai )(0)(Mi ) ≡ 0 (mod mj ).
Assim, para cada mi a soma será
x ≡2 (mod 3)
x ≡1 (mod 7)
x ≡3 (mod 10)
M1 = (7)(10) = 70
M2 = (3)(10) = 30
M3 = (3)(7) = 21
Os inversos são
M1 = 1 (mod 3)
M2 = 4 (mod 7)
M3 = 1 (mod 10)
Assim,
113 ≡ 2 (mod 3)
113 ≡ 1 (mod 7)
113 ≡ 3 (mod 10)
Note que toda a classe de congruência 113 módulo 210 é solução para o
135
sistema: {. . . , −307, −97, 113, 323, 533, . . .} = {210k + 113 | k ∈ Z}. J
O Teorema Chinês dos Restos pode ser generalizado para sistemas onde
os módulos não são co-primos, mas sistemas dessa forma nem sempre tem
solução. Nesta seção detalhamos o critério para existência da solução, além
de uma demonstração construtiva que permite obte-la, quando existir.
Nos Lemas a seguir trataremos de sistemas de congruências
x ≡ a1 (mod m1 ),
x ≡ a2 (mod m2 ),
..
.
x ≡ ak (mod mk ). (6.2)
Lema 6.31. Se, para algum i 6= j, mdc (mi , mj ) - (ai − aj ), então o sistema
de congruências 6.2 não tem solução.
mas isso significa que x não pode satisfazer simultaneamente as duas equa-
ções
Lema 6.32. Se, para todo i 6= j, mdc (mi , mj ) | (ai − aj ), então o sistema de
congruências 6.2 tem solução.
x ≡ ai (mod mi )
136
por
x ≡ ai (mod pi11 )
x ≡ ai (mod pi22 )
..
.
x ≡ ak (mod pikk ).
x≡3 (mod 52 )
x≡3 (mod 7)
seria transformado em
m i = · · · pN · · · ,
m j = · · · pn · · · ,
N > n.
137
m3 = 5 = 51 – neste caso, pN é 52 , e pn é 51 .
Então pn | mdc (mi , mj ).
Como mdc (mi , mj ) | (ai − aj ),
x ≡ ai (mod pN )
pN | x − a i (definição de congruência)
pn | x − a i (N>n)
n
x ≡ ai (mod p ) (definição de congruência)
x ≡ ai (mod pN )
implica em
x ≡ aj (mod pn ),
e podemos remover, dentre as congruências de módulo potência de um
mesmo primo, todas exceto a da maior potência.
O resultado é um sistema de congruências equivalente ao original, mas onde
cada congruência tem como módulo uma potencia de primo, sem que haja
repetição dos primos. Os módulos são, portanto, co-primos, e pelo Teorema
Chinês dos Restos, podemos resolver o sistema.
x ≡ 31 (mod 72)
x ≡ 15 (mod 20)
x ≡ 13 (mod 42)
138
Substituímos as congruências por outras, com módulos potencia de primo.
72 = 23 · 32
20 = 22 · 5
42 = 22 · 3 · 7
x ≡ 31 (mod 23 )
x ≡ 31 (mod 32 )
x ≡ 15 (mod 22 )
x ≡ 15 (mod 5)
x ≡ 13 (mod 2)
x ≡ 13 (mod 3)
x ≡ 13 (mod 7)
x ≡ 31 (mod 23 )
x ≡ 31 (mod 32 )
x ≡ 15 (mod 5)
x ≡ 13 (mod 7).
Agora os módulos são co-primos, e podemo usar o Teorema Chinês dos res-
tos. Obtemos x = 895, que será único módulo mmc(72, 20, 42) = 2520. É
trivial verificar o resultado:
139
Então um sistema de congruências
x ≡ a1 (mod m1 ),
x ≡ a2 (mod m2 ),
..
.
x ≡ ak (mod mk ).
O Teorema Chinês dos Restos tinha como contexto original a contagem mó-
dulo algum inteiro, e sua expressão moderna, na forma de congruências, foi
dada por Gauss.
A partir da metade do Século XIX houve uma tendência à abstração, e o
conceito de congruência mostrou-se insuficiente para expressar o que mate-
máticos pensavam (nasceu nesse período a Álgebra em sua forma abstrata,
moderna), e novas idéias foram sendo introduzidas. Em particular, anéis e
ideais. Pessoas centrais neste processo foram Leopold Kronecker, Richard
Dedekind e Emmy Noether. Em algum momento entre a metade do Século
XIX e o início do século XX, o Teorema Chinês dos Restos teve seu enunci-
ado trocado por uma forma mais abstrata e abrangente, envolvendo anéis
e ideais. Esta Seção traz uma versão ligeiramente simplificada da versão
moderna19 .
Apresentamos novamente o Teorema Chinês dos Restos, mas desta vez usando
isomorfismo entre anéis, e restringindo ao caso particular em que os anéis
são Zn e Zm .
Seja n = ab, com mdc (a, b) = 1, e considere os anéis
Zn = {0, 1, 2, . . . , n − 1},
Za = {0, 1, 2, . . . , a − 1},
Zb = {0, 1, 2, . . . , b − 1},
I1 , . . . , In , mutuamente coprimos aos pares (ou seja, se i 6= j então Ii + Ij = R), o mapa natural
R → R/I1 × · · · × Ii é sobrejetor com núcleo I1 ∩ · · · ∩ In , e portanto induz um isomorfismo
∼ Q
R/(I1 ∩ · · · ∩ In ) = R/Ij ”. Este texto não define ideal de um anel, e o Teorema pode ser
enunciado sem usar explicitamente o conceito, por isso a simplificação.
140
Observe que o produto cartesiano
Za × Zb = {(x, y) | x ∈ Za , y ∈ Zb }
= {(0, 0), (0, 1), . . . , (a − 1, b − 1)}
Enunciamos uma nova versão do Teorema Chinês dos Restos. Este enuncu-
ado, em um primeiro exame, não parece ter relação com o Teorema Chinês
dos Restos enunciado anteriormente (Teorema 6.29) – mas a relação ficará
clara adiante.
f : Zmn → Zm × Zn
f(x) = (x, x),
[x1 ]n 6= [x2 ]n ,
f([x1 ]n ) = ([x]a , [x]b ), (6.6)
f([x2 ]n ) = ([x]a , [x]b ). (6.7)
141
Mas destas equações, olhando apenas para a primeira parte dos pares or-
denados, vemos que
de 6.6, x1 ≡ x (mod a)
de 6.7, x2 ≡ x (mod a)
x1 ≡ x2 (mod b).
Considere a equação
17s + 10t = 1.
Obtemos os coeficientes de Bézout, s = 3, t = −5:
3(17) − 5(10) = 1.
142
Agora multiplicamos, e chegamos a
51 − 50 = 1.
Observamos que
51 ≡ 1 (mod 10)
51 ≡ 0 (mod 17)
−50 ≡ 0 (mod 10)
−50 ≡ 1 (mod 17)
Temos dois números que são congruentes a zero e um nos dois módulos, de
forma que podemos escrever
Ou seja,
percebemos que
Nesta Seção usamos isomorfismos entre anéis para obter um resultado equi-
valente ao Teorema Chinês dos Restos, mas ainda o aplicamos somente em
Zn . O Teorema pode ser também generalizado para que seja aplicado em
anéis arbitrários – tópico fora do escopo deste texto.
143
6.6 Congruências lineares em n variáveis
Tratamos anteriormente de congruências lineares em uma única variável.
Queremos também poder resolver congruências lineares em várias variá-
veis,
a1 x1 + a2 x2 + · · · + an xn ≡ b (mod m).
Da mesma forma que para congruências lineares em uma variável, é neces-
sário que mdc (a1 , a2 , . . . , an , m) | b para que haja solução.
Primeiro observamos que esta congruência é equivalente à equação Diofan-
tina
a1 x1 + a2 x2 + · · · + an xn − b = km
onde as incógnitas são os ai e k.
Para maior clareza, iniciamos com um exemplo em três variáveis,
a1 x1 + a2 x2 + a3 x3 = s (6.8)
mdc (a1 , a2 ) r + a3 x3 = s,
a1 x1 + · · · + an xn ≡ b (mod m)
144
Definição 6.39 (congruência polinomial). Uma congruência da forma
145
Será interessante se pudermos reduzir o problema de obter solução para
uma congruência módulo pa a outra, módulo pb , com b < a.
Procuramos as soluções de uma congruência módulo pa . Para qualquer
b < a, como pb | pa , o Teorema 6.40 nos garante que as soluções módulo
pb também são soluções módulo pa . Obteremos agora um método para, a
partir de soluções módulo pb , chegar a soluções módulo pa – o Lema de
Hensel, demonstrado em 190422 por Kurt Hensel.
Lema 6.42 (de Hensel). Seja f(x) um polinômio com coeficientes inteiros.
Se x ∈ Z, f(x) ≡ 0 (mod pb ) e f 0 (x) 6≡ 0 (mod p), então existe um único t
inteiro positivo tal que f(x + tpb ) ≡ 0 (mod pb+1 ).
Quando f 0 (x) ≡ 0 (mod p), a solução é singular; de outra forma, é não sin-
gular.
O Lema de Hensel é semelhante ao método de Newton – o que ficará claro
em sua demonstração.
Aogra, cada termo aj xj no polinômio f(x) contribui em cada f(k) (x)/k! com
o termo
j(j − 1) · · · (j − k + 1) j−k j
cj x = cj xj−k .
k! k
Isto significa que todos os f(k) (x)/k! são inteiros.
Como estamos trabalhando módulo pj+1 , todos os termos exceto os dois
Hensel, Kurt. Neue Grundlagen der Arithmetik. Journal für die reine und angewandte
Mathematik, v. 127, p. 51–84, 1904.
22
Since then, many variations and generalisations of Hensel’s result have been
found, some of which bear only little resemblance to the original. Confusingly, all
these theorems are known today as “Hensel’s lemma”.
146
primeiros são nulos (porque todos tem pj+1 na fatoração). Logo,
f(x)
tf 0 (x) ≡ − (mod p).
pj
aj+1 = aj + tpj
h i−1 f(a )
j
= aj + − f 0 (aj ) pj
pj
h i−1
= aj − f 0 (aj ) f(aj ).
Temos os polinômios
f(x) = x3 + 2x2 − x − 2
f 0 (x) = 3x2 + 4x − 1.
f(x) (mod 3)
147
únicas possibilidades de solução, 0, 1, 2.
f(0) = −2 ≡ 1 (mod 3)
f(1) = 0 ≡ 0 (mod 3)
f(2) = 12 ≡ 0 (mod 3)
f 0 (1) = 6 ≡ 0 (mod 3)
0
f (2) = 19 ≡ 1 (mod 3)
A solução módulo 32 é
−1
x2 = x1 − f 0 (2)
f(2)
= 2 − (1)(12)
= −10
≡8 (mod 9)
Verificamos:
f(8) = 630 ≡ 0 (mod 9).
3
A solução módulo 3 é
−1
x3 = x2 − f 0 (2)
f(8)
= 8 − (1)(630)
= −622
≡ 26 (mod 27)
Finalmente,
f(26) = 18900 ≡ 0 (mod 27).
Note que p - f 0 (x) – ou seja, 3 - 19, e pelo Corolário 6.43, há uma só solução.
J
148
conforme o enunciado do Teorema 6.45. A demonstração (na verdade muito
simples) é pedida no exercício 160.
Temos os polinômios
f(x) = x3 − 100x
f 0 (x) = 3x2 − 100.
x3 − 100x2 (mod 5)
O Lema de Hensel não nos permite usar a solução zero, porque f 0 (0) ≡ 0
(mod 5).
149
e temos as soluções 0, 5, 10, 15, 20:
para todo yi . Mas g(x) tem grau menor que k (o termo líder de f(x) é
cancelado por ak xk em g(x)). Isto significa que temos uma congruência de
grau menor que k, com mais que k soluções. Como p não divide o termo
líder de f(x), o grau de f(x) é k + 1. Pela hipótese de indução, só nos resta
supor que, para todo x inteiro,
150
Ou seja, g(x) é identicamente zero.
Tomamos então yk+1 .
que
O problema surgiu em conexão com um método para gerar números aleató-
rios, mas acabou se mostrando inesperadamente complexo, então rapidamente
se tornou objeto de interesse por si mesmo.
No original,
The problem arose in connection with a method for generating random num-
bers, but it turned out to be unexpectedly intricate, and so quickly became of
interest in its own right.
151
Interessantemente, a sequência u(mod 2) parece ser periódica (o padrão
1, 1, 0 se repete). Também em u(mod 3), o padrão 1, 1, 2, 0, 2, 2, 1, 0 parece se
repdroduzir, assim como em u(mod 4) o padrão 1, 1, 2, 3, 1, 0 se repete. J
O Exemplo 6.50 nos motivaa questionar se as sequencias u(mod n) são pe-
riódicas, e é isso que o Lema 6.51 estabelece.
k(2) = 3 k(7) = 16
k(3) = 8 k(8) = 12
k(4) = 6 k(9) = 24
k(5) = 20 k(10) = 60
k(6) = 24
Teorema 6.53. Se m > 2, então k(m) é par.
Como k − 1 é par, uk−1 = −u1−k ≡ −u1 . Então u1 ≡ −u1 (mod m), mas isto
só é possível quando m = 2.
24 Há autores que o denotam por π(m), mas neste texto usaremos π(n) para denotar uma
152
Como m deve ser 2 para valores ímpares de k, então todos os outros valores
de k devem ser pares.
ai
MDC dos k(pi ):
Demonstração. (Rascunho)
O Teorema 6.55 garante que k(pi i ) | k(m) para todo i. Assim,
a
mmc(k(pai i )) | k(m). a
(mmc de todos os pi i )
Mas como evidentemente k(pi i ) | mmc(k(pai i )), temos que u(mod pi i ) deve
a a
Teorema 6.57. Seja t o maior inteiro tal que k(pt ) = k(p). Então k(ps ) =
ps−t k(p).
Exercícios
Ex. 130 — Prove que para todo a > 0 e todo m > 1, a ≡ a (mod m).
153
Ex. 131 — Prove que para todo x ímpar e todo inteiro positivo n,
n
x2 ≡ 1 (mod 2n+2 )
Ex. 133 — Prove que, para todos x, y, z ∈ N, se x2 +y2 = z2 , com mdc (x, y, z) =
1, então 3 | x ou 3 | y (mas não ambos!)
Ex. 136 — Prove que se 0 ≤ |a| < m/2, 0 ≤ |b| < m/2 e a ≡ b (mod m),
então a = b.
154
Ex. 142 — Calcule os inversos
Ex. 143 — Mostre uma solução inteira positiva para 30x + 18y = 132, ou
prove que não existe.
Ex. 149 — Seja p um primo ímpar. Determine quais inteiros n existem tais
que p | n2n + 1.
Ex. 150 — Generalize a noção de congruência para o anel Z[i] dos inteiros
Gaussianos, e prove que todo a + bi, é congruente a 0 ou +1 módulo (1 + i).
Ex. 151 — Da forma como apresentamos, o Teorema Chinês dos restos nos
dá solução para sistemas onde cada equação é da forma x ≡ ai (mod mi ).
Mostre como resolver sistemas da forma bi x ≡ ai (mod mi ).
(i)
x ≡2 (mod 5)
x ≡3 (mod 28)
x ≡ 10 (mod 13)
155
(ii)
x ≡1 (mod 36)
x ≡ 10 (mod 12)
x ≡ 15 (mod 470)
(iii)
x ≡4 (mod 10)
4x ≡ 5 (mod 21)
10x ≡ 2 (mod 11)
(iv)
x ≡3 (mod 20)
3x ≡ 2 (mod 35)
2x ≡ 1 (mod 12)
Ex. 153 — Em dúzias, sobra um; em dezenas, sobram três; em setes, so-
bram seis. Qual é o número?
Ex. 156 — Desenvolva um algoritmo que, dada uma lista de números na-
turais m1 , m2 , . . . , mk e um número inteiro a1 , gere aleatoriamente (não
necessariamente de maneira equiprovável) um sistema de congruências
x ≡ a1 (mod m1 )
x ≡ a2 (mod m2 )
..
.
x ≡ ak (mod mk )
156
Ex. 158 — Demonstre o Teorema 6.38.
Ex. 162 — Seja M(x) : Zp → Zp uma função que mapeia classes de re-
síduos. Mostre que para todo primo p existe um polinômio f(x), de grau
estritamente menor que p e com coeficientes integrais, tal que f(x) ≡ M(x)
(mod p) para todo x ∈ Z.
157
158
Capítulo 7
Funções Aritméticas
Euler, Leonhard. Variae observationes circa series infinitas. Commentarii academiae sci-
entiarum Petropolitanae, v. 9, p. 160–188, 1744.
159
uma conexão entre números primos e um produto infinito. No Século IX, Di-
richlet introduziu outros conceitos (caracteres e L-funções), usando méto-
dos analíticos para provar que há infinitos primos da forma ak + b, para a, b
co-primos3 . Em 1859, Bernhard Riemann publicou um artigo4 estudando as
propriedades da função anterirmente abordada por Euler, dando-lhe o nome
de zeta (ζ), e transformando um problema aritmético clássico (a contagem
de primos menores do que um dado inteiro) em um problema de Análise, e
estabelecendo definitivamente a área conhecida como “Teoria Analítica de
Números”.
Exemplo 7.2. Funções simples tendo inteiros positivos como domínio, como
f(n) = 2n são funções aritméticas. Também a função que dá o n-ésimo dí-
gito de π é função aritmética. Da mesma forma,
+1 se o n-ésimo dígito de π é par
f(n) =
−1 se o n-ésimo dígito de π é ímpar
é função aritmética. J
1(n) = 1.
Euler aqui estabelece, portanto, uma expressão da função zeta de Riemann (que ainda não
tinha esse nome) como produto.
Dirichlet, L. Beweis des Satzes, dass jede unbegrenzte arithmetische Progression, deren
erstes Glied und Differenz ganze Zahlen ohne gemeinschaftlichen Factor sing, unendlich vi-
ele Primzahlen erhält. Abhandlungen der Königlich Preußischen Akademie der Wis-
senschaften, p. 45–81, 1837.
3
Riemann, Bernhard. Über die Anzahl der Primzahlen unter einer gegebenen Grösse (On the
Number of Primes Less Than a Given Magnitude). Monatsberichte der Königlich Preußis-
chen Akademie der Wissenschaften zu Berlin, p. 671–680, 1859.
4
160
As três funções a seguir foram definidas e estudadas por Euler.
1, 2, 3, 4, 6, 12,
portanto
d(12) = 6,
σ(12) = 28.
1, 5, 7, 11,
portanto φ(12) = 4. J
Y
r
d(n) = (αi + 1).
i=1
d(72) = (3 + 1)(2 + 1)
=4·3
= 12. J
161
Agora demonstramos o Teorema por indução na quantidade de fatores pri-
mos distintos de n (cada um elevado a uma potência).
Provamos a base, com um único fator (ou seja, n é uma potência de primo
pj ):
d(pj ) = j + 1,
porque p0 , p1 , . . . , pj dividem pj .
A hipótese de indução é que se n tem r fatores primos distintos, então
Y
r
d(n) = (αi + 1).
i=1
Y
r
d(n) = (αi + 1),
i=1
c | N ⇔ c = ab,
a | n, b | pβ ,
Y
r
d(N) = (β + 1) (αi + 1)
i=1
= (α1 + 1)(α2 + 1) · · · (αr + 1)(β + 1).
pk+1 − 1
σ(pk ) = .
p−1
α α α
Teorema 7.9. Seja n um número natural com fatoração n = p1 1 p2 2 · · · pk k .
162
Então
Y
k
pαi +1 − 1
i
σ(n) = .
pi − 1
i=1
1, 2, 3, 6, 9, 18,
σ(18) = σ(2 · 32 )
1+1 2+1
2 −1 3 −1
=
1 2
3 26
=
1 2
= 39. J
a a a
Teorema 7.11. Se a fatoração de n é p1 1 p2 2 · · · pk k , então
Y
k
1
φ(n) = n 1−
pj
j=1
6 Há um método mais simples, mas só poderemos usá-lo depois de definirmos funções multi-
163
da inclusão-exclusão7 , concluímos que φ(150) é igual a
+ {n < 150 : (2 · 3 · 5) | n} ,
onde n ∈ N e n > 0.
Os tamanhos dos conjuntos listados são as partes inteiras das frações
φ(150) = 149 − 74 − 49 − 29 + 24 + 14 + 9 − 4
= 40.
164
Exemplo 7.14. Os divisores de 12 são
1, 2, 3, 4, 6, 12,
e então
quisitiones. O enunciado é
“Se a, a 0 , a 00 , etc são todos os divisores de A (incluindo a unidade e A, ele
mesmo), teremos
φa + φa 0 + φa 00 + etc = A.”
Gauss dá um exemplo, com A = 30, e em seguida apresenta a demonstração. A título de
curiosidade, esta é a forma como os conjuntos Nd são construídos no Disquisitiones (ali esse
nome não lhes é dado):
“Multiplique por A/a todos os números que são primos relativos a a mas não
maiores que a; faça o mesmo com a 0 , multiplicando por A/a 0 , etc. Teremos
φa + φa 0 + φa 00 etc números, nenhum maior que A.”
No resto da demonstração ele mostra que (1) os números são distintos; (2) Todos os números
1, . . . , A estão incluídos, e (3) portanto o resultado segue.
Gauss, Johann Carl Friedrich. Disquisitiones Arithmeticae. [S. l.], 1801.
165
conjunto (Nd ∩ Ne = ∅).
Além disso, os conjuntos Nd contém todos os números em N,
[
N= Nd .
d
uma contradição.
Em cada conjunto Nd ,
i) os elementos são múltiplos de d, rd, porque são números k com mdc (k, n) =
d;
ii) como mdc (k, n) = d, então mdc (r, n/d) = 1;
15 3
−→ ,
40 8
166
o denominador (8) é divisor de 40.
As frações onde n ainda é o denominador são aquelas nas quais o numerador
era co-primo com n. Há φ(n) destas frações.
Para cada divisor d de n haverá exatamente φ(d) frações onde o denomina-
dor é igual a d. Se somarmos todos estes φ(d) teremos o número total de
frações, n.
A demonstração acima poderá ficar mais clara com uma ilustração. Esco-
lhemos n = 18 e listamos as frações. A primeira linha tem as frações antes
da simplificação; a segunda as tem já simplificadas.
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18
18 18 18 18 18 18 18 18 18 18 18 18 18 18 18 18 18 18
↓ ↓ ↓ ↓ ↓ ↓
1 1 1 2 5 1 7 4 1 5 11 2 13 7 5 8 17 1
18 9 6 9 18 3 18 9 2 9 18 3 18 9 6 9 18 1
φ(1) = 1
φ(2) = 1
φ(3) = 2
φ(6) = 2
φ(9) = 6
φ(18) = 6
Exemplo 7.17. J
Exemplo 7.18. A função f(n) = n + 1 não é multiplicativa:
f(ab) = ab + 1
f(a)f(b) = (a + 1)(b + 1) = ab + a + b + 1 J
167
Demonstração. Seja n tal que f(n) 6= 0. Então f(n) = f(n · 1) = f(n)f(1), o
que implica que f(1) = 1.
φ(6) = 2, φ(5) = 4,
d(6) = 4, d(5) = 2,
σ(6) = 12, σ(5) = 6.
φ(30) = φ(6 · 5)
= φ(6)φ(5)
=2·4
= 8.
Verificamos os divisores.
d(30) = d(6 · 5)
= d(6)d(5)
=4·2
= 8.
Quanto à função σ,
σ(30) = σ(6 · 5)
= σ(6)σ(5)
= 12 · 6
= 72,
168
Demonstração. Sejam a, b ∈ Z, com mdc (a, b) = 1. Suponha que as fatora-
ções de a e b sejam
a = pα1 α2 αr
1 p2 · · · pr
b = qβ1 β2 βs
1 q2 · · · qs ,
d(ab) = d(a)d(b).
Para σ, temos
X X X
σ(ab) = d= s t
d|ab s|a t|b
= σ(a)σ(b).
169
funções multiplicativas,
X
f(n) = φ(n)
d|n
g(n) = n
φ(pa ) = pa − pa−1 .
Agora temos
X X
a
f(pa ) = φ(pa ) = φ(pi )
d|pa i=0
X
a
=1+ φ(pi )
i=1
X
a
=1+ pi − pi−1
i=1
= pa ,
Teorema 7.23. Todo número perfeito par pode ser escrito na forma 2n−1 (2n −
1), onde 2n − 1 é primo de Mersenne.
170
mdc k, 2n-1 = 1. Com isso, usamos o fato de σ ser multiplicativa:
σ(m) = σ(2n−1 k)
= σ(2n−1 )σ(k)
n−1
2
= σ(k)
2−1
= (2n − 1)σ(k). (7.1)
Como m é perfeito,
σ(m) = 2m
= 2n k.
k = (2n − 1)r.
k (2n − 1)r
≤ n
σk 2 (r + 1)
n
2 −1 q
=
2n q+1
2n−1
< .
2n
Mas isto contradiz , portanto r = 1 e 2n − 1 é primo de Mersenne.
171
7.2 Convolução de Dirichlet
A convolução de Dirichlet é uma forma de combinar funções.
Quando n = 1,
X
1
(δ ∗ δ)(1) = δ(d)δ
d
d|1
1
= δ(1)
1
= 1.
9 No corpo do texto, é a exposição mais intuitiva que podemos dar. Aqui, em nota de rodapé,
172
Quando n > 1,
X n
(δ ∗ δ)(n) = δ(d) δ
|{z} | {zd }
d|n nulo
para d>1 nulo
para d<n
= 0. J
Para que g seja inversa de f, precisamos que o valor (f ∗ g)(1) seja igual a
δ(1) = 1:
f(1)g(1) = 1
1
g(1) = ,
f(1)
X n
(f ∗ g)(n) = 0 = f(d)g
d
d|n
X n
0 = f(1)g(n) + f(d)g
d
d|n
d<n
1 X n
g(n) = − f(d)g
f(1) d
d|n
d<n
173
divisores de n, não são zero.
A demonstração indutiva também resulta em um método recursivo para de-
terminar a inversa g.
µ(1) = +1,
µ(p) = −1,
µ(p2 ) = 0.
Hardy, G. H.; Wright, E. M. An Introduction to The Theory of Numbers. 6. ed. [S. l.]:
Oxford, 2009.
174
Como exigimos na Definição 7.30 que µ seja multiplicativa, observamos que
que pode ser interessante usar a Definição 7.31 para µ. Note que a primeir
adefinição implica trivialmente nas propriedades descritas na segunda, por
exigir que µ seja multiplicativa – mas a que a segunda definição implica na
multiplicatividade não é trivial, e o demonstramos adiante (Teorema 7.33).
Exemplo 7.32.
µ(7) = (−1)1 = −1
2
µ(21) = µ(3 · 7) = (−1) = +1
µ(30) = µ(2 · 3 · 5) = (−1)3 = −1
2
µ(60) = µ(2 · 3 · 5) = 0
J
Teorema 7.33. A Definição 7.31, embora não o explicite, implica na pro-
priedade da multiplicatividade de µ, sendo portanto equivalente à Defini-
ção 7.30.
Demonstração. Sejam
a = pα1 α2 αs
1 p2 · · · ps
b = qβ1 β2 βt
1 q2 · · · qt
µ(a) = (−1)s
µ(b) = (−1)t ,
175
um dos αi é maior que um. Então µ(a) = 0. Mas se a tem um fator primo
elevado a potência maior que um, ab também tem. Assim,
µ(ab) = 0 = µ(a)µ(b).
Finalmente, se a = 1, então
µ(ab) = µ(1 · b)
= µ(b)
= 1 · µ(b)
= µ(a)µ(b).
µ(1) = +1
µ(2) = (−1)1 = −1
µ(3) = (−1)1 = −1
µ(6) = µ(2 · 3) = (−1)2 = +1
Temos então
X
µ(d) = µ(1) + µ(2) + µ(3) + µ(6)
d|6
176
Verificamos agora que a fórmula está correta para um único primo p, de
forma que n = pa . Como os divisores de pa são p0 , p1 , . . . , pa , então
X
µ(pa ) = µ(1) + µ(p) + µ(p2 ) + µ(p3 ) + · · · + µ(pa )
d|pa
= 1 − 1 + 0 + 0 + ··· + 0
= 0.
= 0.
177
Isto é o mesmo que determinar f(n) = n, e escrever
X
f(n) = φ(d).
d|n
φ(540) = φ(22 · 33 · 5)
= φ(22 ) · φ(33 ) · φ(5)
= 2 · 18 · 4
= 144.
X µ(d)
φ(540) = 540 .
d
d|540
178
Calculamos:
X µ(D)
φ(540) = 540 (D livre de quadrados)
D
D|540
µ(1) µ(2) µ(3) µ(5)
= 540 + + + +
1 2 3 5
µ(2 · 3) µ(2 · 5) µ(3 · 5) µ(2 · 3 · 5)
+ + +
2·3 2·5 3·5 2·3·5
1 1 1
= 540 +1 − 1 −1 −1
2 3 5
1 1 1 1
+1 +1 +1 −1
2·3 2·5 3·5 2·3·5
= 540 − 270 − 180 − 108 + 90 + 54 + 36 − 18
= 144. J
e na última equação,
X n X X
µ(a)g = g(a) µ(a),
d
a|n a|n d| n
d
P
temos a| n µ(d) igual a zero quando n/d > 1,
d
179
e igual a um quanto n = d, portanto
X n X
µ(d)g = g(n)
d
d|n n|n
= g(n),
P
e, partindo de 7.4, f(n) = d|n g(d), determinamos que
X
g(n) = µ(a)f(b).
ab=n
P a
Novamente, d|a µ d é zero quando a/d > 1 e um quando a = d:
X X a X
f(a) µ = f(n) 1 + f(n) 0
d
a|n d|a d|a
d<a
= f(n).
P
Estabelecemos, portanto, que f(n) = a|n g(a) (7.4), usando (7.5).
180
Exemplo 7.38. Alguns exemplos de pares de Moebius são
X
(n, φ(n)) : n = φ(d)
d|n
X
(d(n), 1) : d(n) = 1
d|n
X
(σ(n), id) : σ(n) = d J
d|n
= f(a)f(b).
181
Se f é multiplicativa,
X ab
g(ab) = µ(d)f
d
d|ab
XX
ab
= µ(ce)f (mdc (a, b) = 1)
ce
c|a e|b
XX a b
= µ(c)µ(e)f f (f, µ multiplicativas)
c e
c|a e|b
X a X
b
= µ(c)f µ(e)f
c e
c|a e|b
= g(a)g(b).
Exemplo 7.41.
b1/2c = 0 bec = 2
b3/2c = 1 bϕc = 1
j√ k
b−1/2c = −1 2 =1
b−3/2c = −2 j √ k
− 2 = −2
b3c = 3
bπc = 3 J
182
Por ser simétrico a bxc, não trataremos de dxe. O Teorema 7.43 lista algumas
propriedades de bxc, que são de simples verificação.
(b) bx + nc = bxc + n.
183
Demonstração. A soma sempre é finita, porque quando pi > n, n/pi = 0.
Claramente, os únicos primos que dividem n! são menores ou iguais que n.
O último deles é bn/pc.
Se visualizarmos n! como produto de inteiros, cada um com sua fatoração
única, teremos
n! = 1 · 2 · · · · (p1 p2 . . . pk ) · · · (n − 1)n,
Cada fator em n! contribui com algum pj . Se dividirmos n por p, estaremos
contando o número de vezes que p aparece com expoente ≥ 1 em n!. Ao
dividirmos por p2 , o número de vezes que aparece com expoente ≥ 2, e
assim por diante.
Assim, a soma
n n
+ + ···
p p2
contabiliza exatamente a soma dos expoentes de p em n!.
100!
(10!)10 11!
é inteiro.
Precisamos mostrar que, para cada potência de primo pr na fatoração do
denominador, existe um fator ps no numerador, com s ≥ b.
No denominador temos
184
Agora, para 11!:
11 10 10
ord2 (11!) = + 2 + 3 =5+2+1=8
2 2 2
11 10
ord3 (11!) = + 2 =3+1=4
3 3
11
ord5 (11!) = =2
5
11
ord7 (11!) = =1
7
11
ord11 (11!) = =1
11
ord2 (10!10 ) = 80
ord3 (10!10 ) = 40
ord5 (10!10 ) = 20
ord7 (10!10 ) = 10
ord2 (D) = 80 + 8 = 88
ord3 (D) = 40 + 4 = 44
ord5 (D) = 20 + 2 = 22
ord7 (D) = 10 + 1 = 11
ord11 (D) = 1
185
Verificamos se temos o necessário no numerador, N = 100!:
100 100 100 100 100 100
ord2 (100!) = + + + + +
2 22 23 24 25 26
= 50 + 25 + 12 + 6 + 3 + 1
= 97
> 88.
100 100 100 100
ord3 (100!) = + + +
3 32 33 34
= 33 + 11 + 3 + 1
= 48
> 44.
100 100
ord5 (100!) = +
5 52
= 20 + 4
= 24
> 22.
100 100
ord7 (100!) = +
7 72
= 14 + 2
= 16
> 11.
100
ord11 (100!) =
11
=9
> 1.
7.4 π(n)
A função π(n) dá o número de primos menores ou iguais a n. Por exemplo,
π(2) = 1 π(7) = 4
π(3) = 2 π(8) = 4
π(4) = 2 π(9) = 4
π(5) = 3 π(10) = 4
π(6) = 3 π(11) = 5
12 N/D = 5904968808604507115824213572133292476575768202778243210230806239411719226124080755200.
186
O Teorema 7.47 explicita uma relação entre π(n) e φ(n),
π(n) ≤ k + r + (s − 1)φ(k)
π(n) ≤ 2k + (s − 1)φ(k)
π(n) ≤ 2k + sφ(k)
lxm
π(n) ≤ 2k + φ(k)
k
187
ção do Teorema de Chebytchev incluída aqui depende de um Teorema con-
jecturado por Bertrand em 1845, e demonstrado por Chebychev em 1852.
Para cada inteiro n e primo p, definimos como rp o expoente tal que prp ≤
2n e prp +1 > 2n.
O Lema 7.48 estabelece o fundamento para nossa demonstração do Teo-
rema de Chebychev a respeito do crescimento de π(n).
Y
2n
Y
p pr p ,
n
n<p<2n p<2n
então p está na fatoração de 2n!, porque é menor que 2n, mas não está na
fatoração de n!n!, porque é maior que n.
Q
Já para o lado direito, 2n
n | p<2n prp ,
X
rp
2n
ordp (2n!) =
pi
i=1
X
rp
n
ordp (n!n!) = 2 ordp (n!) = 2
pj
j=1
X rp
2n 2n n
ordp = −2
n pi pi
i=1
X
rp
≤ 1
i=1
= rp .
188
Com estes resultados já é possível demonstrar o Teorema de Chebychev.
Q
Agora, compare número nπ(2n)−π(n) com n<p<2n p
nπ(2n)−π(n) = n · n · n · · · n
Y
p = p1 · p2 · · · pk
n<p<2n
rpi
Há π(2n) fatores nas duas expressões, e cada pi é menor que 2n, portanto
Y
prp ≤ (2n)π(2n) .
p<2n
Y
2n
Y
nπ(2n)−π(n) ≤ p ≤ ≤ prp ≤ (2n)π(2n)
n
n<p<2n p<2n
189
Observamos que
2n
≥ 2n
n
2n
log ≥ n log(2) (log)
n
n
π(2n) − π(n) ≤ 2 log(2)
log(n)
190
2k < n ≤ 2k+1 para algum k. Então
k
π(n) ≤ π(2k+1 ) (n ≤ 2 2 +1
)
k
2
≤6 (por (7.7))
k+1
log(2)2k
=6
log(2)(k + 1)
2k
= 6 log(2)
log(2)k + log(2)
2k
=B log(2)k + log(2) (B = 6 log 2)
log(2)k
2k
<B
log(2)k
2k
=B
log(2k )
n
≤B . (2 k < n )
log n
n
Mostramos, portanto, que π(n) < B log(n) , e a demonstração termina aqui.
Exercícios
Ex. 168 — Determine σ(pn ) e d(pn ), onde p é primo e n ∈ N.
Ex. 169 — Determine forma fechada para σ(n) e d(n), a partir da fatoração
de n.
√
Ex. 170 — Mostre que, se n é composto, σ(n) > n + n.
191
Ex. 176 — Resolva:
a) φ(n) = 12
b) φ(n) = n/2
c) φ(φ(n)) = 220 38
X
n j n k
M = 1.
i
i=1
X µ2 (d)
n = φ(n) .
φ(d)
d|n
Prove que X
f(n) = (−1)p(n/d) g(d),
d|n
n livre de quadrados
Ex. 183 — Prove que se f(n) é uma função aritmética multiplicativa, então
192
Prove que
φ(n) φ(rad(n))
= .
n rad(n)
Y pa+1 − 1
σ(n) = .
p−1
d|n
193
Qual é a cardinalidade da imagem de f(x)?
a) φ(3a 5b ) = 360
b) φ(n) = 16
Y 1
X µ(d)
1− = .
p d
p|n d|n
µ(1) = 1
X
µ(d) = 0, ∀n ∈ N, n > 1.
d|n
Ex. 199 — Prove que a soma dos números k menores que n, tais que mdc (k, n) =
1, é
nφ(n)
.
2
194
Ex. 200 — Prove que se n = n1 + n2 + · · · + nk então
n!
∈ Z.
n1! · n2! · · · nk !
X
bxc
x
g(x) = f
j
j=1
se e somente se
X
bxc
x
f(x) = µ(j)g .
j
j=1
2k
π(2k ) ≤ 3 .
k
Mostre os detalhes.
X
n
(j − 1)! + 1
(j − 1)!
π(n) = −
j j
j=2
√ X
n
X
n
X n
π(n) = π n − 1 + bnc − + − + ···
pi pi pj pi pj pk
i i<j i<j<k
195
de µ(k) para todo k ≤ n:
X
M(n) = µ(k).
1≤k≤n
Por exemplo,
196
Capítulo 8
Sistemas de Resíduos
197
8.1 Sistemas completos e reduzidos de resíduos
Se a ≡ b (mod m), dizemos que a e b representam o mesmo resíduo mó-
dulo m. Por exemplo, como 25 ≡ 4 (mod 7), então 4 e 25 são o mesmo
resíduo módulo 7. A palavra resíduo significa “resto de divisão” – veja que
4 é o resto de 25 ÷ 7, e também é o resto de 4 ÷ 7.
0≡0 (mod 4)
5≡1 (mod 4)
10 ≡ 2 (mod 4)
15 ≡ 3 (mod 4).
1≡1 (mod 4)
3≡3 (mod 4).
198
O Lema 8.3 garante que se um elemento a é parte de um sistema reduzido
de resíduos, toda a sua classe de equivalência também é, porque toda ela
será co-prima com o módulo.
m | (a − b)
km = a − b
a = km + b
mdc (a, m) = mdc (km + b, m)
1 = mdc (km + b, m)
1 = mdc (b, m) .
23 ≡ 9 (mod 14),
25 ≡ 11 (mod 14),
199
ter representante de sua classe de congruência no sistema, e há pelo menos
φ(m) deles, como já demonstrado na parte (i).
d | ari
d|m
Mas como mdc (ri , m) = 1, d não poderia dividir tanto m como ri , logo d deve
dividir a e m – mas mdc (k, m) = 1, e d não pode ser diferente de um.
200
números ari :
Y
φ(m)
Y
φ(m)
ari ≡ ri (mod m)
i=1 i=1
Y
φ(m)
Y
φ(m)
aφ(m) ri ≡ ri (mod m)
i=1 i=1
Mas como mdc (ri , m) = 1 para todos os ri , podemos usar a lei do cancela-
mento, eliminando os ri , e reescrevemos
Fermat enunciou este Teorema sem demonstração em 1640, ainda sem usar
a linguagem de congruências (o que afirmou é que se p é primo e a não é
divisível por p, então ap−1 − 1 é divisível por p). A demonstração foi dada
por Euler em 1736; a generalização de Euler foi publicada em 1763.
201
8.2 Raízes primitivas
Considere o sistema completo de resíduos Z10 = {0, 1, 2, . . . , 9}. Se tomarmos
o número 3, e o multiplicarmos iteradamente, vemos que
31 = 3 ≡3 (mod 10)
2
3 =9 ≡9 (mod 10)
3
3 = 27 ≡7 (mod 10)
34 = 81 ≡1 (mod 10)
5
3 = 243 ≡3 (mod 10)
6
3 = 729 ≡9 (mod 10)
7
3 = 2187 ≡7 (mod 10)
..
.
21 = 2 ≡2 (mod 10)
2
2 =4 ≡4 (mod 10)
3
2 =8 ≡6 (mod 10)
4
2 = 16 ≡8 (mod 10)
5
2 = 32 ≡2 (mod 10)
26 = 64 ≡4 (mod 10)
..
.
202
uma potência de 3 é congruente a 1 módulo 10. Isto nos leva à definição de
ordem de um elemento em um sistema de resíduos.
31 = 3 ≡3 (mod 14)
2
3 =9 ≡9 (mod 14)
3
3 = 27 ≡13 (mod 14)
4
3 = 81 ≡11 (mod 14)
35 = 243 ≡5 (mod 14)
6
3 = 729 ≡1 (mod 14)
7
3 = 2187 ≡3 (mod 14)
203
que se repete. Temos adiante uma ilustração: na primeira linha, os gi ,
onde g é raiz primitiva para algum módulo m; na segunda linha, aj < m
representa a classe de congruencia de gi .
Fica claro, então, que se gi ≡ 1 (mod m), então gki também será congru-
ente a 1 módulo m. No entanto, não provamos que de fato este comporta-
mento sempre acontece. O Teorema 8.11 trata disso, capturando portanto
a característica de repetição da sequência de potências módulo m.
k = qh + r, 0 ≤ |r| < h.
1 ≡ ak (mod m)
≡ aqh+r (mod m)
h q r
≡ (a ) a (mod m)
q r
≡ (1) a (mod m)
r
≡a (mod m)
91 = 9 ≡ 9 (mod 14)
2
9 = 18 ≡ 4 (mod 14)
3
9 = 729 ≡ 1 (mod 14).
Mas sabemos, pelo Teorema de Euler, que 96 ≡ 1 (mod 14). E como deter-
mina o Teorema 8.11, 3 | 6.
Uma raiz primitiva gera um conjunto de números. O próximo Teorema iden-
tifica este conjunto – é um sistema reduzido de resíduos módulo m.
204
Teorema 8.12. Se g é raiz primitiva módulo m, então g, g2 , . . . , gφ(m) são
um sistema reduzido de resíduos módulo m.
Demonstração. Demonstramos que os gi são (i) incongruentes entre si, e
(ii) co-primos com m.
Começamos com a incongruência dos gi . Suponha que existam dois elemen-
tos gs ≡ gt (mod m), com 1 ≤ s < t ≤ φ(m). Então
m | (gt − gs )
m | (gt−s+s − gs )
m | (gt−s gs − gs )
m | gs (gt−s − 1).
Mas como g é raíz primitiva módulo m, o Teorema 8.9 garante que mdc (g, m) =
1, e mdc (gs , m) = 1. Concluímos que m - gs , e por isso
m | (gt−s − 1)
gt−s ≡ 1 (mod m)
Então t − s < φ(m), e gt−s ≡ 1 (mod m). Mas como g é raiz primitiva, φ(m)
deveria ser o menor expoente de g congruente a 1 módulo m – e chegamos
a uma contradição.
Assim, todos os gi do enunciado são incongruentes módulo m.
Passamos a outra parte da demonstração, os gi são co-primos com m. No-
vamente pelo Teorema 8.9, mdc (g, m) = 1, e evidentemente mdc gk , m = 1
também, o conjunto é um sistema reduzido de resíduos.
31 ≡ 3 (mod 10)
32 ≡ 9 (mod 10)
3
3 ≡7 (mod 10)
4
3 ≡1 (mod 10)
205
jh),
ajh ≡ (aj )r
≡ 1r
≡ q (mod m).
h | kj
Mas como agora (i) é co-primo com (ii), então a relação vale se e somente
se (i) | k:
h
k.
mdc (j, h)
Assim, o menor posistivo n tal que (aj )n ≡ 1 (mod m) é h/ mdc (j, h).
51 ≡ 5 (mod 26)
52 ≡ 25 (mod 26)
3
5 ≡ 21 (mod 26)
4
5 ≡1 (mod 26)
206
Corolário 8.14. Se g é raiz primitiva módulo m, então gk também é raiz
primitiva módulo m se e somente se mdc (k, φ(m)) = 1.
φ(m)
,
mdc (k, φ(m))
51 ≡ 5 (mod 18)
5
5 ≡ 11 (mod 18)
Demonstração. Suponha que haja raízes primitivas, e que g seja uma delas.
Há φ(m) elementos no sistema reduzido de resíduos g, g2 , . . . , gφ(m) . O
Corolário 8.14 determina que gk é raiz primitiva módulo m se e somente se
k é co-primo com φ(m). Existem φ(φ(m)) elementos assim.
207
8.3 Raízes primitivas com módulo primo
Apesar de não termos demonstrado o Teorema 8.16 (das raízes primiti-
vas), podemos facilmente provar que sempre há raízes primitivas módulo
p quando p é primo. De fato, já o fizemos!
Teorema 8.17. Sempre há raízes primitivas quando o módulo é primo.
gp−1 ≡ +1 (mod p)
p−1
g 2 ≡ −1 (mod p)
26 = 64 ≡ 16 ≡ −1 (mod 13)
12
2 = 4096 ≡ +1 (mod 13)
8.4 Grupos
Um grupo é uma estrutura algébrica com uma única operação3 . Os sistemas
de resíduos de que tratamos são exemplos de grupos – e demonstraremos
3 A idéia de grupo foi concebida em trabalhos que investigavam solubilidade de equações,
208
nesta seção o Teorema de Euler usando alguns fatos básicos sobre grupos.
Definição 8.19 (grupo). Um grupo é um conjunto onde está definida uma
operação binária, que por ora denotaremos , tal que
(i) é associativa;
nar que a multiplicação não gerará uma matriz fora do conjunto que especificamos.
209
• Seja (R, +, ·) um anel. Se considerarmos somente a operação de adição
em R, temos um grupo (isto segue diretamente da definição de anel).
xa = x
| · x ·{zx · · · x} .
a−1 operações
(xa )b = xab ,
xa+b = xa xb .
(a(b(x)) = (ab)x,
(a + b)x = ax + bx.
G = {e, a, b, c}
210
e dada pela tabela a seguir.
e a b c d
e e a b c d
a a b c d e
b b c d e a
c c d e a b
d d e a b c
c5 = c c c c c
=a c c c
=d c c
=b c
= e.
Da mesma forma,
c2 = c c
= a,
3
c =c c c
=a c
= d,
portanto c2 c3 = a d = e.
Observamos também que o grupo é comutativo, porque a tabela é simétrica.
J
O Teorema 8.11 pode ser visto como caso particular do Teorema 8.24, para
211
grupos.
Teorema 8.24. Seja x um elemento de ordem n em um grupo, e suponha
que xk = 1, com k inteiro positivo. Então n | k.
Demonstração. Expresse a divisão de k por n como k = nq + r, com q, r
inteiros positivos e 0 ≤ r < n. Então
1 = xk
= xnq+r
= (xn )q xr
= xr ,
então r = 0 e n | k.
212
Para cada período k, a ordem de 10k módulo p é k:
101 = 10 ≡1 (mod 3)
6
10 = 1000000 ≡1 (mod 7)
2
10 = 100 ≡1 (mod 11)
6
10 = 1000000 ≡1 (mod 13)
16
10 = 10000000000000000 ≡1 (mod 17)
34 = 81 ≡1 (mod 5)
6
3 = 729 ≡1 (mod 7)
5
3 = 243 ≡1 (mod 11)
3
3 = 27 ≡1 (mod 13)
16
3 = 43046721 ≡1 (mod 17)
213
um grupo com a operação de multiplicação – um subgrupo do grupo das
matrizes não singulares.
aφ(n) ≡ akt
≡ (at )k
≡ 1k
≡1 (mod n).
Definição 8.31 (grupo de unidades módulo n). Para todo inteiro positivo
n, definimos o grupo de unidades módulo n como o subconjunto de Zn
onde todos os elementos são unidades módulo n; a operação de grupo é a
multiplicação módulo n. Denotamos este grupo por Un .
Teorema 8.34. Seja n um inteiro positivo. Então Zφn é grupo com a ope-
ração de multiplicação; além disso, Un é isomorfo a Zφn .
214
8.5 Raízes da Unidade
5 Abraham de Moivre (1667-1754, francês, mudou-se para a Inglaterra ainda jovem devido a
perseguição religiosa – a prática do protestantismo cristão foi declarada ilegal pelo impoerador
Luís XIV) publicou, por volta de 1730, um artigo onde constrói a fórmula6 que hoje tem seu
nome,
(cos θ + i sen θ)n = cos(nθ) + i sen(nθ),
que permitiu a obtenção das raízes n-ésimas de 1, com θ = 2kπ/n. A publicação se chamava
Miscellanea Analytica.
De Moivre, Abraham. Miscellanea Analytica de Seriebus et Quadraturis. Londres: J.
Tonson & J. Watts, 1730.
De Moivre não incluiu a fórmula como a conhecemos no texto; ela pode ser derivada do pri-
meiro lema do livro (na página um), que usava idéias de seu amigo pessoal, Isaac Newton.
Posteriormente, Euler (1707-1783) apresentou a conhecida fórmula exponencial,
215
√ +i
−1+i 3
2
+1 −1 +1
√
−1−i 3
2
−i
+1
7 Gauss estudou as raízes da unidade e sua relação com a construção de polígonos regulares,
216
Agora, 1 elevado a qualquer potência permanece 1, logo
r r
e2iπ = e2iπ = 1r = 1.
2niπ 2(1)niπ
e n = e2iπ = 1 = e 1 .
ω1
ω2
ω0 = ω5 = ω5k = +1
ω3
ω4
217
Para todo k ∈ Z:
ω0 = ω5k
ω1 = ω5k+1
ω2 = ω5k+2
ω3 = ω5k+3
ω4 = ω5k+4
Ou seja, para todo inteiro sj ∈ {0, 1, . . . , n − 1} temos que ωtj será igual a
um ωsj diferente. Como são exatamente n as n-ésimas raízes da unidade,
então o conjunto de expoentes {t0 , . . . , tn−1 } gera todas elas.
Falta mostrarmos que se os ωti são exatamente as n raízes n-ésimas da
unidade, então os ti formam um sistema completo de resíduos.
Suponha que {t0 , . . . , tn−1 } não é sistema completo de resíduos módulo n.
Como há n elementos, isso significa que deve haver dois elementos no con-
8 Uma rotação por θ radianos é obtida ao multiplicar um núero complexo por eiθ ; assim, a
218
junto que são congruentes módulo n: tu ≡ tv (mod n), ou seja, para algum
k,
tu = nk + tv .
Assim teremos
ωtu = ωnk+tv = ωtv ,
e não teremos todos os n distintos ωti .
√ √ √ √
−1+i 3 +1+i 3 −1+i 3 +1+i 3
2 2 2 2
−1 +1 −1 +1
√ √ √ √
−1−i 3 +1−i 3 −1−i 3 +1−i 3
2 2 2 2
219
ordenadas, como observamos), definindo assim um polígono simétrico nos
dois eixos.
Dentre as raízes sextas da unidade há duas que são primitivas,
√
+1 ± i 3
,
2
e as outras são também raízes n-ésimas para n < 6:
+1 n=1 (8.1)
−1 n=2 (8.2)
√
−1 ± i 3
n=3 (8.3)
2
√ √
−1+i 3 +1+i 3
2 2
−1 +1
√ √
−1−i 3 +1−i 3
2 2
220
1 × 12 2×6
3×4 4×3
6×2 12 × 1
mdc (k, n) = 1.
2kiπ
e n , k = 1, 2, . . . , n,
221
A quantidade de n-ésimas raízes primitivas da unidade é, portanto, φ(n).
A intuição nos indica que um análogo do Teorema 8.39 deve valer para
sistemas reduzidos de resíduos, e portanto enunciamos o Teorema 8.43 (de-
monstração pedida no Exercício 244). As mudanças realizadas a partir do
enuncaiado do Teorema 8.39 estão sublinhadas.
Exercícios
Ex. 211 — Prove que em uma lista de k + 1 números a1 , a2 , . . . , ak+1 há
pelo menos dois números, ai e aj , tais que (ai − aj ) | k.
Ex. 214 — Suponha que an−1 ≡ 1 (mod n) mas que, para todo d divisor
próprio de n − 1, ad 6≡ 1 (mod n). Prove que n é primo.
222
Ex. 219 — Prove que se p é um primo ímpar e a tem ordem 2k módulo p,
então ak ≡ −1 (mod p).
Ex. 220 — Prove que o conjunto dos inteiros módulo m, para todo m ≥ 0,
é um grupo comutativo com a operação de soma módulo m.
e a b c d
e e a b c d
a a e c d b
b b d e a c
c c b d e a
d d c a b e
Ex. 224 — Seja p um primo ímpar, e sejam {s1 , s2 , . . . , sp−1 } e {t1 , t2 , . . . , tp−1 }
dois sistemas completos de resíduos módulo p. Prove que {s1 t1 , s2 t2 , . . . , sk tk }
não pode ser sistema completo de resíduos módulo p.
Ex. 229 — Sejam a, b co-primos. Prove que {0, a, 2a, 3a, . . . , (b − a)a} é um
sistema completo de resíduos módulo b.
Ex. 231 — Prove que para todo inteiro positivo n maior que um, n | φ(2n −
1).
223
módulo p. Prove que para todo inteiro n existe r tal que
X
r
n= xi pi (mod pr+1 ),
i=0
Ex. 233 — Suponha que p > 3 seja primo. Prove que o produto das raízes
primitivas entre 1 e p − 1 módulo p é congruente a 1 módulo p.
Ex. 234 — Prove que se mdc (a, b) = 1 e a ordem de a módulo b é ts, então
a ordem de bs em a é t.
Ex. 235 — Dois grupos (G, ) e (H, ) são isomorfos se existe uma bijeção
entre eles que preserva estrutura – ou seja, se existe f : G → H bijetora tal
que ∀a, b ∈ G, f(a b) = f(a) f(b).
(a) Prove que os grupos aditivos definidos por dois sistemas completos de
resíduos com o mesmo módulo são isomorfos, e que por isso podemos
tratá-los como se fossem um só: “o sistema completo de resíduos mó-
dulo m”.
(b) Faça o mesmo com grupos multiplicativos definidos por sistemas redu-
zidos de resíduos.
Ex. 236 — Suponha que g seja raiz primitiva módulo pk . Prove que g tam-
bém é raiz primitiva módulo p.
Ex. 238 — Prove que em qualquer grupo, todo elemento tem um único in-
verso.
C = {(x, y) | x2 + y2 = 1}.
224
i) S é a união de φ(m)/φ(d) conjuntos distintos, cada um sendo um sis-
tema reduzido de resíduos módulo d;
ii) S é a união de φ(d) conjuntos distintos, cada um tendo tamanho φ(m)/φ(d)
números congruentes uns aos outros módulo d.
Ex. 241 — Prove que a soma das n-ésimas raízes da unidade (não somente
as primitivas) é zero.
Ex. 243 — Prove que se p é primo e existe uma n-ésima raiz primitiva da
unidade em Zp , então n | (p − 1).
10 Este Teorema foi demonstrado por Gauss no Disquisitiones (no artigo 81).
Gauss, Johann Carl Friedrich. Disquisitiones Arithmeticae. [S. l.], 1801.
Gauss não usou a fórmula de inversão de Möbius, mas é possível usá-la. Na verdade, Gauss
não usa a função de Möbius em nenhuma outra passagem do Disquisitiones, que foi publicado
inicialmente em 1801 (trinta e um anos antes de Möbius publicar o tratamento sistematizado
da fórmula de inversão em 1832).
225
226
Capítulo 9
Resíduos Quadráticos
227
Demonstração. Se a é resíduo quadrático módulo p, então
p−1 p−1
a 2 ≡ (x2 ) 2 (mod p)
p−1
≡x (mod p)
≡1 (mod p). (pelo Teorema de Euler)
p−1
Agora suponha que a 2 ≡ 1 (mod p). Como p é primo, deve haver alguma
raiz primitiva g módulo p, e existe algum k tal que gk ≡ a (mod p). Agora
reescrevemos a congruência do enunciado,
p−1 p−1
(gk ) 2 ≡a 2 (mod p)
Notamos que a sequência se repete duas vezes. Temos somente que mostrar
que estes são todos incongruentes modulo p Suponha que r2 e s2 sejam
congruentes módulo p. Mas se r2 ≡ s2 (mod p), então e r2 −s2 ≡ 0 (mod p),
228
ou seja, (r + s)(r − s) ≡ 0 (mod p), e r ≡ ±s (mod p).
229
• se (a/p) = 1, então a é quadrado módulo p; mas se b ≡ a (mod p),
então b ≡ a ≡ x2 (mod p), e (b/p) = 1;
Assim, nos três casos (quando (a/p) = −1, 0 + 1), o enunciado vale.
230
Lema 9.8. Se p é primo ímpar,
+1 se p = 4k + 1,
−1
=
p −1 se p = 4k + 3.
Seção IV, art. 131. O texto não tem capítulos, apenas “seções”, e no estilo usado por Gauss
(Gauß), o texto é uma sequência de “artigos”, cada um compreendendo alguns parágrafos. O
próprio Gauss discute, no artigo 151, a história do Teorema.
2 Não quando o enunciou no Disquisitiones, mas informalmente em correspondências.
3 Dois livros sobre demonstrações da reciprocidade quadrática:
Lemmermeyer, Franz. Reciprocity Laws: from Euler to Eisenstein. [S. l.]: Springer,
2000.
Pag. 216.
231
duo de qualquer número primo que, tomado positivamente, é um resíduo ou
não resíduo de p. Se p for da forma 4n + 3, −p terá a mesma propriedade5 .
No parágrafo seguinte, Gauss justifica ter nomeado este fato como “Teo-
rema Fundamental”:
Como quase tudo o que pode ser dito sobre os resíduos qua-
dráticos se baseia neste teorema, a denominação de teorema fun-
damental, que utilizaremos a seguir, não estará fora de lugar6 .
x2 ≡ q (mod p)
x2 ≡ p (mod q)
Si p est numerus primus formae 4n+1, erit +p, si vero p formae 4n+3, erit −p residuum vel non
residuum cuinsuis numeri primi qui positive acceptus ipsius p est residuum vel non-residuum.
6 Quia omnia fere quae de residuis quadraticis dici possunt, huic theoremati innituntur, de-
uma demonstraçõa incompleta do Teorema em 1788. Um artigo sobre os estudos feitos por
Legendre:
Weintraub, Steven H. On Legendre’s Work on the Law of Quadratic Reciprocity. The Ame-
rican Mathematical Monthly, v. 118, n. 3, p. 210–216, 2011.
8 Poderíamos também dizer:
• Se p e q forem da forma 4k + 3:
– p ∈ Qq e q ∈
/ Qp , ou
– p∈
/ Qq e q ∈ Qp .
– p ∈ Qq e q ∈ Qp , ou
– p∈
/ Qq e q ∈
/ Qp .
232
seu símbolo9 .
Teorema 9.13 (Lei da Reciprocidade Quadrática). Sejam p 6= q dois primos
ímpares. Então
p q
= ,
q p
exceto quando p e q são da forma 4k+3, quando vale a negação da igualdade
acima.
Considere a expressão
p−1 q−1
(−1) 2 2 ,
analisando as possibilidades para os expoentes:
p−1 q−1
p, q 2 2 paridade valor
4k + 1, 4j + 1 (4k)(4j)
4 = 4kj par +1
4k + 3, 4j + 3 (4k+2)(4j+2)
4 = 4kj + 2j + 2k + 1 ímpar −1
4k + 3, 4j + 1 (4k+2)(4j)
4 = 16kj + 8j par +1
233
E realmente, 182 ≡ 11 (mod 3)13. J
3∗
−3 2 5
= = = −1 = .
5 5 5 3
Agora suponha q > 5, e suponha que (s∗ /r) = (r/s) para todos os pares de
primos distintos r, s menores que q. O passo é feito em três casos:
Flath, Daniel. Introduction to Number Theory. [S. l.]: John Wiley e Sons, 1989.
234
A partir de (i), (ii) e (iii), conclua a validade da Lei da Reciprocidade Qua-
drática.
Z∗p = {1, 2, . . . , p − 1}
Z∗q = {1, 2, . . . , q − 1}
Claramente, |Z∗pq | = |Z∗p | |Z∗q |, e como mdc (p, q) = 1, o teorema chinês dos
restos13 determina que
f : Z∗pq → Z∗p × Z∗q ,
dada por
f(x) = (x, x)
11 George Rousseau, matemático do Século XX. Não é Jean-Jacques Rousseau (1712-1778),
filósofo e teórico político, que já não estava mais vivo quando Gauss elaborou a primeira de-
monstração do teorema.
12 A apresentação de Rousseau é bem mais compacta que a nossa – o corpo da demonstração
235
é bijetora.
Definimos agora dois conjuntos14 , ambos com metade do tamanho de Z∗pq :
pq q
E= 1<x< D = (a, b) : 1 < a < p, 1 < b <
2 2
Os dois conjuntos tem o mesmo tamanho, mas no conjunto D mantivemos
os valores 1, . . . p − 1 para a, e reduzimos os valores de b para 1, . . . q−1
2 – o
que reduz o tamanho do conjunto pela metade!
Ainda temos uma bijeção: para cada x ∈ E, há um único par ±(a, b). Desta
forma, temos que o produto dos pares (x, x), com x ∈ E deve ser idêntico ao
produto dos pares (a, b) ∈ D.
Y Y
(x, x) = ± (a, b), (9.1)
x∈E (a,b)∈D
No produtório dos pares (a, b), no lado esquerdo do par haverá o produto
dos valores de a entre 1 e p − 1 (portanto (p − 1)!), repetido (q − 1)/2 vezes,
portanto igual a
q−1
(p − 1)! 2
15
q−1
≡(−1) 2 (mod p). (Teorema de Wilson )
Mas
conjunto.
15 Teorema 6.17 (de Wilson): p é primo se e somente se (p − 1)! ≡ −1 (mod p).
236
E portanto,
O produtório é, portanto
Y Y q−1 p−1 p−1 q−1
(a, b) = = (−1) 2 , (−1) 2 (−1) 2 2 . (9.2)
(a,b)∈D a≤p−1
b≤(q−1/2)
Zpq = E ∪ −E.
q−1 p pq
p+ = .
2 2 2
|{z}
tamanho
de Zpq
q−1 p−1
Y
(p − 1)! 2 2 !
x≡ p−1
(mod p)
p−1
x∈P q 2 2 !
p−1
q−1 2 !
≡ (−1) 2
p−1
(mod p) (T. Wilson)
p−1
q 2 2 !
q−1
p−1
−1
≡ (−1) 2 q 2 (mod p) (simplificando)
q−1 p−1
≡ (−1) q 2
2 (mod p) (inverso de ±1 é ele mesmo)
q
(crit. Euler16 )
q−1
≡ (−1) 2 (mod p)
p
237
Por simetria, o mesmo ocorre módulo q, e temos os seguintes dois fatos:
Y q−1
q
x ≡ (−1) 2 (mod p)
p
x∈P
p−1 p
≡ (−1) 2 (mod q)
q
Y
q−1
q p−1
p
(x, x) = (−1) 2 , (−1) 2 (9.3)
p q
x∈E
se e somente se
p−1
a 2 ≡1 (mod p).
238
valência de x módulo m:
Exemplo 9.18. Temos por exemplo 3 ≡ 12 ≡ −6 (mod 9), mas LR9 (3) =
LR9 (12) = LR9 (−6) = 3. J
O Lema de Eisenstein estabelece uma relação importante entre dois primos
p e q e o símbolo de Legendre (q/p).
Lema 9.19 (de Eisenstein). Seja p um primo ímpar e q um ímpar positivo.
Então
Pj qu k
q
= (−1) p
,
p
com u = 2, 4, 6, . . . , p − 1
Exemplo 9.20.
5 2·5 4·5 6·5 8·5 10·5
= (−1)b 11 cb 11 cb 11 cb 11 cb 11 c
11
10 20 30 40 50
= (−1)b 11 cb 11 cb 11 cb 11 cb 11 c
= (−1)0+1+2+3+4
= +1.
P j qu k
Demonstração. Observando o somatório p , vemos que será útil defi-
nir
r(u) = LRp (qu),
239
a classe de equivalência módulo p no numerador.
Além disso,
(−1)r(u) r(u) (mod p)
é também par.
Agora observamos também que os (−1)r(u) r(u) são todos distintos módulo
p. Suponha que existam u e t, tais que (−1)r(u) r(u) ≡ (−1)r(t) r(t) (mod p).
Então teríamos
Calculamos
Y Y
r(u) ≡ qu
≡ 2q · 4q · 6q · · · (p − 1)q
p−1 Y
≡q 2 u (mod p).
P p−1
r(u)
(−1) ≡q 2
P
r(u) q
(−1) ≡ (mod p).
p
240
Ao analisar a demonstração de Eisenstein, Gauss observou que
qu qu r(u)
= + ,
p p p
Assim, Pj qu k
q
= (−1) p
.
p
q−1
2
1
1 2 p−1 p
241
q
2
1
1 2 p
2
1
1 2 a p
242
q
2
1
1 2 p−a a p
D C
2
1
A 1 2 p−a B a p
X qu
≡ α (mod 2).
p
Para verificar que isto vale, observamos que ao contar as paridades das
colunas com abscissa par abaixo da diagonal, contamos as colunas pares
243
dentro de ABC, e também as colunas pares após B – mas para cada uma
dessas, há uma coluna ímpar em ABC.
Com este resultado, chegamos de imediato a
q
= (−1)α .
p
(p − 1) (q − 1)
α+β= ,
2 2
o que nos dá imediatamente a Lei da Reciprocidade Quadrática:
p q
= (−1)α (−1)β = (−1)(p−1)(q−1)/4 .
q p
Pag 212.
244
evitentemente igual a p.
Se p - z, então
X
p−1
ζzp − 1
ζzt = = 0,
ζz − 1
t=0
porque ζzp = 1.
X
p−1
t
gk = ζkt .
p
t=0
Também denotamos
g = g1 .
Exemplo 9.24. Sejam p = 3 e ζ = e2iπ/3 . Então, fixados ζ e p, escolhemos
k=2e
X
2
t
g2 = ζt
p
t=0
0 0 1 1(2) 2
= ζ + ζ + ζ2(2)
3 3 3
= 0ζ0 + 1ζ2 − 1ζ4
√ !2 √ !4
−1 + i 3 −1 + i 3
= −
2 2
√
= −i 3. J
Lema 9.25.
k
gk = g.
p
Demonstração. Se p | k, então os dois lados da equação são zero. O lado
esquerdo é:
X
p−1
t
gk = ζkt
p
t=0
X
p−1
t
= 1,
p
t=0
245
mas como a quantidade de resíduos quadráticos e não quadráticos módulo
p é a mesma, os termos (t/p) se anulam.
O lado direito é
k
g,
p
mas como p | k, o símbolo de Legendre (k/p) é sempre zero.
Consideramos agora o caso em que p - k. Então (k/p) será sempre +1 ou
−1, e
2
k
= 1.
p
Assim,
X
p−1
t
gk = ζkt
p
t=0
Xt
2 p−1
k
= ζkt (multiplicando por 1 = (k/p)2 )
p p
t=0
k X
p−1
kt
= ζkt (propriedade do símbolo de Legendre)
p p
t=0
k X
p−1
r
= ζr (9.4)
p p
r=0
k
= g.
p
Seja
p∗ = (−1)(p−1)/2 p.
Assim como na seção 9.2.1, esta definição resulta que p∗ será igual a p, mas
com sinal +1 se p é da forma 4k + 1 ou sinal −1 se p é da forma 4k + 3.
Também é verdade que
∗ −1
p = p = (−1)(p−1)/2 p.
p
246
Teorema 9.27. Se p - k, então g2 = p∗ .
Pp−1
Demonstração. Escrevemos t=0 gk g−k de duas maneiras diferentes.
Primeiro, se p - k, então
k −k −1
gk g−k = g2 = g2 ,
p p p
X
p−1
gk g−k = (p − 1)gk g−k
t=0
−1
= (p − 1) g2 . (9.5)
p
X X X a b X
gk g−k = ζk(a−b)
a
p p
k b k
X X a b
= δ(a, b)
a
p p
b
= (p − 1)p. (9.6)
247
Corolário 9.28. Seja p um primo ímpar.
√
Se p = 4k + 1 então g = ± +p, e g2 = p.
√
Se p = 4k + 3 então g = ± −p, e g2 = −p.
As operações são todas módulo p.
Até este ponto, Gauss tinha uma forma fechada para o quadrado da soma
(g2 ), mas não sabia qual das duas raizes quadradas era o valor de g – ou seja,
faltava determinar o sinal da soma de Gauss, g. Depois de muito tempo,
Gauss finalmente chegou a uma demonstração. O Teorema 9.29 determina
o sinal da soma de Gauss. A demonstração será omitida.
Lema 9.30.
k
gk (r) = g1 (r)
r
Mas 2
√
p−1
g=i 2
p,
248
portanto reescrevemos
q p
g1 (p) g1 (q) = g1 (pq)
p q
q p g1 (pq)
=
p q g1 (p)g1 (q)
2 2 2
pq−1
− p−1 − q−1
=i 2 2 2
p−1 q−1
= (−1) 2 2 .
Demonstração.
2
x2 ≡ ak+1
≡ a2k+2
≡ a2k+1 a
p−1
≡a 2 a (porque p = 4k + 3)
≡a (mod p). (critério de Euler)
249
resíduo quadrático módulo 11:
11−1
3 2 ≡ 35 ≡ 243 ≡ 1 (mod 11).
Verificamos:
52 ≡ 25 ≡ 3 (mod 11). (9.7)
y = x + tpk ,
x2 − a
t=− (mod pm ).
2xpk
72 ≡ 49 ≡ 4 (mod 5)
2 2
(−7) ≡ (3) ≡ 9 ≡ 4 (mod 5)
y = 3 + t5,
32 − 4
t≡− (mod 52 ).
2(3)5
250
Calculamos t:
5
t≡− ≡ −(6)−1 ≡ −126 ≡ 24 (mod 25).
6(5)
y = 3 + 24(5) = 123.
Verificamos que
1232 ≡ 15129 ≡ 4 (mod 53 ).
Demonstração.
x2 ≡ y (mod m)
m | x2 − y
pk | x2 − y (porque pk |m)
x2 ≡ y (mod pk )
251
Agora resolvemos os quatro sistemas,
Isto vale desde que mdc (2a, m) = 1 (porque usamos a lei do cancelamento,
multiplicando os dois lados por 2a). Quando o módulo é primo, 2a será
evidentemente co-primo com o módulo.
Resolveremos agora x2 − 6x + 5 ≡ 0 (mod 11). Temos
O critério de Euler nos garante que 5 é resíduo quadrático módulo 11, con-
forme já calculamos na seção anterior (equação9.7). A raiz de ∆ é, portanto,
252
Por último, fazemos uma verificação:
Exercícios
Ex. 247 — Calcule:
21 31 122 119
, , , .
11 3 23 7
x2 ≡ 10 (mod 43)
2
X ≡5 (mod 31)
2
3x − x + 1 ≡ 0 (mod 19)
x2 − x + 4 ≡ 0 (mod 29)
2
2x − 10 ≡ 0 (mod 23)
2
3x − 5 ≡ 0 (mod 18)
2
4x − 5 ≡ 0 (mod 25)
Ex. 250 — Um resíduo quadrático módulo p pode ser raiz primitiva módulo
pq, com p e q primos?
Ex. 253 — Prove que se p e q são primos ímpares tais que existe um x
253
inteiro positivo tal que p = q + 4x, então
x x
= .
p q
Ex. 254 — Prove que todo primo p maior que 3 divide a soma de seus re-
síduos quadráticos; e que todo primo p maior que 5 divide a soma dos qua-
drados de seus resíduos quadráticos.
Ex. 258 — Usando o Lema 9.9, prove que há infinitos primos da forma 8k+
7.
254
Ex. 267 — Prove que para n ímpar,
−1
= (−1)(n−1)/2
n
255
Lema 9.37. Seja p primo e a ∈ Z, tal que p - a. Seja também τ a permuta-
ção em Zp \ {0}, definida por
τa (k) = ak (mod p)
Então
a
= (τa ),
p
onde (τa ) denota o sinal da permutação τa .
Prove que o Lema de Zolotarev é equivalente ao Lema de Gauss (Lema 9.36).
O título se refere à “Lei de Reciprocidade de Legendre”, que é como a Lei da Reprocidade Qua-
drática também era conhecida (Legendre chegou a formular uma demonstração incompleta).
O enunciado do Lema de Zolotarev, no artigo (onde é um Teorema), é
Seja p um número primo ímpar. Dada uma sequência de números
1) 1, 2, 3, . . . , p − 1
(· · · )
Teorema I – Seja k um número inteiro qualquer não divisível por p. O caracter da
sequência
3) k, 2k, 3k, . . . , (p − 1)k,
se trocarmos os elementos por seus resíduos
com respeito ao módulo p, que são
k
encontrados na sequência (1), é igual a p
.
No original, em Francês,
Soît p un nombre premîer impair. Étant donnée une suite de nombres
1) 1, 2, 3, . . . , p − 1
(· · · )
Théorème I – Soit k un nombre entier quelconeque non divisible par p. Le ca-
ractère de la suite
3) k, 2k, 3k, . . . , (p − 1)k,
si l’on y remplace les éléments par leurs
résidus parrapport au module p qui se
k
trouvent dans la série (1), est égal a p
.
256
Capítulo 10
Soma de Quadrados
a2 + b2 = n,
tentando determinar quantas soluções tem (se existem), e quais são. Mos-
tramos também que todo inteiro pode ser representado como soma de qua-
tro quadrados.
Por exemplo, 109 tem representação própria como soma de dois quadrados,
já que 109 = 32 + 102 e mdc (3, 10) = 1.
Já 117 tem representação, mas não própria, porque 117 = 32 (13), e mdc (6, 9) =
3. A representação, imprópria, é 117 = 62 + 92 .
A interpretação geométrica do que significa um inteiro ser soma de dois
quadrados é relevante. A expressão x2 + y2 = n representa uma circun-
√
ferência de raio n centrada na origem. Um par (x, y) que represente n
257
é um ponto nesta circunferência. Contar a quantidade de representações
de n como soma de quadrados é o mesmo que contar os pontos inteiros na
circunferência.
√ Por exemplo, se n = 13 podemos visualizar a circunferencia
com raio 13 ≈ 3.605, e os pontos inteiros na circunferencia são
(−2, 3) (2, 3)
(−3, 2) (3, 2)
p−1
≡ (−1) 2 (a afirmação vale para todo quadrado...)
258
pode ser usado. Sabemos que (p − 1)! ≡ −1 (mod p). Então,
p+1
≤ x ≤ p − 1 se e somente se
2
p−1
− ≤ x − p ≤ −1. (subtraia p)
2
Portanto,
(−1)(−1) ≡ +1 (mod p)
2 2
(x )(x ) ≡ +1 (mod p)
x4 ≡ +1 (mod p),
259
Teorema 10.3. Um inteiro positivo n tem representação própria se e so-
mente se não tem fatores da forma 4k + 3.
x2 + y2 ≡ x2 + u2 x2 (mod p)
2 2
≡ x (1 + u ) (mod p)
≡0 (mod p). (p | n)
Exemplo 10.5. O número 275 = (11)52 contém uma potência ímpar de 11,
que é da forma 4k + 3, por isso não pode ser representado como soma de
dois quadrados.
O número 45 = (5)32 rem uma potência par de 3, que é obviamente da forma
4k + 3, e é representável por dois quadrados:
45 = 36 + 9
= 62 + 32 .
x/d = x 0 ⇒ x = dx 0
y/d = y 0
⇒ y = dy 0
260
Agora temos mdc (x', y') = 1. Seja
m = (x 0 )2 + (y 0 )2
x 2 y 2
= + .
d d
Assim, m é um inteiro com representação própria. Mas
p2r+1 | n
p2r+1 | x2 + y2
p2r+1−2j | (x 0 )2 + (y 0 )2 (divida por d2 )
n = ab2 ,
Lagrange, Joseph-Louis. Ouvres de Lagarange. Edição: M. J.-A Serret. [S. l.]: Gauthier
Villars, 1867. v. 3.
.
O artigo, “Démonstration d’un théorème d’arithmétique” está na página 189. Esta é uma
reprodução em uma coletânea. O original é
261
Teorema 10.6. Seja p primo. Então existem x, y, z inteiros, pelo menos um
deles diferente de zero, tais que
x2 + y2 + z2 ≡ 0 (mod p).
C’est un Théorème connu depuis longtemps que tout nombre entier non carré
peut toujours se décomposer en deux, ou trois, ou quatre carrés entiers; mais
personne, que je sache, n’en a encore donné la démonstration. M. Bachet de
Méziriac est le premier qui ait fait mention de ce Théorème; il paraît qu’il y
a été conduit par la question 31e du IV e Livre de Diophante, où le Théorème
dont nous parlons est en quelque sorte tacitement supposé; mais M. Bachet s’est
contenté de s’assurer de la vérité de ce Théorème par induction, en examinant
successivement tous les nombres entiers depuis 1 jusqu’à 325; et quant à la
démonstration générale, il avoue qu’il n’avait pas encore pu y parvenir.
O que Lagrange chama de “indução” não é a técnica que conhecemos – ele fala de verificar
vários casos particulares, e a partir disso supor que o caso geral vale.
Lagrange também menciona brevemente uma tentativa de Euler de demonstrar o teorema.
262
Temos portanto
x2 + y2 + z2 ≡ (d − 1) + (−d) + 1 (mod p)
≡0 (mod p).
Lema 10.8. Sejam α, β inteiros Gaussianos tais que α ≡ β (mod p). Então
αα ≡ ββ (mod p).
tem (k + 1)4 elementos. Como (k + 1)4 > p2 , pelo princípio da casa dos
pombos deve haver pelo menos dois destes números que são congruentes
módulo p. Sejam eles (a1 + b1 i) − (c1 + d1 i)(u + vi) e (a2 + b2 i) − (c2 +
d2 i)(u + vi). Agora, definimos
A = a1 − a2
B = b1 − b2
C = c1 − c2
D = d1 − d2 .
5 O enunciado, como originalmente declarado por Lagrange, é
Todo número inteiro não quadrado sempre pode ser decomposto em dois, tres,
ou quatro quadrados inteiros.
No original,
Tout nombre entier non carré peut toujours se décomposer en deux, ou trois,
ou quatre carrés entiers.
263
Sabemos que
|A|, |B|, |C|, |D| ≤ k,
porque a, b, c, d ≤ k. Além disso, nem todos são zero.
Tomamos A, B, C, D e escrevemos
Z ≤ 4k2 ≤ 4p
A ± B é par
C ± D é par
Então
2p = A2 + B2 + C2 + D2
A2 B2 C2 D2
p= + + +
2 2 2 2
2 2 2 2
A+B A−B C+D C−D
= + + + .
2 2 2 2
Como as somas nos numeradores são pares, as frações acima são todas
inteiras, e p é representável como soma de quatro quadrados.
264
Finalmente, quando t = 3,
3p = A2 + B2 + C2 + D2 .
3p = A2 + B2 + C2 + D2
3p = 9A 0 + 9B 0 + 9C 0 + 9D 0
9A 0 9B 0 9C 0 9D 0
p= + + +
3 3 3 3
p = 3A + 3B + 3C + 3D 0
0 0 0
p = 3w,
A ≡ ±1 (mod 3)
D≡0 (mod 3).
n1 = A + B + C
n2 = A − B + D
n3 = −A + C + D
n4 = B − C + D
265
Logo,
n 2 n 2 n 2 n 2
1 2 3 4
p= + + + ,
3 3 3 3
e completamos a demonstração.
266
Teorema 10.10 (de Gauss-Legendre). Um inteiro positivo é representável
como soma de três quadrados se e somente se não é da forma 4m (8k + 7).
Teorema 10.11. Todo inteiro positivo pode ser escrito como soma de três
números triangulares
7 Gauss demonstrou este teorema no Disquisitiones, usando o mesmo argumento.
Gauss, Johann Carl Friedrich. Disquisitiones Arithmeticae. [S. l.], 1801.
Artigo 293:
O argumento anterior também provê uma demonstração daquele famoso Teo-
rema: todo inteiro positivo pode ser decomposto em três números triangulares.
Foi descoberto por Fermat mas até agora não havia demonstração rigorosa para
ele. É manifesto que qualquer decomposição do número M em três números
triangulares
1 1 1
x(x + 1) + y(y + 1) + z(z + 1)
2 2 2
produzirá uma decomposiçào do número 8M + 3 em três quadrados ímpares
267
Demonstração. Considere a equação
8n + 3 = x2 + y2 + z2
x = 2a + 1
y = 2b + 1
z = 2c + 1
8n + 3 = x2 + y2 + z2
8n + 3 = (2a + 1)2 + (2b + 1)2 + (2c + 1)2
(2a + 1)2 + (2b + 1)2 + (2c + 1)2 − 3
n=
8
4a2 + 4a + 1 + 4b2 + 4b + 1 + 4c2 + 4c + 1 − 3
n=
8
4a2 + 4a + 4b2 + 4b + 4c2 + 4c
n=
8
4a(a + 1) + 4b(b + 1) + 4c(c + 1)
n=
8
a(a + 1) b(b + 1) c(c + 1)
n= + +
2 2 2
Pela demonstração dada no Exemplo8 2.5, n é a soma de três numeros tri-
angulares.
268
Demonstração. Provamos o caso n = 1 separadamente. Todo número é
congruente a zero módulo um, já que a divisão por um nunca deixa resto.
Assim, a equação u2 ≡ −1 (mod 1) tem uma única solução (a única classe
de congruências módulo um, representada pelo zero). Temos N(1) = 1, e o
número de representações de um é, portanto, 4N(1) = 4. De fato,
1 = (+1)2 + 02
= (−1)2 + 02
= 02 + (+1)2
= 02 + (−1)2
x2 + y2 ≡ x2 + (ux)2 (mod n)
≡ x2 (u + 1)2 (mod n)
≡0 (mod n)
Mas como x2 > 0, é necessário que (u+1)2 ≡ 0 (mod n), e u2 ≡ −1 (mod n).
Agora, para cada u com u2 ≡ −1 (mod n), se tomarmos y ≡ ux (mod n),
teremos
y ≡ ux (mod n)
2 2 2
y ≡u x (mod n)
2 2
y ≡ −x (mod n)
2 2
x +y ≡0 (mod n)
269
Teorema 10.14. Para todo inteiro n > 0,
X n
R(n) = r 2
d
d |n
2
(ud)2 + (wd)2 = n
Y Y
! !
n = 2h pi qj ,
p q
i j
N(21 ) = N(2) = 1,
N(22 ) = N(4) = 0,
N(2h ) = 0, h>2
10 Teorema 6.41: Seja f(x) um polinômio com coeficientes inteiros, e m um inteiro positivo.
Denote por N(m) a quantidade de soluções da congruência f(x) ≡ 0 (mod m). Então, se
m = m1 m2 , com m1 e m2 co-primos, N(m) = N(m1 )N(m2 ).
270
ou seja, somente a2 = −1 (mod 2) tem uma solução, e a2 = −1 (mod 2h )
não tem solução quando h > 1.
Para os primos da forma 4k + 3, pelo Lema11 10.2,
N(qj ) = 0, j > 0
R(13) = 4(1 + 1) = 8,
0 (mod pb ) e f 0 (x) 6≡ 0 (mod p), então existe um único t inteiro positivo tal que f(x + tpb ) ≡ 0
(mod pb+1 ).
271
Já 25 é 25 = (20 )(52 )(1), portanto
doze casos.
Agora, se n = 45 = 20 32 · 5, temos 32 , um primo 4k + 3 com expoente dois, e
5, um primo 4k + 1 com expoente 1. Ignoramos o 32 e calculamos
R(45) = 4(1 + 1) = 8.
oito casos.
Analisamos um último caso: n = 650. Agora n = (21 )(52 )(131 ). Novamente
ignoramos os fatores que não são 4k + 1 (neste caso o 2), e computamos
272
expoente j.
X n X
Y X Y X
h i j
2 p q
N 2 = N N N
d d2
d2
d 2
d2 |n d2 |2h p d2 |pi q d2 |qj
| {z } | {z } | {z }
(i) (ii) (iii)
Exercícios
Ex. 277 — Prove que se p é um primo da forma 4k + 1 então p pode ser
representado unicamente (a não ser por ordem e sinal) como soma de dois
quadrados.
X −1
R(n) = 4 .
d
d|n
dímpar
Ex. 280 — Sem usar a fatoração dos números nos argumentos, prove que
se m e n são representáveis como soma de dois quadrados (m = aq + b2 ,
n = c2 + d2 ), então mn também é soma de dois quadrados.
13 Lema 10.15: N(n) = 2s+1 , onde s é a quantidade de primos distintos da forma 4k + 1 que
dividem n.
14 Teorema 10.13: ∀n > 0, r(n) = 4N(n).
273
Ex. 281 — Prove que m = a2 − b2 se e somente se m é fatorável em dois
pares ou dois ímpares.
Ex. 283 — Como corolário do Exercício 282, mostre que um racional m/n
é soma de quadrados de dois racionais se e somente se mn é soma de dois
quadrados de inteiros.
Ex. 286 — Prove o Teorema dos quatro quadrados de Lagrange, desta vez
usando o seguinte argumento. Primeiro, defina
p 0 r s
0 p s −r
A=
0 0 1
0
0 0 0 1
274
Parte II
Capítulo 11
Formas Quadráticas
X
n
f(x1 , x2 , . . . , xn ) = aij xi xj ,
i,j=1
cos formam um todo coeso. A apresentação dada aqui para formas quadráticas não é a mais
abstrata e moderna, hoje usual na Álgebra/Teoria Algébrica de Números; ela parte de algo
mais concreto, não muito diferente da abordagem de Duncan Buell.
Buell, Duncan A. Binary Quadratic Forms. New York, NY: Springer-Verlag, 1989.
É notável também que formas quadráticas são relevantes em outros contextos. Cursos básicos
de Álgebra Linear, por exemplo, tratam de propriedades algébricas e geométricas dessas
formas, quando aplicadas sobre corpos (usualmente R ou C), diferentemente da abordagem
usual em Teoria dos Números, onde são aplicadas ao anel Z.
277
λ ∈ K,
Definição 11.2 (matriz de uma forma bilinear). Seja f uma forma bilinear
em um espaço vetorial V com base {b1 , b2 , . . . , bn }. Então a matriz da forma
f é a matriz de Gram2 mij = f(bi , bj ):
posição i, j é o produto interno do i-ésimo com o j-ésimo vetor. Uma forma bilinear pode não
ser produto interno, porque f(v, v) pode ser negativo, e porque f(v, w) pode ser diferente de
f(w, v), mas ainda assim usamos o nome “matriz de Gram”.
278
Exemplo 11.7. A forma quadrática 3x21 − x22 + x23 − 2x1 x2 + x2 x3 é represen-
tada pela matriz
3 −1 0
−1 −1 1/2 ,
0 1/2 1
porque
3 −1 0 x1
1/2 x2 = 3x21 − x22 + x23 − 2x1 x2 + x2 x3 .
x1 x2 x3 −1 −1
0 1/2 1 x3
O Teorema 11.9 define uma bijeção entre formas bilineares e e formas qua-
dráticas.
q(v + w) = f(v + w, v + w)
= f(v, v) + 2f(v, w) + f(w, w)
= q(v) + q(w) + 2f(v, w)
279
Ou ainda,
Exemplo 11.11. A forma quadrática 3x2 − 2xy − 2y2 tem matriz associada
3 −1
,
−1 −2
mente definidos para o caso geral de polinômios. Uma possível definição, usando as raízes do
polinômio, é: Seja p(x) = an x2 + · · · + a1 x + a0 um polinômio, e sejam r1 , r2 , . . . , rn suas raízes.
O discriminante de p é Y
Disc(p) = a2n−2
n (rj − ri )2 .
j<j
O termo é usado pela primeira vez na página 406, onde Sylvester inclui uma nota de rodapé
justificando a escolha do nome:
“Discriminante”, porque fornece o discernimento ou teste para determinar se
fatores iguais entram em uma função de duas variáveis, ou de forma mais ge-
ral, a existência de múltiplos pontosno locus representado ou caracterizado por
qualquer função algébrica, a mais óbvia e inicialmente observada espécie de sin-
gularidade in tal função ou locus. O progresso nessas pesquisas é impossível sem
o auxílio de uma expressão clara; e a primeira condição de uma boa nomenclatura
é que coisas diferentes sejam chamadas por nomes diferentes. As inovações na
linguagem matemática aqui e em outros lugares (não sem alta sanção) introduzi-
das pelo autor, nunca foram adotadas exceto sob a experiência real do embaraço
decorrente da falta delas, e não exigirão nenhuma vindicação para aqueles que
280
e portanto seus valores são sempre positivos ou sempre negativos – dize-
mos que estas formas são definidas positivas ou definidas negativas. Uma
forma quadrática que cruze o plano xy é indefinida. Outra maneira de ex-
pressar esse mesmo fato é: uma forma quadrática definida positiva tem
valor positivo para quaisquer valores de x e y; uma forma quadrática defi-
nida negativa, similarmente, resultará somente em valores negativos; e as
formas indefinidas resultam em valores positivos ou negativos, dependendo
dos valores de x e y. Consolidamos estas idéia na Definição 11.12.
A forma f(x, y) = 2x2 + 3y2 é positiva definida, porque assume valores po-
sitivos para todos x, y exceto para x = 0, y = 0, quando seu valor é zero.
A figura a seguir mostra o gráfico de f quando o domínio é estendido aos
reais.
A definição que acabamos de dar permite perceber que o discriminante será zero se e somente
se pelo menos duas raízes do polinômio forem iguais.
281
100
5
0
−4 0
−2 0 2 4 −5
20
−20 5
−4 0
−2 0 2 4 −5
282
os inteiros 3, 4, 6 e 29, 48, porque
f(0, 1) = 3
f(1, 1) = 4
f(−1, 1) = 6
f(2, 3) = 29
f(2, 4) = 48.
O último número mostrado, 48, tem representação imprópria, porque mdc (2, 4) =
2. J
A forma, no entanto, não representa o inteiro −1, porque não existem x e y
tais que f(x, y) = −1.
Definição 11.15 (formas quadráticas equivalentes). Duas formas quadráti-
cas são equivalentes se se existe matriz unimodular U tal que5 F = UGUT .
Escrevemos f ∼ g quando f é equivalente a g.
O Teorema 11.16 é apresentado sem sua demonstração, que é bastante sim-
ples.
Teorema 11.16. A relação ∼ é de equivalência.
O próximo teorema relaciona os conjuntos de números representados por
formas.
Teorema 11.17. Formas equivalentes representam os mesmos conjuntos
de números inteiros.
Demonstração. Suponha que f ∼ g, e que portanto haja U unimodular tal
que F = UGUT .
F(v) = n é o mesmo que v(UGUT )vT = n. Podemos reescrever (vU)G(UT vT ) =
n, que significa que G representa n, porque G(vU) = n.
Exemplo 11.18. Sejam
3 1 1 2 15 20
G= , U= , F= .
1 2 1 3 20 27
preservar a invariante da simetria da forma, e não a transformação linear que ela representa,
em base diferente.
283
Escolhemos um vetor, (−2, 3). Então F(−2, 3) = 15(−2)2 +40(−2)(3)+27(3)2 =
63. O número 63 deve, portanto, ser representado por G também. Como
apontado na demonstração do Teorema 11.17, se F = UGUT , então G repre-
senta n porque G(vU) = n. Basta calcular vU, que neste caso é
1 2
(−2, 3)U = (−2, 3) = (1, 5).
1 3
E realmente,
Demonstração.
284
Definição 11.23 (discriminante). O discriminante de uma forma quadrá-
tica ax2 + bxy + cy2 é ∆ = b2 − 4ac.
O Teorema 11.25 implica que não há formas quadráticas binárias com dis-
criminante 4k + 2 ou 4k + 3.
∆−1 2
x2 + xy − y
4
terá discriminante ∆.
Por haver mais de uma forma com o mesmo discriminante, e será inte-
ressante definir qual forma será representante natural do conjunto. Da
demonstração acima extraímos o conceito de forma principal, na Defini-
ção 11.26.
Representamos a forma ax2 + 2bxy + cy2 pelo símbolo (a, b, c) quando não
estivermos interessados nas incógnitas x, y.
Formam axx + 2bxy + cyy quando de indeterminatis x, y non agitur, ita desig-
nabimus, (a, b, c).
285
Definição 11.26 (forma principal). A forma principal de um discrimi-
nante ∆ é
−∆
1, 0, se ∆ ≡ 0,
4
−(∆ − 1)
1, 1, se ∆ ≡ 1.
4
Teorema 11.28. Seja f(x, y) = ax2 + bxy + cy2 uma forma quadrática com
discriminante ∆. Esta forma é indefinida se ∆ > 0; semidefinida (mas não
definida) se ∆ = 0; e definida quando a e c tiverem o mesmo sinal, e ∆ < 0.
Quando a forma é definida, será positiva quando a > 0 e negativa quando
a<0.
Teorema 11.29. Uma forma quadrática binária é produto de duas formas
lineares se e somente se seu discriminante é quadrado perfeito.
286
e f é produto de dois fatores lineares racionais, ou seja, há k, m ∈ Z tal que
k
f(x, y) = p(x, y)q(x, y)
m
df(x, y) = kp(x, y)q(x, y),
clideano, nenhum deles nulo. Então c(fg) = c(g) c(f). Assim, se f e g são primitivos, então fg
também é.
Aqui c(p) é o conteúdo do polinômio, definido como o MDC de seus coeficientes.
287
Novamente expandimos o produto no lado direito da equação para verificar
que a, coeficiente de x2 em g, será α:
∆ = s2 − 4nt
∆ ≡ s2 (mod 4nt)
2
∆≡s (mod 4|n|)
288
Demonstração. Como p é primo, qualquer representação sua é própria, e
pelo Teorema 11.33, ∆ é quadrado módulo 4p. Assim, (∆/p) = 1. A recí-
proca: se (∆/p) = 1 então ∆ é resíduo quadrático módulo p. O enunciado
determina que ∆ ≡ 0, 1 (mod 4), o que significa que ∆ é quadrado módulo 4
(porque um inteiro é quadrado módulo 4 se e somente se é congruente a 0
ou 1 módulo 4). Pelo Teorema Chinês dos Restos, como p é ímpar e
∆ ≡ r2 (mod p)
∆ ≡ k2 (mod 4),
i) ∆ = 4k + 1 livre de quadrados;
289
Se ∆ = 4k, verificamos três casos, k livre de quadrados; k = 4r; e k = 4r + 1.
Para os dois primeiros, a forma
k 2
mx2 − y 2
m
tem discriminante ∆ e não é primitiva, porque m divide os dois coeficientes
não nulos.
Se k = r + 1, a forma
k−1
2x2 + 2xy −
2
tem discriminante ∆ e não é primitiva, porque 2 divide todos os coeficien-
tes. Assim, se ∆ como no enunciado, qualquer forma que o tenha como
discriminante é não-primitiva.
Demonstração.
0 −1 1 1 1 k
S= , T= , Tk =
1 0 0 1 0 1
ST FS = (c, −b, a)
(T k )T FT k = (a, b + 2ka, ak2 + bk + c)
Note que se |a| > |c|, a transformação S leva a uma forma (A, B, C) com
|A| < |C|, porque troca a posição dos dois argumentos. Se |b| > |a|, a pode-
se escolher k tal que a transformação T k leva a uma forma (A, B, C) com
290
|B| < |A|. Assim, se uma forma (a, b, c) não é como desejado, o Lema 11.38
permite encontrar uma forma equivalente (A, B, C) em que |A| ≤ |C| ou |B| ≤
|A|. Após uma quantidade finita de passos, chega-se a uma forma em que os
coeficientes tem a propriedade que queremos:
1. Se |a| > |c|, troque (a, b, c) por (c, −b, −a) (use S);
2. Se |b| > |a|, troque (a, b, c) por (a, B, C), onde B = b + 2ak, com k
escolhido tal que |B| ≤ |a| (use T k );
3. Se a forma obtida não for tal que |b| ≤ |a| ≤ |c|, repita os dois passos
anteriores.
i) −a ≤ b < a < c, ou
ii) 0 ≤ b ≤ a = c.
291
que
a≥A
≥ ar2 − a|rt| + at2
= a|rt| + a(|r| − |t|)2
≥ a|rt|,
e a ≥ A ≥ a|rt|. |rt| deve ser, portanto menor ou igual que um, ou teríamos
a ≥ a|rt| > a. Mas r e t não podem ser ambos zero, porque dessa forma
teríamos U com determinante zero. As possibilidades para r e t são (0, ±1),
(±1, 0), (±1, ±1), (±1, ∓1).
Também comcluímos que quando r, t são ambos diferentes de zero, a ≥ A ≥
a|rt| e |rt| = 1 implicam que a = A.
O mesmo raciocínio aplicado usando c ≥ C leva à conclusão de que na
segunda coluna de U, as possibilidaes de valores para s e u são as mesmas.
Além disso, para que det U = 1, se r = 0 ou u = 0, então t = −s, e se s = 0
ou t = 0, u = r.
Dividimos as matrizes integrais com estas restrições em três casos, de acordo
com a primeira coluna. Note que nos dois primeiros casos a primeira coluna
igual a (1, 0) ou (0, 1) determina um dos elementos da segunda, para que o
determinante seja 1.
s 1
± , (a, b, c) → (a, b ± 2as, . . .)
1 0
0 −1
± , (a, b, c) → (c, b ± 2au, . . .)
1 u
1 s
± , (a, b, c) → (a ± b + c, . . . , . . .)
±1 u
292
passa a ser c. Como as duas formas são semirreduzidas, a ≤ c ≤ a im-
plica que a = c e f = (a, b, a). Se u = 0, a transformação leva de (a, b, a)
em (a, −b, a). Se u = 1, a transformação é (a, b, a) → (a, −b ± 2a, . . . ),
mas é necessário que | − b + 2a| ≤ |a|, o que só é possível se a = b, e te-
mos (a, a, a) → (a, −a, a). Quando u = −1, a = −b e a transformação é
(a, −a, a) → (a, a, a).
No último caso, o primeiro coeficiente de g é a + b + c, mas como r e t são
diferentes de zero, a = A e b = −c. Como as duas formas são semirredu-
zidas, a = ±b, f = (a, a, a) ou f = (a, −a, a). As matrizes do terceiro caso
representam as transformações (a, a, a) → (a, −a, a), (a, −a, a) → (a, a, a),
(a, a, a) → (a, a, a) e (a, −a, a) → (a, −a, a).
−∆ = −b2 + 4ac
≥ −aa + 4a2
= 3a2 .
Teorema 11.44. Toda forma quadrática binária definida positiva com dis-
criminante −4 é equivalente a uma soma de dois quadrados.
293
Como a > 0, necessariamente precisamos a = 1. Mas b deve ser zero ou
um, porque |b| < a. Como9 b2 ≡ ∆g ≡ 0 (mod 4), então b = 0. Com isso c
fica determinado:
∆g = b2 − 4ac
−4 = 0 − 4(1)c
g(x, y) = x2 + y2 ,
294
(e unimodular) U tal que UFUT = F.
A quantidade de automorfismos de f é denotada por w(f).
2 −1/2
Exemplo 11.46. Seja f = (2, −1, 1). A matriz de f é F = .
−1/2 1
−1 −1
Um automorfismo de F é U = , porque
0 1
−1 −1 2 −1/2 −1 0
UFUT = = F. J
0 1 −1/2 1 −1 1
295
• ±S é automorfismo para (a, 0, a), e para estas formas temos mais duas
possibilidades, totalizando quatro.
0 −1 −1 2 −1
• As transformações ±ST = ± e ±(ST ) = ±
, tam-
1 1 0 1
bém dentre aquelas listadas no Teorema 11.41, levam (a, a, a) em
(a, a, a). Assim, além das duas transformações ±I, há mais quatro,
totalizando seis.
296
Demonstração. Separamos a prova em duas partes.
Parte I: usamos desigualdades para mostrar que a forma principal é a única
possível com o discriminante dado.
A forma equivalente, se existisse, poderia ser reduzida – então presumimos
que a forma é reduzida, para podermos usar desigualdades.
Usaremos o Lema14 11.43 para determinar o valor máximo de a.
p
n = 1 Para n = 1, ∆ = −4, e a forma principal é (1, 0, 1). Então a < 4/3, e
precisa ser 1. Pelo Teorema15 11.41, a única forma equivalente seria
(1, −0, 1), que é a mesma forma.
p
n = 2 Para n = 2, ∆ = −8, e a forma principal é (1, 0, 2). Então a ≤ 8/3,
e também precisa ser um. Pelo Teorema 11.41, não há forma equiva-
lente.
p
n = 3 Para n = 3, ∆ = −12, e a forma principal é (1, 0, 3). a ≤ 12/3 = 2,
Mas se a = 2, precisamos de b < a < c, e teríamos |b| < 2 < c.
b2 − 4ac = b2 − 8c
< 1 − 8c (b < 2, b = 1)
< 1 − 8(3) (2 < c, logo c ≥ 3)
= −23.
b2 − 4ac = b2 − 12c
< 4 − 12c (b < 3 )
< 4 − 12(4) (3 < c, logo c ≥ 4)
= −44.
14 Lema 11.43: Se (a, b, c) é uma forma semirreduzida positiva definida com discriminante
∆, então r
−∆
0<a< .
3
15 Teorema 11.41: Se duas formas semirreduzidas são equivalentes, então elas são
297
Se a = 2,
b2 − 4ac = b2 − 8c
≤ 1 − 8c (b < 2 , b ≤ 1 )
≤ 1 − 8(3) (2 < c, logo c ≥ 3)
= −23.
02 − 4(2)c,
298
simplificada por Dirichlet17 em 1851.
Inicialmente, a regra de Gauss definia composição usando produto de poli-
nômios. Venkov (Venkov, 1970) comenta:
Se as formas
X = pxx 0 + p 0 xy 0 + p 00 yx 0 + p 000 yy 0
Y = qxx 0 + q 0 xy 0 + q 00 yx 0 + q 000 yy 0
obtivermos, identicamente em x, y, x 0 , y 0 ,
No original,
234. Postquam haec de formis in classes genera et ordines distribuendis pra-
emisimus, proprietatesque generales quae ex his distinctionibus statim defluunt
explicauimus, ad aliud argumentum grauissimum transimus a nemine hucusque
attactum, de formarum compositione.
Dirichlet, Johann Peter Gustav Lejeune. De formarum binariarum secundi gradus com-
positione. [S. l.: s. n.], 1851. Reproduzido em Jour. fur Math., 47, 1854, 155-160; Werke, II,
1897, 105-114. Trad Francês, Jour, de Math., (2), 4, 1859, 389-398.
299
No que segue, tratamos das classes de equivalência de formas com um
mesmo discriminante. Por exemplo, há três formas primitivas reduzidas
com discriminante −44:
Mas a classe de (1, 0, 11) é diferente da classe de (3, 2, 4): basta perceber
que 1 é representável por f = (1, 0, 11), mas não por g = (3, 2, 4).
Mas g(x, y) = 3x2 + 2xy + 4y2 , que sempre será maior que 1.
f∼F
g ∼ G.
f ∗ g = (a1 a2 , b, c2 /a1 )
= (a1 a2 , b, c1 /a2 ).
18 A exigência a a 6= 0 pode parecer estranha inicialmente – porque não simplesmente dizer
1 2
“a1 , a2 não nulos”? Isso é feito porque estes conceitos podem ser usados também módulo p
(mas isto não será feito neste texto).
300
De maneira semelhante, se C1 e C2 são duas classes de formas com o mesmo
discriminante, f1 ∈ C1 , f2 ∈ C2 , então a forma f1 ∗ f2 pertence a uma classe
C3 , que é denominada a composição das classes C1 e C2 , denotada C3 =
C1 ∗ C2 .
(1, 0, 30)
(2, 0, 15)
(3, 0, 10)
(5, 0, 6)
(3 · 5, 0, 2) = (15, 0, 2)
∼ (2, 0, 15) (redução da forma, (a,b,c) ⇒(c,-b,a))
(2 · 3, 0, 15/3) = (6, 0, 5)
∼ (5, 0, 6) (redução da forma, (a,b,c) ⇒(c,-b,a))
301
Lema 11.57. Se f e g tem o mesmo discriminante e representam 1, então
f ∼ g.
Lema 11.58. Para a composição de classes, a identidade é a classe da
forma principal (Definição 11.2620 ).
(1, 1, 16)
(2, 1, 8)
(4, 1, 4)
(8, 1, 2)
∗ 1 2 4 8
1 1 2 4 8
2 2 4 8 1
4 4 8 1 2
8 8 1 2 4
20 Definição 11.26: A forma principal de um discriminante ∆é
−∆
1, 0, se ∆ ≡ 0,
4
−(∆ − 1)
1, 1, se ∆ ≡ 1.
4
302
Nem todas as operações são imediatas. É um exercício interessante ten-
tar chegar a todos os resultados – pode ser necessário reduzir formas, ou
realizar a operação com formas equivalentes. Por exemplo, ao tentar dire-
tamente calcular (4, 1, 4) ∗ (8, 1, 2), nota-se que 4 - 8 (as formas não são con-
cordantes), e para não chegar a forma resultante (32, 1, 1/2), é necessário
encontrar formas equivalentes concordantes ou, neste caso, simplesmente
observar que
f = (8, 1, 2) ∗ (4, 1, 4)
−1
(8, 1, 2) ∗ f = (4, 1, 4)
(2, 1, 8) ∗ f = (4, 1, 4)
(2, 1, 8) ∗ (a, 1, c) = (4, 1, 4)
onde
2a = 4
8/a = c/2
Temos portanto a = 2, c = 8, e
f = (2, 1, 8).
Para que uma forma quadrática ternária seja integral não basta que os co-
eficientes do polinômio sejam integrais; isso é requerido da matriz que re-
presenta a forma.
303
não é integral, porque a12 = a21 = 1/2, ainda que o polinômio que ela
representa tenha coeficientes inteiros:
2 1/2 0 x1
f(x1 , x2 , x3 ) = x1 x2 x3 1/2 1 0 x2
0 0 2 x3
= 2x21 + x22 + x1 x2 + 2x23 . J
é
f(x1 , x2 , x3 ) = x21 + 2x22 + 2x1 x2 + 5x23
A matriz tem determinante um, portanto Q é equivalente a uma matriz que
representa soma de três quadrados: seja
1 0 0
R = −1 1 0
0 0 1
Então
1 0 0
RQRT = 0 1 0 ,
0 0 1
que representa a forma x21 + x22 + x23 . J
304
Exemplo 11.67. A forma apresentada no Exemplo 11.65,
1 1 0
Q= 1
2 0
0 0 1
a11 = 1 > 0
det Q = 1 > 0
1 1
det = 2 − 1 = 1 > 0. J
1 2
305
Também descartamos o caso n = 8k + 7, portanto consideramos somente os
casos n = 1, 2, 3, 5, 6 (mod 8).
a11 > 0
B = a11 a22 − a212 > 0
e teremos
22 Teorema 11.64: Toda forma quadrática ternária positiva definida integral com determi-
306
Observamos que o determinante de f deve ser 1.
a11 a12 1
det a12
a22 0 = a11 a22 n − a22 − a12 a12 n
1 0 n
= Bn − a22
=1
a11 > 0
B = a11 a22 − a212 > 0
Bn − a22 = 1
i) Escolher a22 = Bn − 1;
307
iii) Escolher a11 de acordo com a equação 11.1.
é primo.
Escolha B = 4t + 1 > 0 e então p = Bn − 1. Agora temos B ≡ 1 (mod 4) e
p ≡ n − 1 ≡ 1 (mod 4), e
−B −1 B
=
p p p
B
= (p = 4k + 1, Lema25 9.8)
p
p
= (p = 4k + 1, recip. quad.)
B
Bn − 1
=
B
−1
=
B
= +1. (B = 4k + 1, Lema 9.8)
Desta forma teremos sempre cn ≡ 3 (mod 4), e (cn − 1)/2 é ímpar. Seja
24 Teorema 11.68 (de Dirichlet): Sejam a, b ∈ Z, com mdc (a, m) = 1. Então Existem
308
h = mdc (4n, (cn-1)/2)). Temos dois casos:
cn − 1 (8t 0 + c)n − 1
p = 4nt 0 + =
2 2
é primo.
Seja B = 8t 0 + c. Como B > 0, então 2p = Bn − 1, precisamos mostrar que B
é quadrado módulo 2p. Consideramos três casos:
A última passagem se justifica porque (i) se p ≡ 1 (mod 4), então (−1/p) (B/p)
= (1)(B/p) = (p/B); e se p ≡ 3 (mod 4) então B ≡ 3 (mod 4) também, e
(−1/p) (B/p) = (−1)(B/p) = (−1)(−1)(p/B).
309
Juntando tudo,
−B p
= (por 11.3)
p B
p −2
= (por 11.2, (−2/B) = +1)
B B
−2p
=
B
1 − Bn
= (2p = Bn − 1)
B
1
=
B
= +1. (1 sempre é quadrado)
x ≡ x0 (mod p).
Finalmente,
r2 + b ≡ 0 (mod p)
2
r +b≡0 (mod 2)
r2 + b ≡ 0 (mod 2p)
r2 ≡ −b (mod 2p),
completando a demonstração.
Exercícios
Ex. 289 — Prove que a seguinte definição é equivalente à dada no texto.
310
1 + 1 6= 0 em K). Uma função f : V × V → K é uma forma quadrática
se
•∀ k ∈ K, v ∈ V , f(kv) = k2 f(v)
•a função b(v, w) = f(v + w) − f(v) − f(w) é uma forma bilinear.
Ex. 290 — (Fácil) Seja f = ax2 + bxy + cy2 uma forma quadrática binária.
Mostre que b ≡ ∆(f) (mod 2).
Ex. 291 — Quais das formas são equivalentes? x2 + 2xy + 4y2 , x2 − 2xy −
21y2 , −2x2 − y2 , 2x2 + 4xy + 3y2 .
Ex. 294 — Seja f uma forma quadrática binária com discriminante nega-
tivo e n ∈ Z. Mostre como resolver a equação diofantina f(x, y) = n.
Ex. 295 — Seja f uma forma quadrática binária com discriminante nega-
tivo e n ∈ R. Mostre que a quantidade de soluções para f(x, y) = n é finita.
Ex. 296 — Prove que todo discriminante pode ser escrito de forma única
como k2 ∆. onde ∆ é discriminante fundamental.
311
Ex. 300 — Encontre uma definição sucinta para forma quadrática definida
reduzida. A definição deve valer para formas positivas e negativas, sem a
necessidade de separar explicitamente estes dois casos.
Ex. 306 — Prove que toda forma definida com determinante 1 é equiva-
lente à forma x2 + y2 .
Ex. 307 — Prove que todo primo da forma 4k + 1 pode ser escrito como
soma de dois quadrados, usando o Teorema 11.33. (Ou seja, apresente uma
demonstração alternativa para o Teorema 10.3).
312
Capítulo 12
az + b
f(z) = ,
cz + d
Representamos transformações como matrizes:
a b
f=
c d
αz + β
g(z) = ,
γz + δ
(bγ + aα)z + bδ + aβ
f(g(z)) = .
(dγ + cα)z + dδ + cβ
313
da forma já dada, e F e G são suas matrizes, então
a b α β bγ + aα bδ + aβ
FG = =
c d γ δ dγ + cα dδ + cβ
Definição 12.1 (grupo modular / grupo linear especial projetivo PSL(2, Z)).
As matrizes 2×2 com elementos integrais e determinante 1, usando a opera-
ção usual de multiplicação de matrizes, formam o grupo modular, também
chamado de grupo linear especial projetivo. Equivalentemente, as transfor-
mações da forma
az + b
T (z) = ,
cz + d
com a, b, c, d ∈ Z, ad − bc = 1, e usando a operação de composição de
funções, formam o grupo modular. Este grupo é denotado por PSL(2, Z), ou
por Γ .
Como exemplo,
2 3
M= ∈ Γ,
3 5
porque todos os mi, são inteiros, e det M = 1.
314
do sinal do determinante; T soma a segunda linha à primeira.
a b a+c b+d a b −c −d
T = , S =
c d c d c d a b
Suponha que c seja zero. Como det M = 1 e os elementos são todos inteiros,
então a diagonal só pode ser a = d = ±1. Mas isto significa que M é T n ,
para algum n, já que
1 n
Tn = .
0 1
Suponha, então, que c > 0. Suponha também que |a| > |c| (se não for,
pode-se usar S para trocar as linhas).
Agora faremos a divisão de a por c: a = qc + r, com 0 ≤ r < |c|. Isto pode
ser realizado multiplicando T −q :
a − qc b − qd
T −q M = .
c d
M = T k1 ST k2 S · · · T kn .
315
Definição 12.6 (região fundamental). Dado um grupo de transformações
no plano, a região fundamental (também chamada de “domínio fundamen-
tal”) do grupo é uma região do plano que não contém dois pontos equivalen-
tes, mas contém pontos representando todas as classes de equivalência.
1 1
z 0 = z, z0 = − , z 0 = −1 − ,
z+1 z
ou seja, a identidade, ST e T −1 S.
316
O ponto i é mapeado em si mesmo somente pela identidade e por S,
1
z 0 = z, z0 = − ,
z
Qualquer outro ponto em R é mapeado em si mesmo apenas pela identidade.
−1 − 12 0 + 12 +1
317
Estes passos (T k seguido de S) podem ter que ser repetidos um número
finito de vezes, porque eventualmente a parte imaginária será maior que 1,
e uma translação será suficiente para chegar a R.
|cz + d| ≤ 1.
Como |z| > 0, então necessariamente |c| ≤ 1. Uma vez que c ∈ Z, então
c ∈ {−1, 0, +1}.
Se c = 0, então
az + b az + b
g(z) = =
cz + d d
Mas ad−bc = 1, e como c = 0, temos ad = 1, com a, d ∈ Z. Assim, a, d = ±1.
Com isso teremos
g(z) = z + b,
e g(z) = T n (z). Mas como a translação não pode mudar a parte imaginária
de um número, e a largura da região que escolhemos como domínio funda-
mental é 1, então b = 0 e g é a identidade, logo z = z 0 .
az + b 1
g(z) = =a− ,
cz + d z
ou seja, T (S(z)). Mas, como a parte imaginária de z estava em R, era maior
que um. E esta transformação muda a parte imaginária para algo menor
que um (porque aplica S, e em seguida T ), e portanto z e g(z) não podem
estar ambos em R.
az + b
g(z) =
z+1
318
Mas ad − bc = 1, portanto a − b = 1, e
az + (a − 1)
g(z) =
z+1
1
=a− ,
ρ+1
Teorema 12.9. Se uma forma quadrática ax2 + bxy + cy2 definida positiva
está na forma reduzida – ou seja,
−a < b ≤ a < c ou 0 ≤ b ≤ a = c,
319
A norma de z é
b2 −∆
N(z) = +
4a2 4a2
b2 − b2 + 4ac
=
4a2
c
= .
a
Desta forma, para que z ∈ R, é necessário que a parte real esteja em
[−1/2, +1/2),
1 −b 1
− ≤ <
2 2a 2
−a ≤ −b < a
a ≥ b > −a,
e que a norma seja > 1 quando a parte real é positiva, e ≥ 1 quando a parte
real é ≤ 0. No primeiro caso,c/a > 1 implica imediatamente que c > a. No
segundo, temos −b/2a > 0 e c/a = 1, o que implica que b ≥ 0 e c = a.
Combinando as possibilidades, concluímos que uma forma definida positiva
tem representante no domínio fundamental de Γ se
−a < b ≤ a < c ou 0 ≤ b ≤ a = c,
conforme o enunciado.
320
12.3 Formas quadráticas indefinidas
Exercícios
Ex. 310 — Prove que o grupo Γ também pode ser gerado por
t(z) = z + 1
z
u(z) =
z+1
Ex. 311 — Prove que o grupo Γ pode ser gerado por duas transformações
de ordem finita no grupo (a transformação T , que usamos no gerador de Γ ,
não tem ordem finita!)
com a, b, c, d ∈ Z.
Prove que Γ2 é grupo, e que Γ2 = Γ1 . Identifique um domínio fundamental
para Γ1 , e prove que de fato é domínio fundamental. Se Γ2 6= Γ1 , faça o
mesmo para Γ2 .
321
322
Capítulo 13
Corpos Quadráticos
Exemplo 13.2. Os corpo dos reais são extensão do corpo dos racionais; o
corpo dos complexos é extensão do corpo dos reais. J
Exemplo 13.3. Z2 é um corpo, contendo os elementos 0 e 1, e onde as
operações são as usuais, mas módulo dois. É usual denotar GF(2) ao invés de
Z2 . Podemos construir um corpo com quatro elementos, que é uma extensão
de GF(2). O conjnuto de polinômios
323
qualquer extensão de corpos: R é também um espaço vetorial sobre Q, com
dimensão infinita.
[E : K] = [E : F][F : K].
0, 1, x, x + 1,
x2 , x2 + 1, x2 + x, x2 + x + 1
324
Este corpo é uma extensão de GF(4), com grau 2 (ou seja, [GF(8) : GF(4)] = 2:
cada elemento de GF(8) é espaço vetorial de dimensão dois sobre GF(4), com
base (1, x).
A seguir estão as combinações lineares da base (1, x). Cada linha mostra
α(1) + β(x), onde α, β são coeficientes pertencentes ao corpo subjacente do
espaço vetorial (aqui GF(4)).
0 + 0(x) = 0
1 + 0(x) = 1
0 + 1(x) = x
1 + 1(x) = x + 1
0 + x(x) = x2
1 + x(x) = x2 + 1
x + x(x) = x2 + x
x + 1 + (x)(x) = x2 + x + 1.
Já com d = −1,
Q[i] = {a + bi : a, b ∈ Q} . J
1 Verifique!
325
Exemplo 13.12. Com d = 6, o corpo quadrático é
√ √ √ √ √
Q[ 6] = Q[ 2 3] = a + b 2 3 : a, b ∈ Q .
326
Demonstração.
(r − α)(r − α) = r2 − (α + α)r + αα
= r2 − Tr(α)r + N(α) (13.2)
x yd
Este é evidentemente o polinômio característico de y x , quando α =
√
x + y d.
Definição
√ 13.17 (inteiro em corpo quadrático). Dizemos que α é inteiro
em Q[ d] (também chamado de inteiro quadrático) se o polinômio 13.2,
que define α, tem coeficientes em Z.
√ √
Exemplo 13.18. Em Q[ 2], 1 + 3 2 é inteiro, porque sua representação
natural é
1 6
,
3 1
que tem polinômio característico x2 − 2x − 17, com coeficientes em Z. J
√
Teorema 13.19. Se α ∈ Q[ d] é inteiro quadrático, então N(α) ∈ Z e
Tr(α) ∈ Z.
O Lema 13.20 será usado na√ demonstração do Teorema 13.21, que identifica
a forma dos inteiros em Q[ d].
m2
dt2 = d ,
p2 w 2
327
Demonstração. (⇒) Primeiro mostramos que os elementos das duas formas
dadas são realmente inteiros
√ quadráticos.
Suponha que α = a+b d, com a, b ∈ Z, então o traço e a norma de α são 2a
e a2 = b2 d, inteiros – portanto os coeficientes do polinômio característico
associado são inteiros. √
Agora suponha que α = a+b 2
d
, sendo que a e b tem a mesma paridade. O
traço é tr(α) = a. A norma é
a b√ a b√
N(α) = + d − d
2 2 2 2
a2 − b2 d
=
4
a2 − b2 (4k + 1)
=
4
a2 − 4kb2 − b2
=
4
a2 − b2
= − kb2
4
(a + b)(a − b)
= = kb2
4
a 2
+ y2 d ∈ Z
2
a2
+ y2 d ∈ Z
4
a2 + (4y2 )d ∈ 4Z
a2 + (2y)2 ∈ 4Z
328
múltiplo de 4. Assim, y = b/2 para algum b ∈ Z.
a2 b2
x2 − dy2 = − d = 4k
4 4
Logo,
a2 ≡ db2 (mod 4)
1 ≡ d(1) (mod 4), (quadrados ímpares são 1 (mod 4))
Seja √
d se d ≡ 1 (mod 4)
ω= √
1+ d
2 se d 6≡ 1 (mod 4)
√
Denotaremos os inteiros em um corpo quadrático F = Q[ d] por
OF = Z[ω] = {a + bω : a, b ∈ Z} .
√
Teorema 13.22. Se α e β são inteiros em Q[ d], então α, α+β e αβ também
são.
329
13.3 Divisibilidade
A noção de divisibilidade em Z se estende a inteiros quadráticos.
γδ = 1
N(γδ) = N(1)
N(γ)N(δ) = 1,
é ±1.
portanto a norma de qualquer unidade√
Agora, suponha que para algum α ∈ Q[ d], N(α) = ±1.
αα = N(α)
αα = ±1,
e o inverso de α é ∓α.
330
Denotamos o grupo de unidades em OF por OF× .
A fatoração a que se refere o Teorema 13.34 pode ou não ser única, depen-
dendo do corpo quadrático.
Exercícios
Ex. 315 — Prove que se α é inteiro quadrático, então α2 + (α)2 ∈ Z.
√ √
Ex. 316 — Prove que Q[ 2] e Q[ 3] não são isomorfos.
331
√ √ √ √
Ex.
√ 317
√ — Prove que Q[√2 3] = Q[ 2 + 3], e que consequentemente,
Q[ 2 3] é extensão de Q[ 2].
√ √ √ √ √
Ex. 318 — Determine Q[ 3 5] : Q[ 5] e Q[ 3 5] : Q .
332
Capítulo 14
Partições de um Inteiro
n
Dizemos que (1 + x)n é a função geradora n
de k , uma vez que (1 + n) des-
m
creve completamente os valores de k . Note que não demos atenção ao
valor de (1 + x)n , mas apenas os coeficientes em sua expansão; e note tam-
bém que a função geradora determina completamente a sequência de coe-
ficientes. Neste Capítulo usaremos séries formais de potencias. Estas são
semelhantes a polinômios, mas podem ter infinitos termos, e usualmente as
título De Partitione Numerorum, onde Euler apresenta uma grande quantidade de idéias
fundamentais no estudo de partições de inteiros.
Euler, Leonhard. Introduction in Analysin Infinitorum. [S. l.], 1748. O original em Latim
está disponível em [Link]
333
tratamos como objetos algébricos – elementos que somamos e multiplica-
mos dentro de uma estrutura algébrica – e não como funções.
onde aj ∈ R.
As séries formais de potências onde os coeficientes pertencem a R e a vari-
ável é x formam um anel, denotado R[[x]].
Por exemplo,
1
1−x
é função geradora da sequência (1, 1, 1, . . .): note que
X
k
1
lim xj = ,
k→∞ 1−x
j=0
P
xj ) são todos iguais a um.
e os coeficientes na soma (
Para um segundo exemplo, a sequência (2, 1 + 1/2, 1 + 1/3, . . . , 1 + 1/k, . . .)
tem como função geradora
−ln(1 − x),
já que
X
m
1
lim 1+ xj = −ln(1 − x).
m→∞ j
j=0
14.2 Partições
334
Por exemplo, as partições de 4 são
4=1 + 1 + 1 + 1
=2 + 1 + 1
=2 + 2
=3 + 1
= 4.
Teorema 14.7.
(−1)s n = s (3s±1)
2
p1 (N̂, n) − p2 (N̂, n) =
0 caso contrário.
335
Cada um dos termos pode ser representado em base dois, e como nesta
partição só há partes ímpares, o número dois não aparece em qualquer das
partes, de forma que as representações em base 2 são distintas e não tem
fatores em comum.
Então, para cada partição contendo partes ímpares, existe uma partição
com partes distintas.
Observamos que toda partição tem parte distintas, quando posta na base 2
ficará na forma da Equação 14.2, e poderá ser transformada, revertendo os
passos, em partição com partes ímpares, como na Equação 14.1
onde S = {s1 , s2 , . . . , sj }.
O número de vezes que xn aparece no somatório é o número de soluções
distintas para
n = s1 k1 + . . . + sj kj , (14.3)
sendo cada solução uma partição de n em Ŝ. Tendo definido uma bijeção
entre as soluções da equação 14.3 e as partições de cada n em Ŝ, temos
finalmente
∞
X Y 1
p(Ŝ, n)xn = . (14.4)
1 − xn
n=0 n∈S
336
P∞
No lado esquerdo da equação 14.4, a soma n=0 p(Ŝ, n)xn converge:
X
sp
Y
p
1
p(Ŝ, n)xn ≤
1 − xsi
n=0 i=1
∞
Y 1
<
1 − xi
i=1
14.4 Exercícios
Ex. 322 — Prove que a quantidade de partições auto-conjugadas de um
inteiro positivo n é igual à quantidade de partições com partes ímpares
distintas desse mesmo inteiro.
Ex. 323 — Mostre algum Ŝ tal que p(Ŝ, n) seja igual à quantidade de parti-
ções onde a distância entre cada duas partes é no mínimo 3, ou prove que
não existe um Ŝ com esta propriedade.
337
338
Capítulo 15
Frações Contínuas
339
xi e os quocientes por yi .
x0 = y1 x1 + x2 (x0 ÷ x1 = y1 , resto x2 )
x1 = y2 x2 + x3
..
.
xn−1 = yn xn ( + 0)
1
q0 = y0 +
qi+1
1
= y0 +
1
y1 +
q2
..
.
1
= y0 +
1
y1 +
y2 + ..
. 1
+
1
yn +
yn+1
340
Por exemplo, se calcularmos MDC(111, 495),
495 = 4(111) + 51
111 = 2(51) + 9
51 = 5(9) + 6
9 = 1(6) + 3
6 = 2(3) + 0
495 51
=4+ ,
111 111
obtendo assim a parte inteira da fração. Se fizermos o mesmo com 51/111,
e assim sucessivamente, chegaremos a
495 1
=4+
111 1
2+
1
5+
1
1+
2
Esta é uma representação do racional 495/111 na forma de fração contínua.
2 Para uma extensa revisão da história das frações contínuas, veja o livro de Claude Brezinski.
Brezinski, Claude. History of Continued Fractions and Padé Approximants. Berlin Hei-
delberg: Springer-Verlag, 1991.
mas não comum hoje. Como curiosidade, a notação para frações contínuas usada por Pietro
x x x
Cataldi em 1613 é: x0 · & y 1· & y 2· & y 2· · · · .
1 2 2
341
da fração contínua4 .
Se xi é inteiro quando i > 0, dizemos que a fração contínua é simples.
1 121
[4; 1, 5, 4] = 4 + = .
1 25
1+
1
5+
4
Teorema 15.2. Toda fração contínua finita representa um número racional.
Teorema 15.3. Todo racional pode ser representado por frações contínuas
finitas
Mesmo racionais que tem representação infinita em base dez (como 1/3 =
0.3333 . . ., por exemplo) tem representação finita como fração contínua.
Nos falta investigar a unicidade da representação de racionais como frações
contínuas. Interessantemente, a representação de racionais como frações
contínuas não é única: há exatamente duas expansões para cada racional,
Cataldi, Pietro Antonio. Trattato del modo brevissimo di trouare la radice quadra delli
numeri, et regole da approssimarsi di coninuo al vero nelle radice delli numeri non
quadrati, con le cause, et inventioni loro. Et anco il modo di pigliarne la radice cuba,
applicando il tutto alle operationi militari et altre. [S. l.: s. n.], 1613. Sim, o título tem
48 palavras. Disponível em [Link]
n8/mode/2up.
4 Falamos dos x porque o numerador é sempre um, mas também se pode considerar frações
i
contínuas com numeradores diferentes de um, da forma x0 + K∞
xm x1 x2 x3
m=1 y = y y y
,
m 1 + 2 + 3 +· · ·
ou seja,
x1
x0 + x2 .
y1 + x3
y2 +
y3 + ..
.
Faremos isto quando tratarmos da irracionalidade de π (na Seção 15.7).
342
mas isto já nos serve. Por exemplo,
1 1
[1; 1, 5] = 1 + , [1; 1, 4, 1] = 1 + ,
1 1
1+ 1+
5 1
4+
1
e ambas são evidentemente iguais (as duas valem 11/6).
O Lema 15.4 mostra que é trivial determinar o inverso de uma fração contí-
nua; ele será útil logo mais na demonstração da unicidade da representação.
Demonstração.
q 1
=
p p/q
1
=
[x0 ; x1 , x2 , . . . , xn ]
1
=
1
x0 +
1
x1 +
x2 + .
..
1
+
xn
= [0; x0 , x1 , x2 , . . . , xn ]
343
e também que
1
[0; x1 , x2 , . . . , xr ] =
1
x1 +
x2 + ..
. 1
+
xr
bac = x0 = y0 ,
−1
[0; x1 , x2 , . . . , xr ] = [x1 ; x2 , . . . , xr ],
−1
[0; y1 , y2 , . . . , ys ] = [y1 ; y2 , . . . , ys ],
344
obtida facilmente:
√ √
2 = 1 + ( 2 − 1)
1
=1+ √
1+ 2
1
=1+
1
1+ 1+ √
1+ 2
1
=1+
1
2+ √
2+ 2
1
=1+
1
2+
1
2+
2+ ..
.
√
Notamos que a expansão é infinita: 2 = [1; 2, 2, 2, . . . ]. É interessante
√ que
como mostramos que uma fração contínua infinita representa 2, e já ha-
víamos demonstrado que racionais sempre tem representação√ finita como
frações contínuas, o que temos é uma prova de que 2 é irracional. Pre-
cisamos portanto definir frações contínuas infinitas, e verificar o que elas
representam e o que podemos concluir a respeito desses números.
Por exemplo,
e = [2; 1, 2, 1, 1, 4, 1, 1, 6, 1, 1, 8, . . .]
π = [3; 7, 15, 1, 292, 1, 1, 1, 2, 1, 3, 1, 14, . . .]
φ = [1; 1, 1, 1, 1, 1, 1, 1, 1, . . .]
tan(1) = [1; 1, 1, 3, 1, 5, 1, 7, 1, 9, 1, 11, . . .]
tanh(1) = [0; 1, 3, 5, 7, 9, 11, 13, 15, 17, 19, . . .]
√
2 = [1; 2, 2, 2, 2, 2, 2, 2, 2, . . .]
√
3 = [1; 1, 2, 1, 2, 1, 2, 1, 2, . . .]
345
rais,
C = 0, 1234567891011121314 · · · ,
cuja representação em frações contínuas é
15.2.1 Convergentes
Neste texto iniciamos com um semianel (N) e aos poucos o aumentamos para
obter estruturas mais úteis: o anel Z e o corpo Q (nesse caminho passamos
brevemente pelo anel sem ordem dos inteiros Gaussianos).
5 ω = 4 575 401 113 910 310 764 836 466 282 429 561 185 996 039 397 104 575 550 006 620 043 930
902 626 592 563 149 379 532 077 471 286 563 138 641 209 375 503 552 094 607 183 089 984 575 801
469 863 148 833 592 141 783 010 987.
346
√
Por exemplo, os primeiros convergentes de 2 são
p0 /q0 = [1] = 1
1 3
p1 /q1 = [1; 2] = 1 + = = 1.5
2 2
1 7
p2 /q2 = [1; 2, 2] = 1 + = = 1.4
1 5
2+
2
1 17
p3 /q3 = [1; 2, 2, 2] = 1 + = = 1.416666 . . .
1 12
2+
1
2+
2
1 41
p4 /q4 = [1; 2, 2, 2, 2] = 1 + = = 1.413793 . . .
1 29
2+
1
2+
1
2+
2
pi = ai pi−1 + pi−2
qi = ai qi−1 + qi−2
com
p0 = a0 q0 = 1
p−1 = 1 q−1 = 0.
347
Demonstração. pi qi−1 − pi−1 qi = (−1)i+1 , logo qualquer divisor comum de
pi e qi é divisor de ±1.
apk−1 + pk−2
[x0 ; . . . , xk−1 , a] =
aqk−1 + qk−2
apk−1 + pk−2
[x0 ; . . . , xk−1 , a] =
aqk−1 + qk−2
Então,
pi+1 pi (−1)i+1
− =
qi+1 qi qi qi+1
Teorema 15.14. Para qualquer fração contínua infinita simples com con-
vergentes pi /qi ,
pi pi−1 1
− ≤ i,
qi qi−1 2
e a sequência é convergente.
348
Demonstração. Denote por Fi o i-ésimo número de Fibonacci. Como qi ≥ Fi ,
então qi qi+1 ≥ Fi Fi+1 ≥ 2i , e
pi pi−1 (−1)i
− ≤ ,
qi qi−1 2i
donde se conclui que a sequência (a)i converge, já que 2−i chega arbitrari-
amente próximo de zero.
pi
lim ,
i→∞ qi
r0 = bxc
1
x = r0 +
r1
1
ri = bri c +
ri+1
Então
x = [x0 ; x1 , . . . , xk−1 , rk ]
Demonstração. Segue de maneira simples por indução em k.
Teorema 15.18. Para qualquer fração contínua infinita simples com con-
vergentes pi /qi e valor x,
pi 1
x− < .
qi 2q2i
Teorema 15.19. Seja x um número irracional, de forma que
x = [ξ0 ; ξ1 ; . . . , ξk−1 , xk ]
349
Então
xk pi + pi−1
x= .
xk qi + qi−1
Demonstração. Segue facilmente por indução.
Tendo demonstrado que toda fração contínua infinita converge, nos falta
verificar que, partindo de um irracional, chegaremos na mesma fração con-
tínua. Isto é garantido pelo Teorema 15.20.
pi
x = lim
i→∞ qi
p a
x− < x−
q b
350
Embora possa parecer que as duas afirmações são equivalentes, não é o
caso, e a recíproca não vale (um contraexemplo é pedido no Exercício 335)
p a
x− < x−
q b
q<b
pi 1
x− < .
qi 2q2i
p pi p pi
− ≤ −x + x− (desigualdade de triângulo)
q qi q qi
pi
≤2 x− (p/q mais próximo de x – Lema 15.23)
qi
1
< 2.
qi
No entanto,
p pi pqi − pi q 1 1
− = > ≥ 2.
q qi qi q qi q qi
Como chegamos a uma contradição, a suposição de que p/q existe é falsa.
351
(i) É impossível que a/b < a0 , porque se assim fosse, 1 seria melhor aproxi-
mação do que a/b:
a
|(1)x − x0 | < x − ≤ |bx − x| . (1≤b)
b
qk < b.
Mostramos que qk < b porque queremos mostrar que pk /qk seria melhor
aproximação do que a/b.
a pk+1 a
x− ≥ −
b qk+1 b
1
≥
bqk+1
1
|bx − a| ≥ ,
qk+1
pk 1
x− <
qk qk qk+1
1
|qk x − pk | ≤ ,
qk+1
então
|qk x − pk | ≤ |bx − a|,
e a/b não pode ser melhor aproximação, porque pk qk é melhor.
(iii) Se a/b > p1 /q1 , então a distância de x até a/b é maior do que até
p1 /q1 :
a p1 a 1
x− > − ≥
b q1 b bq1
352
Então, multiplicando por b,
1 1
|bx − a| > =
q1 x1
1
|(1)x − x0 | ≤ ,
x1
Nos três casos chegamos a contradições, portanto a/b precisa ser um dos
convergentes na expansão de x.
353
Teorema 15.29. Toda fração contínua eventualmente periódica representa
um irracional quadrático.
Demonstração. Seja
x = [ξ0 ; ξ1 , . . . , ξk . . . , ξn ]
Escrevemos somente a parte periódica, e chegamos a
xk = [ξk ; . . . , ξn , xk ]
xk pn + pn−1
xk =
xk qn + qn−1
xk pk−1 + pk−1
x= ,
xk qk−1 − qk−2
e
2
xk pk−1 + pk−1 xk pk−1 + pk−1
a +b +c=0
xk qk−1 − qk−2 xk qk−1 − qk−2
a(xk pk−1 + pk−1 )2 + b(xk pk−1 + pk−1 )(xqk−1 − qk−2 ) + c(xqk−1 − qk−2 ) = 0
Ak x2k + Bk xk + Ck = 0,
354
com
pi 1
x− < .
qi 2q2i
logo
|zn−1 |
pk−1 = xqk−1 + (|z − 1| < 1)
qn−1
Assim, Ak pode ser reescrito como
2
zk−1 zk−1
Ak = a xqk−1 + + b xqk−1 + qk−1 + cq2k−1
qk−1 qk−1
zk−1
= ax2 + bx + c q2k−1 + 2axzk−1 + a 1 + bzk−1
qk−1
z2k−1
= 2axzk−1 + a + bzk−1 (ax2 + bx + c = 0)
q1k−1
z2k−1
|Ak | = 2axzk−1 + a + bzk−1 < 2|ax| + |a| + |b|,
q2k−1
355
15.5 Construção de R com frações contínuas
Gostaríamos de incluir os números irracionais (que surgem em diversos pro-
blemas e mensurações físicas) no corpo que estamos usando, e isto é equi-
valente a incluir “o elemento para o qual convergem” estas aproximações a
que demos o nome de convergentes.
(i) x(x, y) ≥ 0
|an − ak | < ε,
1 1
|an − ak | = −
2n 2−k
1 1
< n+ k
2 2
1 1
< N+ N
2 2
1
< N−1
2
< ε. J
356
Definição 15.35 (espaço métrico completo). Um espaço métrico A é com-
pleto se toda sequência de Cauchy em A converge para algum elemento
também em A.
[1]
[1; 2]
[1; 2; 2]
[1; 2; 2, 2]
..
.
√
não converge para um racional, porque sabemos que [1; 2] = 2 6∈ Q.
A seguir mostramos que, partindo das frações contínuas finitas (que repre-
sentam os racionais), podemos construir um modelo para os reais, inclu-
indo no conjunto as frações contínuas infinitas. Com isso toda sequências
de Cauchy convergirá para um elemento no conjunto. Obteremos um corpo
ordenado que também é espaço métrico completo – e que chamaremos de
corpo ordenado compelto.
Definimos um símbolo ω tal que ω > n para todo n ∈ N, e assim podemos
denotar todas as frações contínuas como infinitas,
[a0 ; a1 , a2 , . . . , an ] → [a0 ; a1 , a2 , . . . , an , ω, ω, . . . ],
a = [a0 ; a1 , a2 , . . . ],
b = [b0 ; b1 , b2 , . . . ],
357
Teorema 15.36. Seja K o conjunto de todas as frações contínuas (finitas
e infinitas). Se ∅ 6= M ⊂ K e M é limitado superiormente, então M tem
supremo. Mais ainda – para toda fração contínua a,
a = sup a(2i) : i ≥ 0 .
−a = sup −a(2n+1) : n ≥ 0
O Teorema 15.37 nos garante que o que construímos foi de fato o corpo dos
números Reais.
Teorema 15.37. Todos os corpos ordenados completos são isomorfos.
15.6 e é irracional
√
Já mostramos a irracionalidade de φ e de k, quando k não é quadrado
perfeito. Tratamos agora de e. Esta seção traz uma demonstração, ela-
borada por Henry Cohn, de que a expansão de e em fração contínua é de
fato [2; 1, 2, 1, 1, 4, 1, 1, 6, . . . ], e com isso ganhamos também a prova de que
e é irracional, e de que não é quadrático (porque a sequencia não é perió-
dica). Após esta, apresentamos outra demonstração, de Fourier, sem o uso
358
de frações contínuas, e mais curta, mas que não leva à irracionalidade de
e2 .
1
[1; 0, 1, 1, 2, 1, 1, 4, 1, 1, 6, 1, 1, 8, . . . , 1, 1, 2n, . . . ] = 1 + ,
1
0+
1
1+
1
1+
2+ ..
.
é o mesmo que
1
[2; 1, 2, 1, 1, 4, 1, 1, 6, 1, 1, 8, . . . , 1, 1, 2n, . . . ] = 2 + ,
1
1+
1
2+
1
1+
1+ ..
.
A primeira fração periódica não segue o padrão que impusemos, porque tem
um coeficiente zero, mas ela pode ser descrita mais facilmente por relações
de recorrência – por isso demonstraremos que ela é a expansão de e em
fração contínua.
Além disso, observe que há um padrão nos coeficientes: eles são descritos
por uma relação de recorrencia de ordem 3: e = [1; 0, 1, 1, 2, 1, 1, 4, 1, . . . ].
logo os coeficientes são
a 3i = 1
a3i+1 = 2i
a3i +2 = 1
i 0 1 2 3 4 5 6 7 8 9
pi 1 1 2 3 8 11 19 87 106 193
qi 1 0 1 1 3 4 7 32 39 71
359
e os descrevermos também como relação de recorrência:
Note que a sequência é descrita com três equações para p e três para q.
Quando demonstrarmos propriedades desta sequência, faremos uma afir-
mação para cada um dos três casos (3n, 3n + 1, 3n + 2).
Agora definimos três sequências, Ak , Bk e Ck , cada uma definida por uma
integral:
Z1
xn (x − 1)n x
An = e dx
0 n!
Z1
xn+1 (x − 1)n x
Bn = e dx
0 n!
Z1
xn (x − 1)n+1 x
Cn = e dx
0 n!
An = q3n e − p3n
Bn = p3n+1 − q3n+1 e
Cn = p3n+2 − q3n+2 e
A0 = e − 1,
B0 = 1,
C0 = 2 − e,
e que
360
n = 0 nas integrais, a relação de recorrência é satisfeita:
A0 = q3(0) e − p3(0) = q 0 e − p0 = e − 1
B0 = p3(0)+1 − q3(0)+1 e = p1 − q1 e = 1
C0 = p3(0)+2 − q3(0)+2 e = p2 − q2 e = 2 − e
Teorema 15.39.
e = [1; 0, 1, 1, 2, 1, 1, 4, 1, 1, 6, . . . , 1, 1, 2n, . . . ]
lim (qi e − pi ) = 0.
i→∞
Como qi ≥ 1 e i ≥ 2, temos
pi
e = lim .
i→∞ qi
361
Suponha que e seja racional: e = p/q, com p, q ∈ N. Então
∞
p X 1
e= =
q k!
k=0
∞
p X q!
q! =
q k!
k=0
X∞
q!
(q − 1)!p =
k!
k=0
Xq X∞
q! q!
= + .
k! k!
k=0 k=q+1
| {z } | {z }
A B
O lado esquerdo, (q − 1)!p, é inteiro, portanto o lado direito deve ser tam-
bém. Mas A é claramente inteiro, porque
q! q! q!
A= + + ···
1 2 q!
= q! + [3 · 4 · q] + · · · + [(q − 2)(q − 1)q] + [(q − 1) · q] + 1.
Assim, B deve também ser inteiro. Mas mostraremos que (i) B > 0, e
(ii) B < 1, de forma que B não pode ser inteiro, levando a uma contradição.
Para (i), note que os termos de B são todos maiores que zero. Para (ii),
basta calcular
∞
X q!
B=
k!
k=q+1
X∞
1
=
(q + 1)(q + 1) · · · k
k=q+1
X∞
1
<
(q + 1)k
k=q+1
X∞
1
<
(q + 1)k
k=1
!
1 1
= 1
q+1 1− q+1
1
=
q
< 1.
362
15.7 π é irracional
Uma vez que são conhecidos muitos dos primeiros dígitos de π, também
conhecemos muitos dos primeiros coeficientes de sua expansão em fração
contínua,
π = [3; 7, 15, 1, 292, 1, 1, 1, 2, 1, 3, 1, 14, 2, 1, . . . ]
No entanto, não conhecemos forma fechada para estes coeficientes – o que
é o mesmo que dizer que não conhecemos uma descrição completa da ex-
pansão de π em frações contínuas simples, da forma como as definimos. No
entanto, há várias expansões de π em frações contínuas onde as regras de
formação que impusemos são quebradas. Algumas delas são
4 4
π= 2
π=
1 12
1+ 2
1+
2 32
3+ 2+
32 52
5+ 2+
42 72
7+ 2+
9+ .. 2+ .
. . .
1 π 1
π=3+ 2 =1+
32 1
6+ 1+
52 1
6+ 1/2 +
72 1
6+ 1/3 +
92 1/4 + .
. .
6+
6+ .
..
Nesta seção não derivaremos uma fração contínua para π; ao invés disso,
obteremos a expansão de tan(x) em fração contínua, e dela concluiremos
que π2 e π são irracionais – esta é em essência a mesma demonstração dada
por Johann Lambert em 1761.
Lema 15.40. Se
a1
x= a2
b1 + a3
b2 + a4
b3 +
b4 + ..
.
363
Lema 15.41.
x
tan(x) =
x2
1−
x2
3−
5− ..
.
π a
= , a, b ∈ Z.
4 b
Substituimos π/4 por a/b na expansão em fração contínua de tan(π/4):
π a
tan = tan .
4 b
Como tan(π/4) = 1, podemos igualar 1 à expansão em fração contínua de
tan(a/b):
a
b
1=
a2
b2
1−
a2
b2
3−
a2
b2
5−
7− ..
.
a
=
a2
b−
a2
3b −
a2
5b −
7b − ..
.
364
15.8 φ é irracional
O valor φ, também chamado de razão áurea, é definido como segue. Para
quaisquer números reais, a, b, com a > b > 0, se
a a+b
= .
b a
então φ = a/b.
Isto implica que
a+b
φ=
a
a b
= +
a a
b
=1+
a
1
=1+ ,
φ
φ2 − φ − 1 = 0.
o que implica que p|q2 , e poratnto p e q tem um fator comum. Como presu-
mimos que isto não acontece, somos obrigados a admitir que p seja 1. Mas
365
isso implicaria que
1
q= ,
φ
que não é inteiro.
15.9 Exercícios
Ex. 324 — Represente 2/3, 20/3, 11/13 e 21/13 como frações contínuas.
Ex. 325 — Expanda as frações contínuas como números racionais: [0; 1, 2, 3],
[0; 3, 2, 1], [0; 10, 10, 10], [1; 9, 9].
√ √
Ex. 326 — Determine as expansões de 11 e 12 como frações contínuas.
√
Ex.
√ 327 — Obtenha a expansão de 5 em fração contínua, e conclua que
5 é irracional.
√
Ex. 328 — Determine a expansão em fração contínua de (b+ b2 − 4ac)/2a.
a1 a2
<x< .
b1 b2
Prove que uma das duas frações deve ser convergente na expansão de x.
366
Ex. 330 — Seja x = [x0 ; x1 , x2 , . . . ] um número irracional, e sejam y1 , y2 , . . .
uma sequência de inteiros positivos. Prove que
lim [x0 ; x1 , . . . , xk , y1 , y2 , . . . ] = x
k→∞
Ex. 333 — Dado um intervalo, como determinar o racional dentro dele que
tenha o menor numerador e o menor denominador? (Dica: represente as
extremidades como frações contínuas).
x0 −1 0 ··· 0 0
1 x1 −1 0
..
0 1 . 0
Pk =
.
..
.. .
0 xn−1 −1
0 0 0 ··· 1 xk
367
Para cada vetor v = (x, y), com x, y ∈ Q, é possível definir uma sequência
a b x
svn = ,
0 c y
1, 999 · · · = 2,
2, 5999 · · · = 2, 6.
Prove, usando a construção de reais que demos neste Capítulo, que 0, 999 · · · =
1.
368
Capítulo 16
• com a régua, retas podem ser traçadas passando por dois pontos;
369
Para um exemplo simples de construção com régua e compasso, examina-
mos a bisecção de um ângulo. São dadas duas retas não paralelas que se
interceptam em um ponto O. Marcamos dois pontos, um em cada reta, e
a uma mesma distancia de O. Nomeamos os pontos A e B. Desenhamos
dois círculos, um com centro em A, e um com centro em B; o raio deve ser
maior que a distância de A até B. Estes dois círculos se interceptam em dois
pontos; tomamos um deles, C, e a reta OC é a bissetriz do ângulo dado.
B
C
O
A
370
Determinaremos agora quais números são construtíveis. Gradualmente iden-
tificaremos conjuntos numéricos. O primeiro conjunto de números constru-
tíveis será o dos inteiros (Z) – os pontos inteiros no eixo real.
Assim, verificamos a seguir que podemos identificar os eixos real e imagi-
nário, e construir todos os pontos inteiros nesses eixos.
A B C
Com isso provamos que os números da forma (k, 0), com k ∈ Z, são constru-
tíveis (e portanto Z é construtível).
371
B
372
a + bi
b
373
a + bi
374
os componentes real e imaginário separadamente, isto bastará. Geometri-
camente, se pudermos somar as coordenadas separadamente nos dois eixos,
a + a 0 e b + b 0 , o Lema 16.51 garante que a partir dessas novas coordenadas
podemos construir (a + a 0 ) + (b + b 0 )i.
Dados a e a 0 no eixo real, temos a distância da origem até a 0 . Criamos um
círculo centrado em a com raio igual a essa distância, e um dos pontos de
interseção do círculo com o eixo é a + a 0 ; o outro é a − a 0 .
a0 0 a − a0 a a + a0
Passamos à multiplicação.
a+ a b+i
bi
0 a b
O ponto obtido é a + (a/b)i, e pelo Lema 16.5, é possível obter (a/b)i e a/b.
O procedimento inverso pode ser usado para obter ab a partir de a e b.
ser construídos.
375
O conjunto C , além de ser um corpo, tem outra propriedade – é fechado para
a extração de raízes quadradas.
(1 + r)/2
0 1 r
Agora trace uma perpendicular ao eixo real, passando pelo um. Ela inter-
√
ceptará o círculo nos pontos 1 ± r i. Isto pode ser facilmente verificado
usando o Teorema de Pitágoras.
b c
r 1
a= +
2 2
1+r
c=
2
√ √
eb= c2 − a2 resulta em r.
√ √
2k
É interessante que, sendo possível calcular x, pode-se calcular x, para
todo k ∈ N, já que
√ √
q
2k 2k−1
x= x.
O fato de podermos extrair raízes quadradas implica que C é superconjunto
estrito de Q[i]. E, como os números construídos são todos complexos,
Q[i] ⊂ C ⊆ C.
376
Na próxima seção mostraremos que a segunda inclusão também é estrita
(C ⊂ C).
(x − a)2 + (y − b)2 = e
(x − c)2 + (y − d)2 = f,
377
simples: o resultado será a solução de um sistema da forma
ax + by = e,
(x − c) + (y − d)2 = f,
2
• Trisecção de um ângulo
A trisecção de um ângulo α com régua e compasso consiste em obter
pontos que determinem duas retas formando um ângulo α/3.
Seja α igual a 60o , ou π/3. A trisecção deste angulo nos daria ângulos
de 20o , ou π/9. Mas se este ângulo pudesse ser construído, a distância
dad pelo seu cosseno também o seria (pela definição de cosseno, basta
baixar um aperpendicular). No entanto, cos π/9 é raiz de
8x3 − 6x − 1,
que provar que de fato este polinômio não é redutível em Q – o que fica fora do escopo deste
texto.
378
• Quadratura do círculo
Obter a “quadratura de um círculo” é, dado um círculo, construir um
quadrado com a mesma área.
Considere um círculo com raio unitário: sua área é π. Um quadrado
√
com área π precisaria ter lado com comprimento igual a π, que não
é construtível.
Exercícios
Ex. 338 — Dados dois pontos A e B, mostre como construir um quadrado
tendo como um dos lados o segmento AB.
Ex. 341 — Números algébricos são raizes de equações polinomiais com co-
eficientes racionais. Por exemplo, 1 + 2i é algébrico, porque é raiz da equa-
ção x4 − 4x3 + 10x2 − 12x + 5 = 0; A razão áurea é um número algébrico,
porque é raiz da equação x2 − x − 1 = 0; já π não é algébrico, porque não é
raiz de qualquer equação linear com coeficientes racionais. Denote o con-
junto dos números algébricos por A. Qual a relação entre A e C ? Um está
contido no outro?
Ex. 342 — Dados os pontos 0+0i e 1+0i, como é possível construir o ponto
cos(π/6) + sin(π/6)i?
Ex. 343 — Se for possível usar uma régua com dois pontos diferentes mar-
cados, as construções realizadas não são mais as clássicas construções Eu-
clideanas com régua e compasso. Mostre que, com uma régua dessas, é
possível realizar a trisecção de qualquer ângulo.
379
380
Apêndices
Apêndice A
Dicas e Respostas
a2 + b2 = c2
a 2 b 2
+ =1
c c
Resp. (Ex. 17) — Duas matrizes invertíveis podem ser somadas resultando
em uma singular. O conjunto não seria fechado para soma.
00
‘‘ an xn + an−1 xn−1 + · · · + a0
=an ⊗ x
| ⊗x⊗
{zx · · · x} ⊕ an−1 ⊗ x
| ⊗x⊗
{zx · · · x} ⊕ · · · ⊕ a0
n vezes x n−1 vezes x
(⊗ → + )
=an + x {zx · · · x} ⊕ an−1 + x
| +x+ {zx · · · x} ⊕ · · · ⊕ a0
| +x+
n vezes x n−1 vezes x
383
Resp. (Ex. 21) — Só haverá um símbolo a usar, e a quantidade dele é a
quantidade representada (diferente do esquema apresentado no texto!) Note
que, usando somente o dígito 1, ainda vale
X
k
n= dk 1k .
i=0
n = 1 · 12 + 1 · 11 + 1 · 10
=1+1+1
= 3.
1 a1 a2 an
= + + ... + n,
7 60 602 60
Simplifique o lado direito, de forma a manter 60n no denominador.
b = aq + r, 0 ≤ r < a.
384
Resp. (Ex. 50) — A inversa de matriz 2 × 2 tem forma fechada bastante
simples. Veja ali que será necessário que os números
a b
,
a2 − b2 a2 − b2
sejam inteiros.
Resp. (Ex. 63) — Uma que evidentemente pode ser tentada é usando a fór-
mula de Euler-Binet (basta escrever os termos de maneira adequada). Outra
possibilidade é usando a igualdade de Honsberger, e aplicando indução.
Resp. (Ex. 82) — Fatore. Nenhum deles tem mais que três divisores pri-
mos distintos.
385
k ∈ X tal que kd 0 = d. Mas então
X
!
v i
ai x = menor i tal que ai 6= 0.
i
d < c,
n
d< ,
d
d2 < n,
√
d < n.
√
Resp. (Ex. 99) — Presuma k
n = a/b, com mdc (a, b) = 1. O que acontece
se b > 1?
Resp. (Ex. 101) — Suponha que p < q são primos consecutivos, e que p +
386
q = 2t. Então t = (p + q/2), e claramente, p < t < q. Mas t, estando entre
p e q, não pode ser primo, porque p e q são primos consecutivos.
p + 1 p-1
mdc , = 2 mdc (p + 1, p-1)
2 2
= 2 mdc (p + 1-(p-1), p-1)
= 2 mdc (2, p-1)
p-1
= mdc 1,
2
= 1.
Resp. (Ex. 103) — Todo Fn deixa resto dois quanto dividido por 5, e são
todos ímpares.
Resp. (Ex. 111) — (Dica) s + t tem um fator que não está dentre os fatores
de A.
Resp. (Ex. 112) — mas não ambos. Logo, nenhum primo divide s + t, e
s + t > 1 seria um novo primo, não listado antes.
100
Resp. (Ex. 120) — Ache o expoente de 2 na fatoração de n .
387
Resp. (Ex. 127) — 6/pi2 .
Para resolver: comece olhando para a probabilidadede um inteiro qualquer
k dividir os dois números; a de um número ser o MDC de ambos; e a desse
último número ser 1.
Primeiro, não existe o caso em que todos são divisíveis por 3, porque mdc (x, y, z) =
1.
Assim, não é possível que tanto 3 | x como 3 | y, porque se assim fosse, 3 | z
e cairíamos no mesmo problema (mdc (x, y, z) = 1).
Agora, por absurdo, suponha que nem x nem y sejam zero módulo 3 (ou
seja, 3 - x, 3 - y). Então
x, y ≡ ±1 (mod 3)
Isso porque
x2 + y2 = 3k + 2, z2 = 3r + 1 ou 3r.
Mas então,
x2 + y2 = z2
3k + 2 = 3r + 1 ou 3r
3(k − r) = 1 − 2 ou − 2
3(k − r) = −1 ou − 2,
Resp. (Ex. 143) — A equação diofantina tem soluções, mas nenhuma com
x e y positivos:
−22(30) + 44(18) = 132
A forma geral da solução é
388
Mas precisamos então de
Ou seja,
22
k> ≈ 1.222
18
44
k< ≈ 1.466,
30
e não existe k ∈ Z que possamos usar.
Resp. (Ex. 144) — k > −30.75, e como k deve ser inteiro, k ≥ −30.
Resp. (Ex. 147) — Está claro, pela presença de “(p − 1)!” no enunciado,
que o teorema de Wilson será usado. O expoente p − 1 indica que o pequeno
teorema de Fermat (ou o de Euler) também é útil.
Resp. (Ex. 148) — Escreva (p − 1)!, escreva (p − 1)!/(p − n)!, use o teorema
de Wilson.
Resp. (Ex. 163) — Lembre que dois uns consecutivos reiniciam a sequên-
cia.
pn+1 −1
Resp. (Ex. 168) — σ(pn ) = p−1 d(pn ) = n + 1
√
Resp. (Ex. 170) — n = ab. σ(n) > n + a + b + 1. Se a < n, então o que
ocorre com b?
389
os divisores são 1, 22 , 23 , . . . , p1 , p21 , . . . , p2 , p22 , . . .. Escreva σ(n):
√ √
Resp. (Ex. 190) — n ≤ 2π(n) n, e depois chegue a 2πn ≥ n, e π(n) ≥
√
log n.
Resp. (Ex. 213) — {−13, −11, −9, −7, −5, −3, −1, 1, 3, 5, 7, 9, 11}.
ab = c
ac = d
Então
aab = ac = d,
mas
aab = eb = b,
e como a operação não é associativa – a(bb) 6= (aa)b – teríamos b = d.
390
Resp. (Ex. 223) — Não – mostre que não são incongruentes (mod m).
k
Resp. (Ex. 225) — φ é multiplicativa; g2p − 1 é par ou ímpar? O que sig-
k
nifica g2p (mod 2pk )?
1 2
4 8
7 11
13 14
1 2 4 8
11 7 14 13
Resp. (Ex. 251) — (i) use a fórmula para a soma dos n primeiros quadra-
dos; (ii) lembre que os resíduos quadráticos são distribuídos simetricamente
ao redor de zero (ou, equivalentemente, ao redor de (p − 1)/2).
Apostol, Tom. Introduction to Analytic Number Theory. New York, NY: Springer, 1976.
9
391
Resp. (Ex. 255) — Pense na existencia de raiz quarta primitiva da unidade
em Up .
Resp. (Ex. 270) — Não é (ou seja, (17/401) = −1). Use a lei da reciproci-
dade quadrática e propriedades do símbolo de Jacobi.
a2 c2
n= +
b2 d2
e chege a
depois argumente que nb2 é representável; que por isso nb2 (e consequen-
temente n) não tem fatores 4k + 1.
392
Resp. (Ex. 285) — Comece com 4a (8k + 7) = 4a (8k + 6) + (2a )2 . Depois,
4a (8k + 6) + (2a )2 = x2 + y2 + z2 . Com w = 2a o resultado segue.
A B
√
3
√
3
Resp. (Ex. 341) — Claramente, 2 ∈ / C , mas 2 ∈ A. Além disso, da de-
monstração do Teorema 16.12, todo número construtível é algébrico. Por-
tanto,
C⊂A
393
394
Produção do Livro
395
396
Índice Geral
397
Chebychev convolução de, 172
teorema de, 189 discriminante, 280, 285
co-primos, 89 fundamental, 289
coeficientes parciais (de fração divide, 55
contínua), 341 para inteiros quadráticos,
combinação linear inteira, 59 330
complexidade divisão, 58
do algoritmo de Euclides, 75 domínio Euclideano, 82
composição domínio fundamental, 316
de formas quadráticas, 300
composto Eisenstein
em anel de inteiros demonstração da Lei da
quadráticos, 331 Reciprocidade
congruência, 114 Quadrática, 238
linear em n variáveis, 144 Lema de, 239
não linear, polinomial, 144 elemento irredutível, 106
polinomial, 144 equação diofantina, 127
conjugado linear, 127
em corpo quadrático, 326 equivalência
construção de pontos em H, 315
com régua e compasso, 369 espaço métrico, 356
conteúdo de polinômio, 108 completo, 357
convergente, 346 Euclides
convolução de Dirichlet, 172 algoritmo de (complexidade),
Conway 75
função base 13, 47 algoritmo de (para o MDC),
corpo, 34, 37 63
dos números tropicais, 37 algoritmo estendido de, 65
extensão de, 323 lema de, 61
quadrático, 325 Euler
quadrático imaginário, 325 critério de, 227
quadrático real, 325 Teorema de, 200
crescimento de π(n), 189 extensão
critério de Euler, 227 de corpo, finita, 324
de corpo, grau de, 324
de Moivre extensão de corpo, 323
fórmula de, 215 extensão de um corpo, 323
delta
de Kronecker, 160 fatoração única, 90
descida infinita, 24 Fermat
determinante método da descida infinita,
de forma quadrática, 280 24
diagrama de Ferrer, 335 número de, 97
Dirichlet pequeno Teorema de, 201
398
primo de, 97 geradora, 334
Ferrers multiplicativa, 167
diagrama de, 335 funções aritméticas, 159
Fibonacci fórmula
coelhos imortais, 69 de de Moivre, 215
números de, 70
Gauss
números, módulo m, 151
demonstração da Lei da
período d esequencia módulo
Reciprocidade
m, 152
Quadrática com raízes
sequência de, 70
da unidade, 244
forma bilinear, 277
demonstração da Lei da
simétrica, 278
Reciprocidade
forma quadrática, 278
Quadrática por indução,
binária, 277, 278, 284 234
determinante, 280 Lema de, 255
grau de, 278 Lema de, para polinômios,
principal, 285 109
reduzida (positiva definida), soma de, 245
291 geometria hiperbólica, 8
semirreduzida (positiva gerador de grupo, 212
definida), 291 grau
ternária, 303 de extensão de corpo, 324
ternária integral, 303 de forma quadrática, 278
formas modulares, 313 grau de congruência polinomial,
formas quadráticas 144
composição de, 300 grupo, 209
concordantes, 300 abeliano, 209
definidas, 281 comutativo, 209
indefinidas, 281 cíclico, 212
formas quadráticas binárias de resíduos quadráticos
equivalentes, 283 módulo n, 227
fração contínua de unidades de inteiros
coeficientes parciais, 341 quadráticos, 331
eventualmente periódica, de unidades módulo n, 214
353 linear especial, 314
finita, 341 linear geral, 314
infinita, 345 modular, 314
infinita simples, valor de, 349 grupo modular, 313
simples, 341
Hensel
função
Lema de, 146
aritmética, 160
base 13 de Conway, 47 inclusão-exclusão - em nota de
de Merten, 195 rodapé, 164
399
indução finita, 9 primo de, 94
integral Merten
forma quadrática ternária, função de, 195
303 Moebius
inteiro Teorema (fórmula) da
em corpo quadrático, 327 inversão, 177
Gaussiano, 76 multiplicação (de naturais), 18
Gaussiano (norma de), 78 máximo divisor comum, 58
quadrático, 327 métrica, 356
inteiros, 30 mínimo múltiplo comum, 68
racionais, 30
invariante, 285 norma
inverso módulo m, 118 de inteiro Gaussiano, 78
irracional em corpo quadrático, 326
quadrático, 353 em domínio Euclideano, 82
irracionalidade número
de φ, 365 de classe de discriminante
de π fundamental, 296
√, 363
de 2, 344 de Fermat, 97
de e, 358 de Fibonacci, 70
de Mersenne, 94
Kronecker inteiro, 33
δ de, 160 inteiro Gaussiano, 76
irracional quadrático, 353
Legendre-de Polignac perfeito, 94
Teorema (fórmula de), 183 triangular, 14
Lema números
de Bézout, 59 construtíveis, 370
de Eisenstein, 239 de Fibonacci, módulo m, 151
de Euclides, 61 inteiros, 30
de Gauss, 255 irracionais, 344
de Gauss para polinômios, naturais, 6
109 racionais, 30
de Hensel, 146 tropicais (corpo dos), 37
Lucas
Teorema de, 111 ordem
de elemento em sistema de
matriz resíduos, 203
de Redheffer, 196 de raiz da unidade, 219
meio-plano superior, 315 parcial, 21
melhor aproximação, 350 ordem de p em n, 92
menor ou igual, 20 ordenação dos naturais, 20
Mersenne
número de, 94 par de Moebius, 177
400
partição, 30 demonstração de Rousseau,
partição de um inteiro, 334 235
partições de um inteiro, 333 demonstração geométrica de
representação gráfica, 335 Eisenstein, 238
Pascal Teorema da, 232
triângulo de, 10, 111 Redheffer
pertinência a expoente módulo matriz de, 196
m, 203 região fundamental, 316
período relação
de Pisano, 152 de equivalência, 31
de sequência de Fibonacci de ordem parcial, 21
módulo m, 152 representação
Pisano de inteiro como dois
período de, 152 quadrados, 257
plano complexo, 76 de inteiro por forma
polinômio quadrática, 282
conteúdo de, 108 própria de inteiro como dois
primitivo, 108 quadrados, 257
primo, 89 regular, 326
das formas 4n + 1 e 4n + 3, resto, 58
102 resíduo quadrático, 227
de Fermat, 97 reticulado, 76
de Mersenne, 94 Rousseau
em anel de inteiros demonstração da Lei da
quadráticos, 331 Reciprocidade
Quadrática, 235
quociente, 58 régua e compasso
construção com, 369
racionais, 30
radical, 192 sequência de Cauchy, 356
raiz da unidade, 215 sistema completo de resíduos,
ordem de, 219 198
raiz primitiva, 202 sistema reduzido de resíduos,
raiz primitiva da unidade, 219 198
razão áurea, 70 solução singular para
raízes da unidade congruência polinomial,
demonstração da Lei da 146
Reciprocidade soma (de naturais), 18
Quadrática, 244 soma de dois quadrados, 257
reciprocidade quadrática, 231 soma de Gauss, 245
demonstração de Gauss com soma de quadrados, 257
raízes da unidade, 244 soma de quatro quadrados, 261
demonstração de Gauss por soma de três quadrados, 266
indução, 234 subgrupo, 213
401
sucessor, 7 313
série formal de potências, 334 traço, 326
símbolo tripla pitagórica, 25
de Jacobi, 229 triângulo
de Legendre, 229 retângulo, 25
triângulo de Pascal, 10, 111
Teorema tropicais
Chinês dos restos, 131 corpo dos números, 37
da inversão de Moebius, 177
um (definição como sucessor do
da reciprocidade quadrática,
zero), 18
232
unidade
de Chebychev, 189
em anel, 35
de Euler, 200
em grupo de inteiros
de Fermat (pequeno), 201
quadráticos, 330
de Legendre-de Polignac,
183 valor de fração contínua infinita
de Lucas, 111 simples, 349
de Wilson, 122 valor intermediário
do valor intermediário, 47 teorema, 47
fundamental da aritmética,
91 Wilson
transformação linear fracionária, Teorema de, 122
402
Índice de Pessoas
403
404
Referências
Andrews, George. Number Theory. New York: Dover, 1994. Página 42.
405
Bondarenko, Boris. Generalized Pascal Triangles and Pyramids.
[S. l.]: The Fibonacci Association, 1993. Disponível em
[Link] Página 11.
Boyer, Carl B. A History of Mathematics. [S. l.]: Wiley, 1991. Página 41.
406
Colebrooke, Henry Thomas. Algebra, with Arithmetic and
mensuration, from the Sanscrit of Brahmegupta and Bháscara.
[S. l.]: London J. Murray, 1817. Disponível em
[Link] Página 134.
Dedekind, Richard. Was sind und was sollen die Zahlen? [S. l.], 1888.
Publicado como brochura. Página 6.
Euclid. The Elements. [S. l.]: Green Lion Press, 2002. Edição bilíngue
Inglês/Grego. Páginas 25, 61, 63, 89, 94.
407
[Link]
Página 333.
Hensel, Kurt. Neue Grundlagen der Arithmetik. Journal für die reine
und angewandte Mathematik, v. 127, p. 51–84, 1904. Página 146.
408
Hiscocks, John. Triangle Numbers in the History of Mathematics.
Teaching Mathematics and its Applications, v. 9, n. 2, 1990. Página 14.
409
Newcomb, Simon. Note on the Frequency of Use of the Different Digits in
Natural Numbers. American Journal of Mathematics, v. 4, n. 1,
p. 39–40, 1881. Página 52.
Ore, Oystein. Number Theory and Its History. New York: Dover
Publications, 1976. Páginas 42, 121.
410
Russel, Bertrand. Introdução à Filosofia Matemática. [S. l.]: Zahar,
1974. Página 6.
Sun Tzu. A Arte da Guerra. [S. l.]: Edipro, 2021. Sun é nome; Tzu é título
(mestre). Edição bilíngue. Há também uma tradução para o Inglês,
livremente disponível em
[Link]
Página 132.
411
Waring, Edward. Meditationes Algebraicae. 3. ed. [S. l.]: J. Archdeacon,
1782. Disponível em [Link]
century_meditationes-algebraic_waring-edward-lucasian_1770. Existem
traduções para o Inglês. Página 121.
Yong, Lam Lay; Se, An Tian. Fleeting Footsteps. [S. l.]: World Scientific
Publishing Company, 2004. Páginas 132, 133.
Yong, Ke-Xin Au. Qin Jiushao and His Mathematical Treatise in Nine
Sections in Thirteenth-Century China. 2011. Diss. (Mestrado) –
University of Alberta. Página 133.
412