TEORIA DOS NUMEROS´ - UnB

1 UNIVERSIDADE DE BRASI LIA. DEPARTAMENTO DE MATEMA TICA -IE. TEORIA DOS NU MEROS. Texto de aula Professor Rudolf R. Maier Versa o atualizada 2005. Estas notas sa o o resultado da experie ncia nas aulas do curso do mesmo t tulo, proferido regularmente pelo autor neste Departamento de Matema tica. Durante o curso e na elaborac a o destas notas fizemos livre uso e seguimos com modificac o es e complementac o es a linha do livro ELEMENTARY NUMBER THEORY. de David M. Burton Revised Printing University of New Hampshire Allyn and Bacon, Inc. Boston London Sydney Toronto c 1980. I ndice 1 Resultados Preliminares .. 1. O princ pio da induc a o O teorema binomial n km X. As fo rmulas para Sn (m) =. k=1. Os nu meros triangulares Algumas observac o es sobre lo gica elementar Diferenc a de dois quadrados 2 TEORIA de divisibilidade nos nu meros inteiros .. 21. O algoritmo geral de divisa o Ma ximo divisor comum de dois nu meros Nu meros relativamente primos O algor tmo Euclidiano O m nimo mu ltiplo comum Equac o es Diofantinas 3 Nu meros primos e sua distribuic a o.

2 34. O teorema fundamental da aritme tica A quantidade dos divisores de um nu mero n A decomposic a o prima ria de n! Estimativas sobre quantidades de primos A func a o dos nu meros primos Decomposic a o de nu meros e o crivo do Erato stenes A conjetura de Goldbach Progresso es aritme ticas e primos Polino mios e primos 4 Triplos Pitago ricos e a conjetura de Fermat .. 53. Triplos Pitago ricos A conjetura de Fermat i 5 Nu meros deficientes-abundantes-perfeitos e de Mersenne .. 61. Nu meros deficientes, abundantes e perfeitos O teorema de Euclides/Euler Nu meros de Mersenne 6 A TEORIA das congrue ncias .. 69. Divisibilidade e congrue ncias Congrue ncias lineares Congrue ncias simulta neas e o teorema do resto chine s 7 Os Teoremas de Fermat e de Wilson .. 78. O pequeno teorema de Fermat O teorema de Wilson 8 Congrue ncias quadra ticas e a lei da reciprocidade quadra tica de Euler/Gauss .. 85. Restos quadra ticos Um Lema de Euler O s mbolo de Legendre Um Lema de Gauss.

3 O s mbolo de Legendre p2. A lei da reciprocidade quadra tica Mais alguns s mbolos de Legendre especiais 9 Representac a o de inteiros como soma de quadrados .. 105. Soma de dois quadrados Soma de tre s quadrados Soma de quatro quadrados (o teorema de Lagrange). 10 A func a o de Euler .. 114. Restos relativamente primos e a func a o . O teorema de Euler Mais algumas propriedades da func a o . 11 Ra zes primitivas .. 123. Ordens mo dulo n e ra zes primitivas Existe ncia de ra zes primitivas. ii TEORIA DOS NU MEROS. Notas de aula - Versa o atualizada 2005. Prof. Rudolf R. Maier 1 Resultados Preliminares A TEORIA dos Nu meros, a mais pura disciplina dentro da mais pura das Cie ncias - da Matema tica - tem uma longa histo ria, originando-se nas antigas civilizac o es da hu- manidade. Listamos primeiro alguns nomes famosos de matema ticos que voltara o a aparecer no contexto do nosso curso: Pitagoras (569-500 a.)

