Teoria dos Numeros

Teoria dos Numeros

(Parte 1 de 2)

Texto de aula Professor Rudolf R. Maier

Versao atualizada 2005

Estas notas sao o resultado da experiencia nas aulas do curso do mesmo tıtulo, proferido regularmente pelo autor neste Departamento de Matematica.

Durante o curso e na elaboracao destas notas fizemos livre uso e seguimos com modificacoes e complementacoes a linha do livro de David M. Burton

Revised Printing

University of New Hampshire

Allyn and Bacon, Inc.

§ 1 Resultados Preliminares1

Indice

O princıpio da inducao O teorema binomial

As formulas para Sn(m) = n∑ k=1 km

Os numeros triangulares Algumas observacoes sobre logica elementar Diferenca de dois quadrados

§ 2 Teoria de divisibilidade nos numeros inteiros21

O algoritmo geral de divisao Maximo divisor comum de dois numeros Numeros relativamente primos O algorıtmo Euclidiano O mınimo multiplo comum Equacoes Diofantinas

§ 3 Numeros primos e sua distribuicao34

O teorema fundamental da aritmetica A quantidade dos divisores de um numero n A decomposicao primaria de n! Estimativas sobre quantidades de primos A funcao pi dos numeros primos Decomposicao de numeros e o crivo do Eratostenes A conjetura de Goldbach Progressoes aritmeticas e primos Polinomios e primos

§ 4 Triplos Pitagoricos e a conjetura de Fermat53

Triplos Pitagoricos A conjetura de Fermat

e de Mersenne61

§ 5 Numeros deficientes-abundantes-perfeitos

Numeros deficientes, abundantes e perfeitos O teorema de Euclides/Euler Numeros de Mersenne

§ 6 A teoria das congruencias69

Divisibilidade e congruencias Congruencias lineares Congruencias simultaneas e o teorema do resto chines

§ 7 Os Teoremas de Fermat e de Wilson78

O pequeno teorema de Fermat O teorema de Wilson

reciprocidade quadratica de Euler/Gauss85

§ 8 Congruencias quadraticas e a lei da

Restos quadraticos Um Lema de Euler O sımbolo de Legendre Um Lema de Gauss

O sımbolo de Legendre ( 2

A lei da reciprocidade quadratica Mais alguns sımbolos de Legendre especiais

soma de quadrados105

§ 9 Representacao de inteiros como

Soma de dois quadrados Soma de tres quadrados Soma de quatro quadrados (o teorema de Lagrange)

§ 10 A funcao ϕ de Euler114

Restos relativamente primos e a funcao ϕ O teorema de Euler Mais algumas propriedades da funcao ϕ

§ 1 Raızes primitivas123

Ordens modulo n e raızes primitivas Existencia de raızes primitivas.

TEORIA DOS NUMEROS Notas de aula - Versao atualizada 2005 Prof. Rudolf R. Maier

§ 1 Resultados Preliminares

A Teoria dos Numeros, a mais pura disciplina dentro da mais pura das Ciencias - da Matematica - tem uma longa historia, originando-se nas antigas civilizacoes da humanidade. Listamos primeiro alguns nomes famosos de matematicos que voltarao a aparecer no contexto do nosso curso:

Dedicaremos os nossos estudos durante este curso as propriedades dos numeros inteiros racionais. Lidaremos entao com o conjunto

, −3, −2, −1, 0, 1, 2, 3 , . . .

dos numeros inteiros e seus subconjuntos, particularmente com os subconjuntos

0, 1, 2, 3 ,}
1, 2, 3 ,

dos numeros inteiros nao-negativos e dos numeros naturais.

Iniciamos, lembrando exemplos de algumas sequencias importantes no conjunto IN dos numeros naturais:

1.1 Exemplo. Sequencias importantes em IN sao: A sequencia

= (1, 2, 3 ,, n ,...) de todos os numeros naturais,
= (2, 4, 6 ,, 2n ,...) dos numeros naturais pares,
= (1, 3, 5 ,, 2n−1 ,...) dos numeros ımpares,d) (

n∈IN

1, 4, 9 ,, n2 , . . .)

=( dos quadrados perfeitos, n∈IN

1, 8, 27 ,, n3 , . . .)

