Seja Bem-Vindo ao IMPA.
O tema deste livro é a chamada Teoria dos Números, que é a parte da Matemática que se dedica ao estudo dos números inteiros e seus amigos. Não há dúvidas de que o conceito de inteiro é um dos mais antigos e fundamentais da ciência em geral, tendo acompanhado o homem desde os primórdios de sua história. Assim, é de certa forma surpreendente que a Teoria dos Números seja atualmente uma das áreas de pesquisa mais efervescentes da Matemática e que, mais do que nunca, continue a fascinar e desafiar as atuais gerações de matemáticos. Diferentemente de muitas outras áreas da Matemática, a Teoria dos Números se distingue muito menos por seus métodos mas mais sim por seus problemas, cujo tema comum subjacente é o de número inteiro. Assim, por exemplo, enquanto um analista utiliza-se de métodos analíticos para resolver seus problemas e um algebrista empregue métodos algébricos para atacar questões algébricas, em Teoria dos Números um mesmo problema pode requerer para a sua solução a utilização simultânea de métodos algébricos, analíticos, topológicos, geométricos e combinatórios, além de uma boa dose de imaginação! Talvez seja este aspecto multidisciplinar, aliado à simplicidade de seus conceitos e ao seu caráter fundamental, que torna a Teoria dos Números um dos ramos mais populares em toda a Matemática, cativando pessoas de formação totalmente diversas. Em particular, os quatro autores são matemáticos de áreas diferentes umas das outras e nenhum deles é propriamente um especialista em teoria dos números. A escolha dos temas abordados neste livro pretende justamente ilustrar esta personalidade múltipla da Teoria dos Números. Assim, o leitor encontrará aqui, além dos tópicos já consagrados como próprios da Teoria dos Números, tais como divisibilidade, congruências, primos, raízes primitivas e reciprocidade quadrática, diversos outros na interface com outras disciplinas como Análise, Álgebra e até mesmo Computação: por exemplo, estudamos entre outros o comportamento assintótico de funções aritméticas, a aritmética do anel de inteiros algébricos bem como alguns dos testes de primalidade mais eficientes atualmente conhecidos. A grande maioria dos resultados são clássicos (= vistos em classe) e nossa única contribuição original (além dos erros) é quanto à sua apresentação. Naturalmente a escolha de quais temas foram abordados e quais foram deixados de fora é mais um reflexo do gosto e da experiência pessoal de nós autores do que uma meticulosamente calculada amostragem dos diversos aspectos da teoria. Ainda sim, acreditamos que cada um dos aspectos mais relevantes tenha sido coberto em pelo menos algum trecho do livro, de modo que o leitor não se sentirá frustrado, tenha ele inclinações mais para uma área do que outra! Devo ler este livro? Bem, naturalmente esta é um questão que só você pode responder! Mas vejamos algumas das ``iguarias'' que você estará perdendo se decidir que não: 1- os teoremas caracterizando quais naturais são respectivamente somas de dois, três e quatro quadrados perfeitos (capítulo 4); 2- duas demonstrações da famosa lei de reciprocidade quadrática, um dos resultados favoritos de Gauss (capítulos 2 e 6); 3- o recentemente descoberto algoritmo AKS, que demonstrou que o problema de decidir se um número inteiro é ou não primo pode ser resolvido em tempo polinomial (capítulo 7); 4- o teorema de Lucas-Lehmer, que fornece uma condição necessária e suficiente para que um número da forma 2^p-1 seja primo, e cujo algoritmo correspondente é responsável pelos maiores primos explicitamente conhecidos atualmente (capítulo 7); 5- a utilização de frações contínuas para a obtenção das melhores aproximações racionais de números reais e os teoremas de Khintchine, que quantificam estas melhores aproximações para quase todo número real (capítulos 3 e 8); 6- o teorema da fatoração única em ideais primos no anel de inteiros algébricos de uma extensão finita de Q (capítulo 6); 7- uma introdução à teoria de curvas elípticas, que é um dos temas centrais na Teoria dos Números contemporânea (capítulo 9). Este livro incorpora a maior parte de um livro anterior Primos de Mersenne e outros primos muito grandes sobre números primos escrito por dois dos autores para o Colóquio Brasileiro de Matemática de 1999. Por falar em primos, incluímos o apêndice A, intitulado ``O teorema dos números primos'', escrito por Jorge Aarão. Este apêndice é basicamente a sua dissertação de mestrado, apresentada em 1988 no IMPA, sob a orientação de José Felipe Voloch. Nele são provados o teorema dos números primos e o teorema dos números primos em progressões aritméticas (que implica o teorema de Dirichlet). Trata-se de uma das melhores referências que conhecemos sobre o assunto. Somos muito gratos ao Jorge por ter-nos permitido incluir esse texto em nosso livro. Gostaríamos também de agradecer ao Nivaldo Nunes de Medeiros por suas ótimas sugestões de problemas. Mas a quem exatamente se destina este livro? Na verdade, este livro foi escrito tendo em mente leitores com bagagens técnicas diversas e em diversos estágios de seu desenvolvimento matemático, seja o leitor aluno de graduação, pós-graduação, matemático profissional ou apenas um curioso aficcionado em Matemática. Assim, a exposição não segue um tempo uniforme: ela pode variar desde um largo ou andante, nos capítulos iniciais, até um prestíssimo em certos trechos da segunda parte. Ainda sim, fizemos um genuíno esforço para manter a exposição o mais auto-contida possível, mesmo quando fazemos uso de ferramentas um pouco mais avançadas, que acreditamos porém acessíveis à maioria dos alunos de graduação em cursos de Ciências Exatas (por exemplo). Para facilitar a adoção deste livro em cursos de graduação e pós-graduação, dividimos o livro em duas partes: ``Fundamentos'' e ``Tópicos adicionais bacanas''. A primeira cobre o programa mais ou menos tradicional em cursos de Teoria Elementar dos Números, incluindo temas como divisibilidade, congruências, raízes primitivas, reciprocidade quadrática, equações diofantinas e frações contínuas. Na segunda parte, os capítulos são mais ou menos independentes entre si, e vários trechos podem ser utilizados em seminários, projetos de iniciação científica ou como tópicos especiais em cursos. Em todo caso, excetuando-se os dois primeiros capítulos, cujos resultados são utilizados constantemente ao longo de todo o texto, a leitura não precisa ser ``linear'': o leitor é completamente livre para excursionar pelos diversos temas que o atraírem e apreciar a paisagem nesta, esperamos, agradável viagem. Exemplos e Problemas Propostos Exemplos e exercícios são uma parte importante no aprendizado de qualquer novo assunto e não poderia ser diferente neste livro. Mas, como mencionamos no início, isto é ainda mais verdade em Teoria dos Números, cujo pilar central unificador são exatamente os problemas. Há mais de 80 exemplos e 200 exercícios, de dificuldades as mais variadas, incluindo desde cálculos rotineiros até problemas desafiantes extraídos de diversas Olimpíadas de Matemática ao redor do mundo. Para estes, utilizamos as seguintes abreviações: - AusPol: Olimpíada Austro-Polaca de Matemática - IMO: International Mathematical Olympiad - OBM: Olimpíada Brasileira de Matemática - OIbM: Olimpíada Ibero-americana de Matemática O número razoavelmente grande de problemas de olimpíadas neste livro está provavelmente relacionado ao fato de todos os autores serem ex-olímpicos. Exortamos veementemente o leitor a tentar resolver o maior número possível de problemas. Exercícios matemáticos são de certa forma como exercícios físicos: você não ficará em forma se só olhar outros fazendo... E além disso, problemas matemáticos são como esporte amador: você não tem nada a perder ao tentar, além de serem muito divertidos! Mas não se preocupe se não conseguir resolver alguns problemas deste livro: muitos deles são (ou foram) difíceis para nós também. Confessamos que não resolvemos cada qual dos exercícios, assim pode haver pequenos erros na maneira em que eles são apresentados, e neste caso é parte do exercício obter uma formulação correta. Caso o leitor encare isto com um lapso da parte dos autores, queremos então lembrar os seguintes versos de Goethe: “Irrtum verläss t uns nie, doch ziehet ein höher Bedürfnis Immer den strebenden Geist leise zur Wahrheit hinan.” Erros nunca nos abandonam, ainda sim uma necessidade maior empurra gentilmente nossos espíritos almejantes em direção da verdade. Terminologia Frequente e Notações Utilizamos a já consagrada notação N, Z, Q, R, C para denotar os conjuntos dos números naturais (incluindo o zero), inteiros, racionais, reais e complexos. Além disso, ao longo de todo o livro utilizaremos a seguinte terminologia: 1- Claramente: Nós não estamos com vontade de escrever todos os passos intermediários. 2- Lembre: Nós não deveríamos ter que dizer isto, mas\dots 3- Sem Perda de Generalidade: Nós não faremos todos os casos, então vamos fazer só um e deixar você adivinhar o resto. 4- Verifique: Esta é a parte chata da prova, então você pode fazê-la na privacidade do seu lar, quando ninguém estiver olhando. 5- Esboço de prova: Estamos com muita preguiça de fazer os detalhes, então só listamos alguns passos que fazem parte do argumento. 6- Dica: A maneira mais difícil dentre as várias maneiras de se resolver um problema. 7- Analogamente: Pelo menos uma linha da prova acima é igual à prova deste caso. 8- Por um teorema anterior: Nós não nos lembramos de como era o enunciado (na verdade, não temos certeza se provamos isto ou não), mas se o enunciado está correto, o resto da prova segue. 9- Prova omitida: Acredite, é verdade. Julho de 2010 Fabio, Gugu, Nicolau e ET ``Young men should prove theorems, old men should write books.'' G. H. Hardy ``To get a book from these texts, only scissors and glue were needed.'' J.-P. Serre (comentário ao receber o prêmio Steele por seu livro ``Cours d'Arithmétique'')
I Fundamentos 0 Princípios 0.1 Princípio da Indução Finita 0.2 Princípio da Casa dos Pombos 1 Divisibilidade e Congruências 1.1 Divisibilidade 1.2 mdc, mmc e Algoritmo de Euclides 1.3 O Teorema Fundamental da Aritmética 1.4 Congruências 1.5 Bases 1.6 O Anel de Inteiros Módulo n 1.7 A Função de Euler e o Teorema de Euler-Fermat 1.8 Polinômios 1.9 Ordem e Raízes Primitivas 2 Equações Módulo m 2.1 Equações Lineares Módulo m 2.2 Congruências de Grau 2 2.2.1 Resíduos Quadráticos e Símbolo de Legendre 2.2.2 Lei de Reciprocidade Quadrática 2.3 Congruências de Grau Superior 3 Frações Contínuas 3.1 Reduzidas e Boas Aproximações 3.2 Boas Aproximações são Reduzidas 3.3 Frações Contínuas Periódicas 3.4 Os Espectros de Markov e Lagrange 4 Equações Diofantinas 4.1 Ternas Pitagóricas 4.2 Soma de Quadrados 4.2.1 Soma de Dois Quadrados 4.2.2 Soma de Quatro Quadrados e o Problema de Waring 4.2.3 Soma de Três Quadrados 4.2.4 Teorema de Minkowski 4.3 Descenso Infinito de Fermat 4.3.1 Equação de Markov 4.3.2 Último Teorema de Fermat 4.4 Equação de Pell 4.4.1 Solução Inicial da Equação de Pell 4.4.2 A Equação x^2-Ay^2=-1 4.4.3 Soluções da Equação x^2-Ay^2=c 4.4.4 Soluções da Equação mx^2-ny^2= ±1 5 Funções Aritméticas 5.1 Funções Multiplicativas 5.2 Função de Möbius e Fórmula de Inversão 5.3 Algumas Estimativas sobre Primos 5.3.1 O Teorema de Chebyshev 5.3.2 O Postulado de Bertrand 5.3.3 Outras estimativas 5.4 A Função phi de Euler 5.5 A Função sigma 5.6 Números Livres de Quadrados 5.7 As Funções omega e Omega 5.8 A Função Número de Divisores d(n) 5.9 A Função Número de Partições p(n) 5.10 A Função Custo Aritmético tau(n) II Tópicos adicionais bacanas 6 Inteiros Algébricos 6.1 Inteiros de Gauss e Eisenstein 6.2 Extensões Quadráticas e Ciclotômicas 6.3 Alguns Resultados de Álgebra 6.3.1 Polinômios Simétricos 6.3.2 Extensões de Corpos e Números Algébricos 6.3.3 Imersões, Traço e Norma 6.4 Inteiros Algébricos 6.5 Ideais 6.5.1 Fatoração Única em Ideais Primos 6.6 Grupo de Classe e Unidades 7 Primos 7.1 Sobre a Distribuição dos Números Primos 7.1.1 O Teorema dos Números Primos 7.1.2 Primos Gêmeos e Primos de Sophie Germain 7.1.3 Outros Resultados e Conjecturas sobre Primos 7.2 Fórmulas para Primos 7.3 Testes de Primalidade 7.3.1 Trabalhos Anteriores ao AKS 7.3.2 Testes de Primalidade Baseados em Fatorações de n-1 7.3.3 Teste de Agrawal, Kayal e Saxana 7.4 Primos de Mersenne 7.5 Sequências Recorrentes e Testes de Primalidade 7.6 Aspectos Computacionais 7.6.1 O Algoritmo de Multiplicação de Karatsuba 7.6.2 Multiplicação de Polinômios Usando FFT 7.6.3 Multiplicação de Inteiros Usando FFT 7.6.4 A Complexidade das Operações Aritméticas 7.7 Tabelas 8 Aproximações Diofantinas 8.1 Teoria Métrica das Aproximações Diofantinas 8.2 Aproximações Não-Homogêneas 8.3 O Teorema de Khintchine 8.3.1 O Caso Unidimensional 8.3.2 O Teorema de Khintchine Multidimensional 8.4 Números de Liouville 9 Introdução às Curvas Elípticas 9.1 Curvas Elípticas como Curvas Projetivas Planas 9.2 A Lei da Corda-Tangente 9.3 Curvas Elípticas como Rosquinhas III Apêndices A O Teorema dos Números Primos (por Jorge Aarão) A.1 Os Conceitos Básicos A.1.1 A Função Zeta de Riemann A.1.2 A Função psi(x) A.2 Teoremas Tauberianos e o Teorema dos Números Primos A.2.1 Teoremas Tauberianos A.2.2 O Teorema dos Números Primos A.3 Caráteres de Grupos, L-Séries de Dirichlet e o Teorema em Progressões Aritméticas A.3.1 A Função psi(x; q , l) A.3.2 Caráteres A.3.3 L-séries de Dirichlet A.4 O Lema de Landau A.5 Bibliografia B Sequências Recorrentes B.1 Sequências Recorrentes Lineares B.2 A Sequência de Fibonacci B.3 A Recorrência x^n+1 =x^2_n -2 B.4 Fórmulas Gerais para Recorrências Lineares C Qual o próximo destino? C.1 Alguns comentários e sugestões C.1.1 Fundamentos C.1.2 Leis de Reciprocidade C.1.3 Inteiros p-ádicos C.1.4 Geometria Diofantina C.2 Sugestões Bibliográficas C.2.1 Textos Gerais C.2.2 Textos sobre Teoria Analítica dos Números C.2.3 Textos sobre Aproximações Diofantinas C.2.4 Textos sobre Teoria Algébrica dos Números C.2.5 Textos sobre Curvas Elípticas e Geometria Diofantina Bibliografia Índice Remissivo
