Introdução à teoria dos números

Introdução à teoria dos números

(Parte 1 de 3)

Vıtor Neves

Departamento de Matematica Universidade de Aveiro

Introducao

O presente texto resulta da evolucao de um conjunto de notas de apoio a disciplina Introducao a Teoria dos Numeros do segundo semestre do terceiro ano da licenciatura em Ensino de Matematicada Universidade de Aveiro.

Parafraseando um mestre, nao pretendemos ”escrever para autodidatas, mas sim para alunos com professor”, pelo que deixamos para o leitor demonstrar – por vezes explicitamente como exercıcio – o que e manifestamente rotineiro (nao necessariamente trivial...) ou nos parece estar fora do ambito de um primeiro curso sobre Teoria dos Numeros.

Nao sendo especialistas, limitamo-nos a aspectos classicos e elementares da Teoria, de caracter mais formativo e menos tecnico: a orientacao foi de facto muito forte no sentido de preparar docentes para o ensino secundario.

O capıtulo sobre extensoes do corpo dos numeros reais (Cap. 8) pretende recuperar o estudo das construcoes do corpo real e suas extensoes mais importantes, que deixou de se fazer sistematicamente nas licenciaturas, mas continua a ser importante se se pretende aprofundar o conceito de Numero. As extensoes nao arquimedianas sao afloradas de modo a alertar para a sua existencia e onde podem ser estudadas.

A finalidade principal do texto – apoiar uma disciplina semestral – obrigou a escolhas nao muito agradaveis: por questoes de tempo nao se tem mostrado razoavel tratar cuidadosamente a equacao de Pell, aspectos de Teoria Analıtica, aproximacao por fraccoes contınuas, raızes primitivas, criterios de primalidade ou Teoria Combinatoria. Tais assuntos poderiam ser abordados se a filosofia subjacente a este texto se modificasse; mesmo assim, nem toda a materia aqui descrita tem sido trabalhada durante o semestre nas aulas teoricas ou teorico-praticas.

Utilizamos um mınimo de Algebra, de modo a construir um texto tao independente quanto possıvel.

Os saltos na numeracao das paginas sao um expediente de organizacao tipografica incompleta: podem incluir-se sempre mais paginas alterando muito pouco as referencias de edicao para edicao.

Agradecemos aos Mestres Paulo Almeida e Rui Duarte e a Doutora Ana Foulquie a leitura cuidada das varias versoes preliminares destas notas bem como as sugestoes que apresentaram.

Salvo referencia em contrario, variaveis representadas por letras minusculas designam numeros inteiros.

Aveiro

Maio de 2001 Vıtor Neves

Indice

I Introducao a Teoria dos Numeros 1

1.1 Numeros Naturais3
1.1.1 Axiomatica de Peano3
1.1.2 Soma, ordem e produto4
1.2 Aritmetica7
1.2.1 O maximo divisor comum7
1.2.2 Teorema Fundamental da Aritmetica10
1.3 Exercıcios13

1 Teorema Fundamental da Aritmetica 3

2.1 Propriedades basicas201
2.2 Inversao I203
2.3 Congruencias lineares204
2.3.1 Inversao I205
2.4 A funcao φ de Euler206
2.4.1 Sistemas reduzidos de resıduos206
2.4.2 Teoremas de Euler, de Fermat e de Wilson207
2.5 Congruencias polinomiais210
2.5.1 Introducao210
2.5.2 Modulo primo211
2.5.3 Modulo potencia de base prima213
2.5.4 Teorema Chines do Resto215
2.6 Exercıcios218

2 Congruencias 201

3.1 Introducao301
3.2 Preliminares302
3.3 Lei de Reciprocidade Quadratica303
3.4 Exercıcios308

3 Resıduos quadraticos 301 4 Equacoes Diofantinas 401

4.1 Ternos Pitagoricos401
4.2 Somas de duas quartas potencias406
4.3 Somas de dois quadrados408
4.4 Somas de quatro quadrados412
4.5 Exercıcios414
5.1 Introducao501
5.2 Produto de Dirichlet504
5.3 Funcoes multiplicativas504
5.4 Formula de Inversao de Mobius506
5.5 A funcao de Euler507
5.6 Numeros perfeitos509
5.7 Exercıcios510