4 C.). Euclides ( 350 a. C.). Erato stenes (276-196 a. C.). Diofantos ( 250 d. C.). Plutarco ( 100 d. C.). Marin Mersenne (1588-1648). Pierre de Fermat (1601-1665). Blaise Pascal (1623-1662). Christian Goldbach (1690-1764). Leonhard Euler (1707-1783). Joseph Louis Lagrange (1736-1813). John Wilson (1741-1793). Adrien Marie Legendre (1752-1833). Carl Friedrich Gauss (1777-1855). Augustin Louis Cauchy (1789-1857). Peter Gustav Dirichlet (1805-1859). P. L. Tchebychef (1821-1894). Frederick Nelson Cole (1861-1927). Axel Thue (1863-1922). Jacques Salomon Hadamard (1865-1963). Charles de la Valle e Poussin (1866-1962). 1. Dedicaremos os nossos estudos durante este curso a s propriedades dos nu meros inteiros racionais. Lidaremos enta o com o conjunto n o ZZ = .. , 3, 2, 1, 0, 1, 2, 3 , .. dos nu meros inteiros e seus subconjuntos, particularmente com os subconjuntos n o n o IN0 = 0, 1, 2, 3 , .. e IN = 1, 2, 3.

5 Dos nu meros inteiros na o-negativos e dos nu meros naturais. Iniciamos, lembrando exemplos de algumas sequ e ncias importantes no conjunto IN dos nu meros naturais: Exemplo. Sequ e ncias importantes em IN sa o: A sequ e ncia a) (n) = (1, 2, 3 , .. , n , ..) de todos os nu meros naturais, n IN. b) (2n) = (2, 4, 6 , .. , 2n , ..) dos nu meros naturais pares, n IN. c) (2n 1) = (1, 3, 5 , .. , 2n 1 , ..) dos nu meros mpares, n IN.. d) n2 = 1, 4, 9 , .. , n2 , .. dos quadrados perfeitos, n IN.. e) n3 = 1, 8, 27 , .. , n3 , .. dos cubos perfeitos, n IN. f) (2n ) = (2, 4, 8 , .. , 2n , ..) das pote ncias de 2. n IN. g) (pn ) = (2, 3, 5 , .. , pn , ..) dos nu meros primos, n IN. h) etc. Dizemos tambe m: n e o n-e simo nu mero natural, 2n e o n-e simo nu mero par, 2n 1 e o n-e simo nu mero mpar, n2 e o n-e simo quadrado perfeito, etc. Temos duas operac o es internas em IN0 e tambe m em ZZ a adic a o + e a multi- plicac a o as quais queremos admitir sem mais explicac o es.

6 A ordem natural em ZZ e dada por: n, m ZZ temos m n a equac a o m + x = n possui uma soluc a o x IN0 . Uma fundamantal propriedade do conjunto IN dos nu meros naturais e : 2. O princ pio da induc a o. Todo conjunto na o vazio S de nu meros naturais possui um elemento m nimo. Em s mbolos: S IN , S 6= 6 O , m S tal que m n n S. Deste princ pio segue a importante Proposic a o. Seja T um conjunto de nu meros naturais ( T IN ) satisfazendo a s propriedades: a) 1 T. b) Sempre se n T , enta o tambe m n+1 T . Enta o T = IN e o conjunto de todos os nu meros naturais. Demonstrac a o: Suponhamos T 6= IN . Para o conjunto complementar S = IN \ T temos enta o 6 O 6= S IN . Pelo princ pio da induc a o existe m S tal que m n para todos os n S. Como 1 T pela propriedade a), temos 1 6 S, particularmente m > 1. Da concluimos n = m 1 T. Pela propriedade b) temos pore m m = n+1 T , de onde sai o absurdo m S T = 6 O. Isto mostra que S 6= 6 O e imposs vel.

7 Temos que ter S = 6 O e da T = IN . Proposic a o aplica-se para verificar a validade geral de fo rmulas as quais en- volvem nu meros naturais, como mostra o seguinte Exemplo. Para todos os nu meros naturais n vale 1 + 3 + 5 + .. + (2n 3) + (2n 1) = n2 ( ) . Em palavras: A soma dos n primeiros nu meros naturais mpares e o n-e simo quadrado perfeito. ( ). n 2. Demonstrac a o: Seja T = n IN =n o conjunto dos nu meros X. (2k 1). k=1. naturais para os quais a fo rmula ( ) e verdadeira (o conjunto verdade ou o con- junto de validade de ( )). Para mostrar que T = IN , so e preciso verificar a) e b). 3. da Proposic a o para este T : Para n = 1 ( ) simplesmente afirma que 1 = 12 , o que certamente e verdade, ou seja, 1 T . Suponhamos n T para algum nu mero natural n, isto e , 1 + 3 + .. + (2n 1) = n2 . Somando-se 2n+1 a ambos os lados, obtemos 1 + 3 + .. + (2n 1) + (2n+1) = n2 +2n+1 , de onde segue 1 + 3 + .. + (2n 1) + 2(n+1) 1 = (n+1)2.