=( dos cubos perfeitos,

= (2, 4, 8 ,, 2n , . . .) das potencias de 2
= (2, 3, 5 ,, pn ,...) dos numeros primos,

h) etc.

Temos duas operacoes internas em IN0 e tambem em Z a adicao + e a multi- plicacao · as quais queremos admitir sem mais explicacoes. A ordem natural em Z e dada por: ∀ n,m ∈ Z temos

Uma fundamantal propriedade do conjunto IN dos numeros naturais e:

O princıpio da inducao.

Todo conjunto nao vazio S de numeros naturais possui um elemento mınimo. Em sımbolos:

Deste princıpio segue a importante 1.2 Proposicao.

Seja T um conjunto de numeros naturais (i.e. T ⊆ IN) satisfazendo as propriedades:

b) Sempre se n ∈ T , entao tambem n+1 ∈ T. Entao T = IN e o conjunto de todos os numeros naturais.

Demonstracao: Suponhamos T 6= IN. Para o conjunto complementar S = IN \ T temos entao 6O 6= S ⊆ IN. Pelo princıpio da inducao 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 porem m = n+1 ∈ T, de onde sai o absurdo m ∈ S ∩ T = 6O. Isto mostra que S 6= 6O e impossıvel. Temos que ter S = 6O e daı T = IN.

Proposicao 1.2 aplica-se para verificar a validade geral de formulas as quais envolvem numeros naturais, como mostra o seguinte

1.3 Exemplo. Para todos os numeros naturais n vale

1 + 3 + 5 ++ (2n−3) + (2n−1) = n2 (∗) .

Em palavras: A soma dos n primeiros numeros naturais ımpares e o n-esimo quadrado perfeito.

naturais para os quais a formula (∗) e verdadeira (o ”conjunto verdade” ou o ”conjunto de validade” de (∗)). Para mostrar que T = IN , so e preciso verificar a) e b) da Proposicao 1.2 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 numero natural n, isto e,

1 + 3 ++ (2n−1) = n2 .
1 + 3 ++ (2n−1) + (2n+1) = n2+2n+1 ,
1 + 3 ++ (2n−1) + (

Isto por sua vez significa n+1 ∈ T. Pela proposicao concluimos que o conjunto verdade da formula (∗) e o conjunto T = IN de todos os numeros naturais.

1.4 Exemplo. Para todos os numeros naturais n e todo real a 6= 1 vale

1 + a + a2 + a3 ++ an−1 + an =
1 + 2 + 4 ++ 2n−1 + 2n = 2n+1 − 1 .

Particularmente (quando a = 2) obtemos

Demonstracao: Mais uma vez temos que verificar a assercao para n = 1 e para n+1 sob a hipotese que ela ja e valida para algum n:

Suponhamos, para algum numero natural n ja esteja provado

1 + a + a2 + a3 ++ an−1 + an =
1 + a + a2 ++ an−1 + an + an+1 =

Somando-se an+1 a ambos os lados, obtemos an+1 − 1

1 + a + a2 ++ an + an+1 =

Isto diz que a formula continua valida para n+1. Concluimos que ela vale para todo n ∈ IN.

Mencionamos que, as vezes e conveniente trabalhar com a seguinte generalizacao de 1.2:

Seja n0 ∈ Z um inteiro fixo e seja T ′ um conjunto de (alguns) numeros in-

propriedades:

≤ n ∈ Z} e o conjunto de todos os numeros inteiros maiores ou iguais a n0 .

Isto e facilmente verificado pela aplicacao de 1.2 ao conjunto

Observamos que para este T temos T ⊆ IN e n0 ∈ T ′ e equivalente a 1 ∈ T.

(1.2 e obtido de volta a partir de 1.2’ fazendo-se n0 = 1).

A tıtulo de ilustracao mencionamos o seguinte exemplo. A afirmacao (correta) que o leitor queira verificar:

2n > n2 para todos os n ≥ 5 podemos substituir pela afirmacao equivalente 2n+4 > (n + 4)2 para todos os n ∈ IN

O teorema binomial

Se n ∈ IN0 entendemos por n! o produto

k = 1 · 2 · 3 ·· n , se n ∈ IN
24,,n! = (n−1)! · n, (n+1)! = n! · (n+1) ,... .

1.5 Definicao. Para todo n ∈ IN e todos os k ∈ IN0 com 0 ≤ k ≤ n colocamos