5 Funcoes aritmeticas 501

I Numeros reais 601

6.1 Corpos ordenados e numeros racionais603
6.2 Uma visao construtiva608
6.3 Extensoes proprias do corpo dos numeros racionais610
6.4 Corpos ordenados completos612
6.5 Existencia615
6.6 Numeros transcendentes618
6.7 Exercıcios619

6 Fundamentacao 603

7.1 Dızimas701
7.2 Fraccoes contınuas simples705
7.3 Fraccoes periodicas713
7.4 Exercıcios715

7 Dızimas e Fraccoes contınuas 701

8.1 Os numeros complexos801
8.2 Quaternioes803
8.3 Extensoes ordenadas805
8.3.1 (In)Completude805
8.3.2 Parte standard806
8.4 Exercıcios807

8 Extensoes 801 i VN

Int. a Teoria dos Numeros Indıce

I Aplicacoes 901

9.1 Introducao903
9.2 Sistemas afins903
9.3 Codificacao Matricial904
9.4 Criptografia de chave publica905
9.5 Assinaturas; ISBN907
9.6 Exercıcios908

9 Criptografia 903 VN i

Indice ITN (2001) iv VN

Parte I Introducao a Teoria dos Numeros

Teorema Fundamental da Aritmetica

Se bem que se suponham conhecidas as propriedades algebricas elementares dos conjuntos de numeros naturais, inteiros, racionais, reais e complexos, vamos enunciar propriedades basicas dos numeros naturais que serao demonstradas e utilizadas mais tarde numa construcao de outros conjuntos de numeros.

1.1.1 Axiomatica de Peano

Uma estrutura de numeros naturais e um terno N =≺ N,S,1 satisfazendo as seguintes condicoes:

N1) N e um conjunto nao vazio

N2) S e uma funcao injectiva de N em N.

N4) Princıpio de Inducao. Se 1 ∈ A ⊆ N e S(n) ∈ A sempre que n ∈ A, entao A = N.

Um elemento S(n) designa-se por sucessor de n, a condicao N3 estabelece que 1 nao e sucessor e, de acordo com a condicao N2, dois elementos de N sao iguais sse tem o mesmo sucessor.

Teorema Fundamental ITN (2001) Explorando as propriedades das estruturas de numeros naturais:

Por outras palavras: 1 e o unico elemento de N que nao e sucessor.

Pode tambem demonstrar-se que Teorema 1.1.2 Todas as estruturas de numeros naturais sao isomorfas

definem uma funcao1 I : N1 → N2. O Princıpio de Inducao, o teorema 1.1.1 e o facto de as funcoes sucessor serem injectivas garantem que I e um isomorfismo entre as estruturas. 2

Em face deste teorema, passaremos a designar os elementos de N por numeros naturais. No entanto, ainda antes de nos fixarmos nos numeros naturais intuitivos, verificaremos que a axiomatica N1, N2, N3 e suficiente para definir a Aritmetica e ordenar adequadamente a estrutura.

1.1.2 Soma, ordem e produto Seja N =≺ N,S,1 uma estrutura de numeros naturais.

Definicao 1.1.1 A soma de dois numeros naturais m e n designa-se por m + n e

1Veja-se o Teorema de Recursao em [8, p 39 e seg.] 2Idem nota 1

4 VN

Int. a Teoria dos Numeros (2001) Teorema Fundamental Tem-se entao

Teorema 1.1.3 Para quaisquer m,n ∈ N a soma m + n esta definida e ≺ N,+ e um semigrupo comutativo que verifica a Lei do Corte, isto e, a condicao seguinte ∀m,n,p ∈ N m+p = n+p ⇒ m = n. (1.2)

Dem. Esquematizamos apenas uma demonstracao da Lei do Corte. Defina-se para cada m,n ∈ N

Tem-se 1 ∈ Amn pela definicao de soma e pelo axioma N2. Se p ∈ Amn tem-se respectivamente por (1.1), por S ser injectiva (N2) e porque p ∈ Amn. Mas entao 1 ∈ Amn & p ∈ Amn ⇒ S(p) ∈ Amn (p ∈ N) Pelo Princıpio de Inducao Amn = N. 2