8 Isto por sua vez significa n + 1 T. Pela proposic a o concluimos que o conjunto verdade da fo rmula ( ) e o conjunto T = IN de todos os nu meros naturais. Exemplo. Para todos os nu meros naturais n e todo real a 6= 1 vale an+1 1. 1 + a + a2 + a3 + .. + an 1 + an = . a 1. Particularmente (quando a = 2) obtemos 1 + 2 + 4 + .. + 2n 1 + 2n = 2n+1 1 . Demonstrac a o: Mais uma vez temos que verificar a asserc a o para n = 1 e para n+1 sob a hipo tese que ela ja e va lida para algum n: a2 1. Para n = 1 simplesmente afirma-se que 1+a = , o que e verdade (porque ?). a 1. Suponhamos, para algum nu mero natural n ja esteja provado an+1 1. 1 + a + a2 + a3 + .. + an 1 + an = . a 1. Somando-se an+1 a ambos os lados, obtemos an+1 1. 1 + a + a2 + .. + an 1 + an + an+1 = + an+1 , a 1. 4. de onde segue 2 n n+1 an+1 1 + (a 1)an+1 a(n+1)+1 1. 1 + a + a + .. + a + a = = . a 1 a 1. Isto diz que a fo rmula continua va lida para n + 1.

9 Concluimos que ela vale para todo n IN . Mencionamos que, a s vezes e conveniente trabalhar com a seguinte generalizac a o de : ' Proposic a o. Seja n0 ZZ um inteiro fixo e seja T 0 umn conjunto de (alguns) nu meros in- teiros maiores ou iguas a n0 ( T 0 n n0 n ZZ ), satisfazendo a s o propriedades: a) n0 T 0. b) Sempre se n0 n T 0 , enta o tambe m n+1 T 0 . Enta o T 0 =. n o n n0 n ZZ e o conjunto de todos os nu meros inteiros maiores ou iguais a n0 . Isto e fa cilmente verificado pela aplicac a o de ao conjunto n n0 + 1 n T 0 . n o T =. Observamos que para este T temos T IN e n0 T 0 e equivalente a 1 T . ( e obtido de volta a partir de ' fazendo-se n0 = 1). A t tulo de ilustrac a o mencionamos o seguinte exemplo. A afirmac a o (correta) que o leitor queira verificar: 2n > n2 para todos os n 5. podemos substituir pela afirmac a o equivalente 2n+4 > (n + 4)2 para todos os n IN. (ou tambe m por 2 n+783 > (n + 783)2.

10 Para todos os n ZZ com n 778, se quisermos). 5. O teorema binomial Se n IN0 entendemos por n! o produto n Y. n! = k =1 2 3 .. n , se n IN. k=1. e acrescentamos 0! = 1 , se n = 0 (produto vazio) . n! le -se: n fatorial. E imediato que se tem 0! = 1! = 1, 2! = 2, 3! = 2! 3 = 6, 4! = 3! 4 =. 24, .. , n! = (n 1)! n, (n+1)! = n! (n+1) , .. Definic a o. Para todo n IN e todos os k IN0 com 0 k n colocamos n n! k = k!(n k)! , nu mero este que se chama o coeficiente binomial n sobre k. Temos as seguintes propriedades dos coeficientes binomiais: Observac a o. Para todo n IN e todos os k IN0 com 0 k n valem n n(n 1) .. (n k+1). a) k = . k! n . n . b) k = n k . n . n . n+1 . c) k + k 1 = k sek 1. n n! n(n 1) (n k + 1) (n k) 2 1. Demonstrac a o: a) k = = =. k!(n k)! k!(n k)! n(n 1) (n k + 1).. k! b) Observamos primeiro que com 0 k n temos tambe m 0 n k n. Pela definic a o temos de imediato . n n! n! n . n k = = = k.