numero este que se chama o coeficiente binomial n sobre k.

Temos as seguintes propriedades dos coeficientes binomiais:

Para todo n ∈ IN e todos os k ∈ IN0

n(n−1) ·· (n−k+1)

b) Observamos primeiro que com 0 ≤ k ≤ n temos tambem 0 ≤ n−k ≤ n. Pela definicao temos de imediato( n n−k) =

c) Se k ≥ 1 calculamos

Eis alguns valores especıficos de coeficientes binomiais:

Podemos enunciar e provar agora o fundamental teorema do desenvolvimento binomial:

1.7 Teorema. Para todo n ∈ IN e todos os numeros reais a, b temos

por extenso:

Demonstracao: Demonstraremos isto por inducao sobre o expoente n, isto e, provaremos 1 ∈ T e a implicacao ”n ∈ T ⇒ n+1 ∈ T ”, quando T e o conjunto de validade da formula.

igual a a + b de ambos os lados, i.e. 1 ∈ T. Suponhamos entao que, para algum n ∈ IN, ja esteja provado

e provamos a validade para n+1. Para isto multiplicamos os dois lados de (∗) por (a + b) e obtemos, usando-se a observacao 1.6 c):

Isto significa que, a partir da suposta validade da formula (∗) para algum n, conseguimos provar a sua validade para n+1 (i.e. n ∈ T ⇒ n+1 ∈ T). Concluimos que (∗) tem validade para todo n ∈ IN.

ordenados no chamado Triangulo de Pascal, cuja n-esima linha fornece entao os coeficientes no desenvolvimento de (a + b)n para n = 0, 1, 2, 3 ,...

(

Vemos ainda a visualizacao da formula 1.6 c), a qual diz como o termo (n+1k ) da