Ha uma forma frequentemente mais conveniente de enunciar o Princıpio de Inducao, a saber:

A ordenacao de N pode fazer-se a custa da soma. O numero natural m diz-se menor que o numero natural n — escrevendo-se m < n — se existir p ∈ N tal que n = m + p.

3. A relacao < e de ordem total estrita em N, ou seja, e transitiva e para quaisquer m,n ∈ N, da-se uma e so uma das seguintes condicoes m = n ou m < n ou n < m.

4. Todo o subconjunto nao vazio de N tem mınimo para <.

Em virtude das partes 3 e 4 deste teorema diz-se que N e bem ordenado por <. A relacao de ordem permite um novo enunciado do Princıpio de Inducao.

Teorema 1.1.6 Princıpio de Inducao Completa Se A e um subconjunto de N tal que, seja qual for n ∈ N, n ∈ A sempre que {k ∈ N : k < n} ⊆ A, entao A = N.

VN 5

Teorema Fundamental ITN (2001)

Este enunciado e de facto equivalente ao axioma N4 e ao teorema 1.1.4 em estruturas de numeros naturais, mas nao em conjuntos bem ordenados quaisquer. E passamos a definicao do produto.

Definicao 1.1.2 O produto dos numeros naturais m e n, nota-se m · n e define-se

Como habitualmente, a notacao simplifica-se pondo m·n = mn (m,n ∈ N). Nestes termos vem

Teorema 1.1.7 Para quaisquer m,n ∈ N o produto mn esta bem definido e ≺ N,· e um semigrupo comutativo com elemento neutro 1 que verifica a Lei do Corte, isto e, a condicao seguinte

Retomando o teorema 1.1.2, pode acrescentar-se que

Teorema 1.1.8 A aplicacao I do teorema 1.1.2 respeita a soma, o produto e a ordem, isto e, se +i,·i,<i designam respectivamente a soma, o produto e a ordem sobre Ni (i = 1,2), entao, para quaiquer m,n ∈ N1,

naturais intuitivos 1,2,3,com a respectiva soma +, ordem < e produto × usuais,

Este teorema da-nos mais uma razao para nos limitarmos a estudar como estrutura de numeros naturais o terno ≺ N,S,1 , onde N designa o conjunto dos numeros sendo S(n) = n + 1.

Os teoremas de extensao de semigrupos (ordenados) que verificam a lei do corte por grupos (ordenados) e de domınios de integridade (ordenados) por corpos (ordenados) permitem varias construcoes de aneis de Numeros Inteiros e de corpos de Numeros Racionais a partir das estruturas de Numeros Naturais. Algumas destas construcoes, bem como o estudo do corpo dos Numeros Reais e suas extensoes, serao tratadas mais tarde (parte I).

Terminamos esta seccao com uma das propriedades mais importantes de N. Recordese que ≤ designa a relacao de ordem lata associada a <, i.e., a ≤ b se e so se a < b ou a = b.

3Idem nota 1

6 VN

Int. a Teoria dos Numeros (2001) Teorema Fundamental

Teorema 1.1.9 Propriedade Arquimediana Para quaisquer a,b ∈ N, existe x ∈ N tal que a < xb.

Dem. Tome-se a ∈ N. Seja

1.2.1 O maximo divisor comum

Teorema 1.2.1 (Algoritmo de Euclides) Para quaisquer a e b, se a > 0 existem numeros inteiros unicos d e r tais que

Dem.

o que e impossıvel. Portanto d = d′ e tambem r = r′.

Existencia Se 0 ≤ b < a tem-se b = 0a + b e pode fazer-se d = 0 & r = b. Se a < b, pelo teorema 1.1.9, existe x ∈ N tal que b < xa. Tome-se

Um corolario de facil demonstracao:

VN 7

Teorema Fundamental ITN (2001)

Dem. Aplique-se o teorema anterior 1.2.1 a |b| e |a| e ajuste-se adequadamente. 2

Os numeros d e r das proposicoes anteriores designam-se respectivamente por cociente e resto da divisao de b por a.