(n+1)-esima linha no triangulo de Pascal e obtido como soma dos termos vizinhos( n

da linha anterior.

Disto conclui-se facilmente por inducao sobre n a

1.8 Consequencia. Os coeficientes binomiais sao numeros inteiros.

As formulas para Sn(m) = n∑ k=1 km

1.9 Definicao. Para todo n ∈ IN e todo m ∈ IN0 colocamos

km =1m + 2m + 3m ++ nm ,

isto e, Sn(m) e a soma das n primeiras m-esimas potencias.

Sn(0) = 10 + 20 + 30 ++ n0 = n,
Sn(1) = 1 + 21 + 31 ++ n1 = 1 + 2 + 3 + ... + n

Por exemplo, e a soma dos primeiros n numeros naturais,

Sn(2) = 12 + 2 + 32 ++ n2 = 1 + 4 + 9 + ... + n2

e a soma dos primeiros n quadrados perfeitos,

Sn(3) = 13 + 23 + 3 ++ n3 = 1 + 8 + 27 + ... + n3

e a soma dos primeiros n cubos perfeitos, etc.

Como podemos obter formulas fechadas para Sn(m)?

teriores Sn(0)=n, Sn(1), Sn(2) ,, Sn(m−1):

A seguinte formula recursiva permite calcular Sn(m) a partir das formulas an- 9

1.10 Teorema. Para todos os n, m ∈ IN vale

Sn(k) −− (m+1

Demonstracao: Desenvolvemos primeiro a expressao (1+x)m+1 pelo teorema binomial:

por extenso,

Colocando-se x = 1, 2 ,, , . . . , n, obtemos
12 ++
1k ++
2 ++
2k ++
2 ++
k ++
n2 ++
nk ++
numeros 2m+1 ,, nm+1 e observando-se a definicao de Sn(k), obtemos

Somando-se estas n equacoes verticalmente, cancelando-se de ambos os lados os

Lembrando ainda n = Sn(0), isto da a nossa formula afirmada

Vejamos os primeiros casos desta formula.

o que da para a soma dos n primeiros quadrados perfeitos:

o que da para a soma dos n primeiros cubos perfeitos:

ainda a relacao interessante

(1 + 2 + 3 ++ n)2 = 13 + 23 + 3 + ... + n3 ,

valida para todos os n ∈ IN.

Uma formula fechada para Sn(m) sem uso das anteriores podemos estabelecer em forma de um (m+1) × (m+1)-determinante:

Para todo n ∈ IN e m ∈ IN0 temos

0 00 0 (n+1)1−1(20
00 0 (n+1)2−1(30
0 0 (n+1)3−1
(

Demonstracao: Nossa formula de recursao

podemos reescrever, substituindo-se m = , como

Explicitando-se esta para = 0,1,2 ,, m, obtemos um sistema de m + 1
equacoes lineares nas m + 1 incognitas Sn(0), Sn(1), Sn(2) ,, Sn(m):
(
Sn(1) ++
Sn(1) ++

O determinante dos coeficientes deste sistema (o produto dos coeficientes da diagonal neste caso) e

A aplicacao da regra de Cramer fornece para a incognita Sn(m), como afirmado:

0 00 0 (n+1)1−1(20
00 0 (n+1)2−1(30
0 0 (n+1)3−1
(

Os numeros triangulares 1.12 Definicao. Para todo m ∈ IN indicamos por

tm chama-se o m-esimo numero triangular. Desta definicao decorre imediatamente:

1.13 Observacao. Para todo m ∈ IN temos

tal como

1, 3, 6, 10 ,,
,)

A denominacao ”numero triangular” para os numeros desta sequencia explica-se pelo seguinte triangulo equilatero de lados m o qual contem exatamente tm pontos:

A seguinte caracterizacao dos numeros triangulares entre os numeros naturais e um resultado classico devido a Plutarco (ca. 100 d. C.)

1.14 Proposicao. Para todo numero natural n temos: n e um numero triangular, se e somente se, 8n + 1 e um quadrado perfeito.

Demonstracao: Nesta proposicao duas coisas estao sendo afirmadas e tem que ser provadas: 1) Sempre quando n e um numero triangular, 8n + 1 sera um quadrado perfeito. 2) Sempre quando 8n+1 e um quadrado perfeito, n sera um numero triangular.

Seja primeiro n um numero triangular, i.e. n = tm para algum m ∈ IN. Segue que

e um quadrado perfeito.

Seja agora n ∈ IN tal que 8n + 1 = k2 e um quadrado perfeito. Como k e ımpar

mostrando que n e um numero triangular (mais exatamente: n e o k−12 -esimo termo na sequencia dos numeros triangulares).

Algumas observacoes sobre logica elementar

Suponhamos, A e B sao ”assercoes” (ou ”propriedades”) - as quais podem ser verdadeiras ou falsas e cuja veracidade ou falsidade pode ser constatada de forma unica. Quando escrevemos A =⇒ B queremos dizer que

A implica em B, ou seja, sempre quando A for verdadeira, tambem B sera verdadeira. Outra maneira de dizer isto e:

(A validade de) A e condicao suficiente para (a validade de) B, ou B e condicao necessaria para A, ou A vale somente se B vale, ou B vale se A vale, ou ainda Se A, entao B.

E claro que

B ⇐= A significa o mesmo quanto A =⇒ B.

Vejamos exemplos. Seja A a assercao: ”um certo numero natural n e multiplo de 4” (isto pode ser verdadeiro ou falso), B a assercao: ”n e par”.

Claramente temos neste caso A =⇒ B, pois sempre se n e multiplo de 4, concluimos que n e par. Assim, podemos dizer: ”n ser multiplo de 4 implica que n e par”,

”n ser multiplo de 4 e condicao suficiente para n ser par”,

”n ser par e condicao necessaria para n ser multiplo de 4”

Um outro exemplo. Seja A a assercao: ”esta chovendo”, (tambem isto pode ser verdadeiro ou falso aqui e agora), B a assercao: ”a praca esta molhada”.

Tambem neste caso temos A =⇒ B, pois, se realmente esta chovendo, temos certeza que a praca esta molhada. Assim, podemos dizer:

”estar chovendo implica que a praca esta molhada”,

”estar chovendo e condicao suficiente para termos uma praca molhada”, ”uma praca molhada e condicao necessaria para estar chovendo”,

”esta chovendo somente se a praca esta molhada”,

”a praca esta molhada se esta chovendo”,

”se esta chovendo, entao a praca esta molhada”.

Exercıcio:

Pensando-se num certo quadrangulo Q, facam o mesmo com as assercoes

E claro que a seta numa implicacao A =⇒ B nao pode ser simplesmente invertida: Se A e condicao suficiente para B, isto significa que B e condicao necessaria para A, mas nao que B e condicao suficiente para A:

O fato de ”n ser par”e condicao necessaria mas nao suficiente para ”n ser multiplo de 4”. O fato de ”n ser multiplo de 4” e condicao suficiente mas nao necessaria para ”n ser par”: Tambem 6 e par sem ser multiplo de 4.

O fato de termos ”uma praca molhada” e condicao necessaria mas nao suficiente para ”estar chovendo”. O fato de ”estar chovendo ”e condicao suficiente mas nao necessaria para termos ”uma praca molhada”: A praca pode estar molhada sem que esteja chovendo (por exemplo devido a uma operacao dos bombeiros). Existem assercoes A e B que ambas implicam na outra, ou seja, as quais satisfazem simultaneamente

Nesta situacao temos entao que A e suficiente para B e tambem A e necessario para B. Dizemos que A e (condicao) necessario(a) e suficiente para B, ou tambem A vale se e somente se vale B.

Este fato indicamos por

Dizemos tambem que A e B sao assercoes equivalentes, ou ainda que A constitui uma propriedade caracterıstica para B (e vice versa).

Cada uma destas duas propriedades, as quais um numero n pode ter ou nao, e suficiente para a outra. Cada uma e necessaria para a outra. Cada uma e necessaria e suficiente para a outra. Cada uma vale se e somente se a outra vale.

Pensar sobre as assercoes equivalentes, quando Q e um certo quadrangulo:

Se A e uma assercao, indicamos por A a assercao ”nao-A”, a qual e verdadeira se e somente se A e falsa. Sejam A e B duas assercoes e suponha

O que acontece com esta implicacao se negarmos as duas assercoes ? A resposta e que devemos tambem inverter a seta da implicacao, ou seja, teremos

Em outras palavras: Se A e suficiente para B, entao B e suficiente para A.

Ou tambem: Se A e suficiente para B, entao A e necessario para B. Por exemplo, se negarmos a implicacao

”ser multiplo de 4 e suficiente para ser par ”, (”ser um quadrado e suficiente para ser um retangulo”), a implicacao negada e:

”nao ser multiplo de 4 e necessario para ser ımpar”, (”nao ser um quadrado e necessario para nao ser retangulo”) mas, nao ser multiplo de 4 (nao ser quadrado) nao e suficiente para ser ımpar (nao ser retangulo).

Claro que numa equivalencia podemos negar as assercoes dos dois lados, ou seja, nao importa se escrevemos

Na Proposicao 1.14 ja conhecemos mais um exemplo de duas propriedades equivalentes, a saber, uma caracterizacao de um numero natural n ser triangular: Necessario e suficiente para n ser triangular e a propriedade de 8n+1 ser um quadrado perfeito.

Existem teoremas que afirmam simplesmente implicacoes, de modo que na sua demonstracao deve ser verificado que uma certa propriedade B e consequencia de uma propriedade A (a hipotese). outros teoremas matematicos afirmam equivalencias de certas propriedades. Eles tem a forma:

Sob certas condicoes sao equivalentes:

a) Vale a propriedade A b) Vale a propriedade B.

”a) ⇒ b)”:Aqui deve ser mostrado que A e suficiente para B.

A demonstracao de um tal teorema sempre se divide em duas partes: Isto pode ser mostrado diretamente, mostrando-se que B e verdade, supondo-se a veracidade de A. Ou indiretamente, supondo-se a veracidade de B e concluindose que A e verdade.

”b) ⇒ a)”:Aqui deve ser mostrado que A e necessario para B (que B e

suficiente para A). Isto pode ser mostrado, verificando-se que A e verdade, supondo-se a veracidade de B. Ou indiretamente, supondo-se que A e falso e concluindo-se que B e falso.

1.15 Observacao. Se n ∈ IN e um quadrado perfeito, entao valem:

a) Se n for par, entao n e divisıvel por 4.

o resto 1 quando dividido por 8.

Convem frisar que, as afirmacoes de 1.15 nao sao equivalencias. Trata-se de duas implicacoes: A condicao de um numero n ser quadrado perfeito par (ımpar) e suficiente para n ser divisıvel por 4 (ser da forma 8k + 1). Estas propriedades porem nao sao necessarias: n = 12 (n = 17) e divisıvel por 4 (e da forma 8k + 1) sem que n seja quadrado perfeito.

(Parte 1 de 2)

Comentários