Definicao 1.2.1 Dado a 6= 0, b e divisıvel por a (ou a divide b ou a e divisor de b ou b e multiplo de a) se o resto da divisao de b por a e zero. Nota-se a | b se a divide b.

Repare-se que zero e divisıvel por qualquer numero inteiro, no sentido em que para qualquer a ∈ Z, existe d ∈ Z tal que 0 = da, nomeadamente d = 0; nao se define o cociente de zero por zero

Dem. Demonstramos apenas a equivalencia 1.6, no caso em que a 6= 0 6= b.

Mais algumas propriedades importantes, cuja demonstracao fica ao cuidado do leitor.

A alınea 1. do teorema anterior e de facto equivalente a qualquer das alıneas do corolario seguinte.

8 VN

Int. a Teoria dos Numeros (2001) Teorema Fundamental

Definicao 1.2.2 O numero inteiro d e maximo divisor comum de a e b e designa-se por mdc(a,b), se satisfaz simultaneamente as seguintes condicoes:

Se mdc(a,b) = 1 diz-se que a e b sao primos entre si.

pelo que o maximo divisor comum de dois numeros inteiros nao simultaneamente nulos existe e e unico.

O que, em particular, tem como consequencia

Corolario 1.2.3 Se d = mdc(a,b), entao existem x,y ∈ Z tais que d = ax + by.

Dem. (Teorema 1.2.3) Seja

Vamos ver que d | a. Ponha-se a = qd + r, de acordo com o teorema 1.2.1, sendo 0 ≤ r < d; repare-se que, portanto, se r > 0, r teria de ser maior ou igual ao mınimo de S, o que nao e o caso. A troca de a por b neste racicınio, permitiria concluir que d | b e a condicao 2 da definicao tambem esta verificada.

Quanto a unicidade: utilize-se o que acabamos de ver e a condicao 1.6 para concluir que se d′ verifica as mesmas condicoes que d, entao d = d′. 2

Algumas propriedades do maximo divisor comum. Teorema 1.2.4 Para quaisquer a,b ∈ Z

VN 9

Teorema Fundamental ITN (2001)

Alınea 2. Observe-se que d = ax+by, para certos x,y e divida-se por d em, ambos os membros.

Alınea 3. Como mdc(a,b) = 1, para certos x,y, 1 = ax+by de onde se segue que c = acx + bcy. Como a | bc, para certo q vem c = acx + aqy = a(cx + qy) e a | c. Alınea 4. Esquematicamente:

1.2.2 Teorema Fundamental da Aritmetica

Definicao 1.2.3 Um numero inteiro p diz-se primo se verificar simultaneamente as duas condicoes

A propriedade mais importante dos numeros primos e talvez a seguinte:

Lema 1.2.1 (de Euclides) Se p e numero primo e p | ab, entao p | a ou p | b.

Dem. Se p | ab, entao, pelo teorema 1.2.4, p mdc(p,a) | b; ora se p 6 |a, como p e primo

10 VN

Int. a Teoria dos Numeros (2001) Teorema Fundamental

Lema 1.2.2 Se n > 1 e p = min{x > 1| x | n}, entao p e primo. Em particular, qualquer numero natural maior que 1 tem divisores primos.

Dem. Ou bem que n e primo e, nesse caso p = n, ou bem que nao; neste caso n tem divisores maiores que 1 e distintos de si proprio, o mınimo dos quais e p; ora p nao pode ter divisores distintos de si proprio e de 1, pois qualquer deles seria um divisor de n, maior que 1 e menor que p, que nao existe por definicao de p; logo p e primo. 2

E passamos a demonstrar o

Teorema 1.2.5 (Fundamental da Aritmetica)

Esta representacao de n e unica a menos de uma permutacao dos factores.

Dem. Tome-se um numero natural n.

Dem. Seja n > 1. Do lema anterior concluimos que n tem divisores primos.

Defina-se uma sequencia de numeros primos da seguinte forma

} se existir (1.10)

Repare-se que pi+1 so nao existe se n∏i j=1 pj pretende verificar que acontece.

Por outro lado, ∏m j=1 pj | n desde que existam os pj definidos como acima (proposicao

1.2.1) e, de facto, ∏m j=1 pj ≤ n.

Observe-se ainda que, sendo os numeros primos maiores ou iguais a 2, vem

Como 2m > n, para m suficientemente grande, concluimos que os numeros primos pi sao em numero finito, em particular, para certo i, pi existe, mas pi+1 nao. Como

Nao e difıcil mostrar que pj ≤ pj+1 (1 ≤ j < i), pelo que associando da esquerda para a direita primos iguais, se obtem

pαi i

VN 1

Teorema Fundamental ITN (2001) com bases pi em ordem crescente. Resta ver que todos os divisores primos de n foram encontrados. Suponha-se que p e primo e p | n. Pelo lema 1.2.1, p tera de dividir um dos pi, sendo portanto um deles. 2

Ha muitos numeros primos. Corolario 1.2.4 (de Euclides) O conjunto dos numeros primos e infinito.

Dem. Vamos ver que, seja qual for o conjunto de numeros primos {p1,· ,pk} existe um numero primo que lhe nao pertence.

Dados primos p1,· ,pk, seja n = p1 ·pk + 1. De acordo com o Teorema Fundamental, n tera pelo menos um divisor primo. Ora como nenhum dos pi divide n, pois pi | p1 ···pk mas pi 6 |1, esse primo nao pode ser um deles. 2

Os numeros primos estao esparsamente distribuidos

Corolario 1.2.5 Os intervalos entre numeros primos consecutivos sao arbitrariamente grandes.

Onde parar na deteccao dos divisores primos de um dado inteiro?

Teorema 1.2.6 Todo o numero composto n > 0 tem um divisor primo menor ou iguala √ n.

Dem. Se n e composto tem pelo menos dois divisores primos, possivelmente iguais, caso contrario seria primo pelo Teorema Fundamental; se p1,p2 sao primos que dividem

Um resultado semelhante e o corolario seguinte do lema de Euclides (1.2.1) e do teorema 1.2.2

Teorema 1.2.7 (de Gauss) O produto de dois numeros naturais menores que um numero primo nao e divisıvel por este ultimo.

12 VN

Int. a Teoria dos Numeros (2001) Teorema Fundamental

Quanto a distribuicao dos numeros primos, o seguinte teorema e um dos mais importantes de Dirichlet; a sua demonstracao e muito difıcil e esta fora do ambito do presente texto; o leitor interessado pode encontrar uma demonstracao por exemplo em [3], onde todo o capıtulo 7 lhe e dedicado.

Teorema 1.2.8 (de Dirichlet) Se a e b sao numeros naturais primos entre si, a progressao aritmetica (na + b)n∈N tem uma infinidade de termos que sao numeros primos.

Tendo-se observado que um numero primo ımpar e de uma das formas 4k + 1 ou 4k − 1 (k ∈ Z), uma ligeira adaptacao da demonstracao do corolario 1.2.4 permite no entanto demonstrar facilmente o seguinte:

Dem. Consideremos um conjunto finito de numeros primos distintos da forma 4k −1, digamos C := {p1,· ,pn} e defina-se

Em primeiro lugar observe-se que N e da forma 4k − 1 e maior que qualquer dos elementos de C, portanto se for primo nao esta em C, i.e., C nao contem todos os numeros primos da forma em estudo; se N for composto e p for um seu divisor primo, entao p tambem nao pode ser qualquer dos elementos de C; deixa-se como exercıcio mostrar que algum divisor primo de N e da forma 4k−1 e, como acabamos de ver, nao esta em C. Em suma: C nao contem todos os numeros primos da forma 4k − 1. 2

Nao e tao simples demonstrar que o teorema anterior vale com 4k + 1 em vez de 4k − 1; fa-lo-emos mais tarde (vide corolario 2.4.3).

1. Demonstre que a adicao e a multiplicacao em N sao associativas, sao comutativas e verificam a Lei do Corte.

2. Mostre que se f : N → N e estritamente crescente, entao para qualquer n ∈ N, n ≤ f(n).

3. Demonstre o seguinte teorema.

(Parte 1 de 3)

Comentários