Algebra fund. web

Algebra fund. web

(Parte 1 de 3)

Notas de Aulas Introducao a Algebra

Profa Maria Julieta Ventura Carvalho de Araujo Prof. Frederico Sercio Feitosa (colaborador) i i

Introducao a Algebra (MAT128) Introducao a Teoria dos Numeros (MAT143)

1. Ementa

(a) Os Princıpios de Inducao Matematica e da Boa Ordenacao (b) Divisibilidade (c) Numeros Primos e o Teorema Fundamental da Aritmetica (d) Equacoes Diofantinas Lineares (e) Congruencias (f) Sistema de Congruencias Lineares (g) Criptografia Basica (MAT128)

2. Bibliografia

(a) Fernandes, A. M. V. et al. Fundamentos de Algebra. Belo Horizonte: UFMG, 2005.

(b) Coutinho, S. C. Numeros Inteiros e Criptografia RSA. Serie de Computacao e Matematica. Rio de Janeiro: IMPA, 1997.

(c) Hefez, A. Curso de Algebra. Vol. 1. Colecao Matematica Universitaria. Rio de Janeiro: IMPA, 1993.

(d) Elementos de Aritmetica. Colecao Textos Universitarios. Rio de Janeiro: SBM, 2005. (e) Alencar Filho, E. Teoria Elementar dos Numeros. Sao Paulo: Nobel, 1985. (f) Milies, F. C. P. Numeros: Uma Introducao a Matematica. Sao Paulo: EDUSP, 2003.

(g) Rosen, K. H. Elementary Number Theory and its Applications. New York: Addison-Wesley, 1984.

(h) Koblitz, N. A Cource in Number Theory and Cryptography. New York: Springer-Verlag, 1987.

3. Horario de Atendimento

4. Provas

Indice

1.1 Introducao1
1.2 Deducao e Inducao1
1.3 Princıpio de Inducao Matematica - PIM - 1a forma2
1.4 Princıpio de Inducao Matematica - PIM - 2a forma5
1.5 Princıpio da Boa Ordenacao (PBO)7
1.6 Exercıcios9

1 Os Princıpios de Inducao Matematica e da Boa Ordenacao 1

2.1 Relacao de divisibilidade em Z1
2.2 Conjunto dos divisores de um inteiro13
2.3 Divisores comuns de dois inteiros13
2.3.1 Exercıcios14
2.4 Algoritmo da Divisao14
2.4.1 Exercıcios15
2.5 Representacao de um numero em uma base qualquer16
2.5.1 Exercıcios18
2.6 Alguns criterios de divisibilidade18
2.6.1 Exercıcios19
2.7 Maximo Divisor Comum19
2.7.1 Maximo divisor comum de dois inteiros19
2.7.2 Inteiros primos entre si21
2.7.3 Caracterizacao do maximo divisor comum de dois inteiros2
2.7.4 Maximo divisor comum de varios inteiros23
2.7.5 Exercıcios23
2.7.6 Algoritmo de Euclides (metodo para encontrar o maximo divisor comum)24
2.7.7 Algoritmo euclidiano estendido26
2.8 Mınimo multiplo comum28
2.8.1 Multiplos comuns de dois inteiros28
2.8.2 Mınimo multiplo comum de dois inteiros29
2.8.3 Relacao entre mdc e mmc29
2.8.4 Exercıcios30
3.1 Numeros primos e compostos32
3.2 Crivo de Eratosthenes3
3.3 Teorema Fundamental da Aritmetica36
3.4 A procura de numeros primos37
3.5 Exercıcios37

3 Numeros primos e o Teorema Fundamental da Aritmetica 32 i

INDICE i

4.1 Generalidades39
4.2 Condicao de existencia de solucao39
4.3 Solucoes da equacao diofantina linear ax + by = c40
4.4 Exercıcios41

4 Equacoes Diofantinas Lineares 39

5.1 Inteiros congruentes42
5.2 Caracterizacao de inteiros congruentes43
5.3 Propriedades43
5.4 Sistema completo de restos45
5.5 Exercıcios46
5.6 Classes residuais47
5.6.1 Revisao47
5.6.2 Definicao e propriedades47
5.6.3 O conjunto das classes residuais48
5.6.4 Adicao e Multiplicacao em Zm49
5.6.5 Exercıcios51
5.7 Congruencias lineares51
5.7.1 Definicao e condicao de existencia51
5.7.2 Solucoes da congruencia linear ax ≡ b (mod m)52
5.8 Resolucao de equacoes diofantinas lineares por congruencia53
5.9 Inverso de um inteiro modulo m53
5.10 Teoremas de Fermat e de Wilson54
5.1 Criterios de divisibilidade usando congruencias5
5.12 Exercıcios56
5.13 A funcao ϕ de Euler57
5.14 Exercıcios59
6.1 Introducao60
6.2 Teorema Chines do Resto61
6.3 Representacao Grafica (tabela)62

Capıtulo 1

Os Princıpios de Inducao Matematica e da Boa Ordenacao

1.1 Introducao

Em 1742, o matematico Christian Goldbach afirmou que todo inteiro par maior que 4 pode ser escrito como a soma de dois primos ımpares. Certamente Goldbach intuiu este resultado depois de observar que ele era verdadeiro para alguns numeros, como por exemplo, 6 = 3 + 3, 8 = 3 + 5, 10 = 5 + 5, etc. Ja foi erificada esta afirmativa para todo inteiro par entre 6 e 108, entretanto nao podemos considera-la verdadeira a partir deste fato ja que 108 e um numero insignificante comparado com a ”maior parte”dos inteiros. Muitos matematicos tem procurado demonstrar ou refutar esta conjectura, mas nada foi conseguido ate hoje.

Em uma teoria matematica, muitas vezes, resultados sao enunciados a partir de consideracoes de casos particulares, como por exemplo acima, mas eles so sao tidos como verdadeiros se puderem ser demonstrados, isto e, deduzidos de proposicoes que nao sao demonstradas e nos quais esta fundamentada a teoria.

Trataremos aqui dos numeros naturais, N = {1,2,3,...}, a partir de um dos postulados que os caracterizam, a saber, o Princıpio de Inducao Matematica. Veremos como utiliza-lo na demonstracao de afirmacoes a respeito dos numeros naturais, como por exemplo, o Princıpio da Boa Ordenacao.

1.2 Deducao e Inducao

Consideremos os seguintes exemplos:

(1) Todo mineiro e brasileiro. (2) Paulo e mineiro. (3) Logo, Paulo e brasileiro.

No exemplo 1.1, a afirmacao (1) e geral e com o auxılio da afirmacao particular (2) obtemos a afirmacao particular (3).

No exemplo 1.2, a afirmacao (1) e particular e estamos tentando generaliza-la atraves da afirmacao (2).

CAPITULO 1. OS PRINCIPIOS DE INDUC AO MATEMATICA E DA BOA ORDENAC AO 2

Definicao 1.1 A passagem de uma afirmacao geral para uma particular e chamada DEDUC AO (exemplo 1.1). A tentativa de generalizacao de uma afirmacao particular, isto e, a passagem de uma afirmacao particular para uma geral, e chamada INDUC AO (exemplo 1.2).

Observacao 1.1 Note que a conclusao do exemplo 1.2 e falsa (faca n = 40, por exemplo). Temos entao a seguinte questao que sera resolvida aqui: Como poderıamos usar inducao em matematica de forma a obter somente conclusoes verdadeiras ?

Suponhamos que para cada natural n se tenha uma afirmativa P(n) que satisfaca as seguintes propriedades:

(i) P(1) e verdadeira;

(i) Sempre que a afirmativa e valida para um numero natural arbitrario n = k, ela e valida para seu sucessor n = k + 1 (isto e, P(k) verdadeira implica P(k + 1) verdadeira).

Entao, P(n) e verdadeira para todo natural n > 1.

Observacao 1.2 Uma prova baseada no PIM e chamada uma prova pelo metodo da inducao matematica. Tal prova deve consistir da demonstracao de dois fatos independentes:

Fato 1 a afirmacao e valida para n = 1.

Fato 2 a afirmacao e valida para n = k + 1 se ela e valida para n = k, onde k e um numero natural arbitrario.

Se ambos estes fatos sao provados entao, com base no PIM, a afirmacao e valida para todo numero natural n.

Observacao 1.3 Note que o fato 2 contem uma implicacao, portanto possui uma hipotese (P(k) e verdadeira) e uma tese (P(k + 1) e verdadeira). Provar o fato 2 significa provar que a hipotese acarreta a tese. A hipotese do fato 2 e chamada Hipotese de Inducao (HI).

Exemplo 1.3 Calcular a soma

++

Temos que:

Usando o metodo de inducao matematica tentaremos provar que Sn = n

CAPITULO 1. OS PRINCIPIOS DE INDUC AO MATEMATICA E DA BOA ORDENAC AO 3

Fato 2: Suponhamos que a afirmacao seja verdadeira para n = k, isto e, Sk = 1

+

k +1 e vamos provar que a afirmacao e verdadeira para n = k + 1, ou seja, Sk+1 =

De fato,

++

HI= k

Portanto, com base no PIM, podemos afirmar que Sn = n

Exemplo 1.4 Vimos, pelo exemplo 1.2, como uma atitude negligente para com o fato 2 pode nos levar a resultados falsos. O exemplo seguinte mostra que tao pouco podemos omitir o fato 1.

Seja Sn = 1 + 2 + 3 ++ n e consideremos a conjectura Sn =

Fato 2: Supponhamos a afirmativa valida paraq n = k, isto e, Sk = 1

Assim temos:

Sk+1 = 1 + 2 + 3 ++ k + (k + 1)

Logo, o fato 2 se verifica. Entretanto, e facil ver que esta conjectura nao e verdadeira para todo numero natural n.

Observacao 1.4 O fato 1 cria a base para se fazer a inducao. O fato 2 nos da o direito de passar de um numero natural para o seu sucessor (de k para k + 1), ou seja, o direito de uma extensao ilimitada desta base.

Se o fato 1 nao foi provado mas o fato 2 sim, entao a base para se iniciar a inducao nao foi criada e nao faz sentido aplicar o fato 2, ja que nao existe nada para ser estendido. Se o fato 2 nao foi provado mas o fato 1 sim, entao temos a base para se comecar a inducao, mas nao temos argumentos que nos possibilitem estende-la.

CAPITULO 1. OS PRINCIPIOS DE INDUC AO MATEMATICA E DA BOA ORDENAC AO 4

Observacao 1.5 Se fizermos uma afirmativa incorreta nao conseguiremos demonstra-la pelo metodo de inducao. Por exemplo, examinando a soma

++

para alguns valores de n, obtivemos S1 = 1

,e estes resultados particulares sugeriram

a hipotese de que, para todo natural n > 1, Sn = n n+1 , o que foi provado no exemplo 1.3.

Poderıamos ter feito a seguinte conjectura: Sn = n+1

2 . Suponhamos que ela seja verdadeira para n = k, isto e, Sk =

3k +1 e tentaremos provar que ela

Mas,

o que nao confirma a nossa conjectura.

O fato de se comecar a inducao em n = 1 nao e importante. Podemos re-escrever o PIM da seguinte forma:

Proposicao 1.1 Seja a ∈ N. Suponhamos que para cada natural n > a se tenha uma afirmativa P(n) que satisfaca as seguintes propriedades:

(i) P(a) e verdadeira;

(i) Sempre que a afirmativa e valida para um numero natural arbitrario n = k > a, ela e valida para seu sucessor n = k + 1 (isto e, P(k) verdadeira implica P(k + 1) verdadeira).

Entao, P(n) e verdadeira para todo natural n > a. Prova:

O processo de inducao matematica se baseia no fato de que depois de cada numero natural k existe um sucessor (k + 1) e que cada numero natural n pode ser alcancado mediante um numero finito de passos, a partir do 1. Portanto e, muitas vezes, mais conveniente enuncia-lo do seguinte modo:

CAPITULO 1. OS PRINCIPIOS DE INDUC AO MATEMATICA E DA BOA ORDENAC AO 5

Proposicao 1.2 Se S ⊂ N e um subconjunto tal que:

Entao podemos afirmar que S = N. Prova:

Observacao 1.6 Para mostrar que

++

poderıamos ter considerado o conjunto

++

e entao pelos mesmos argumentos utilizados no exemplo 1.3, concluirıamos que:

Logo, terıamos que S = N, ou seja, a formula

++

Seja a ∈ N. Suponhamos que para cada natural n > a se tenha uma afirmativa P(n) que satisfaca as seguintes propriedades:

(i) P(a) e verdadeira; (i) P(m) verdadeira para todo natural m com a 6 m 6 k implica P(k + 1) verdadeira.

Entao P(n) e verdadeira para todo natural n > a.

CAPITULO 1. OS PRINCIPIOS DE INDUC AO MATEMATICA E DA BOA ORDENAC AO 6

Observacao 1.7 Note que aqui tambem a condicao (i) consiste em uma implicacao. Sua hipotese e tambem chamada de hipotese de inducao (HI). A diferenca entre as duas formas esta exatamente na hipotese de inducao: na primeira supoe-se que P(k) seja verdadeira e na segunda supoe-se que P(k),P(k− 1),P(k − 2),...,P(a) sejam todas verdadeiras.

Observacao 1.8 Esta forma e util nos casos em que a validade de P(k+1) nao puder ser obtida facilmente da validade de P(k) mas sim, da validade de algum P(m), onde a 6 m 6 k.

1, 1, 2, 3, 5, 8, 13, 21,

Exemplo 1.5 Considere a sequencia de Fibonacci onde cada elemento, a partir do terceiro, e a soma dos dois anteriores.

Usando a primeira forma do PIM

, n ∈ {1, 2, 3,}.

que e uma cota maior do que a desejada. Vamos, entao usar a segunda forma do PIM:

Usando a segunda forma do PIM Ja vimos que P(1) e P(2) sao verdadeiras. Seja k 6 2 e suponhamos P(m) verdadeira para todo

CAPITULO 1. OS PRINCIPIOS DE INDUC AO MATEMATICA E DA BOA ORDENAC AO 7

Teorema 1.1 (Segunda forma do PIM) Seja a ∈ N. Suponha que para cada numero natural n se tenha uma afirmativa P(n) que satisfaca as seguintes propriedades:

(i) P(a) e verdadeira;

Entao P(n) e verdadeira para todo natural n > a.

Portanto pela primeira forma do PIM temos que todos naturais n tais que n > a pertencem a S, isto e, S = {n ∈ N : n > a}, donde P(n) e verdadeira para todo n > a.

1.5 Princıpio da Boa Ordenacao (PBO)

“Todo subconjunto nao vazio S ⊂ N possui um nemor elemento, isto e, existe a ∈ S tal que a 6 x, para todo x ∈ S.”

Prova: Vamos usar a segunda forma do PIM.

CAPITULO 1. OS PRINCIPIOS DE INDUC AO MATEMATICA E DA BOA ORDENAC AO 8

Suponhamos que exista um conjunto S ⊂ N que nao possua menor elemento. Vamos mostrar que S = ∅.

Portanto, pela segunda forma do PIM, nenhum elemento de N esta em S. Como S ⊂ N temos que S = ∅. Assim podemos afirmar que se S ⊂ N, S 6= ∅, entao S possui menor elemento.

Observacao 1.9 O Princıpio da Boa Ordenacao tambem e conhecido como Princıpio do Menor Inteiro.

Exemplo 1.8 Considere o conjunto dos numeros racionais positivos:

2 < a, chegamos a uma contradicao.

n+1 para todo natural pelo PBO, existe a ∈ F tal que a e o menor elemento de F. Como a ∈ F temos que Sa 6= a

++

. Assim, temos:

Mas isso contradiz Sa 6= a

ou seja, Sn = n

CAPITULO 1. OS PRINCIPIOS DE INDUC AO MATEMATICA E DA BOA ORDENAC AO 9

1.6 Exercıcios 1. Verifique, por inducao, as seguintes formulas para n > 1:

(a) 1 + 2 + 3 ++ n =
(b) 1 + 3 + 5 ++ (2n − 1) = n2
(c) 5 + 9 + 13 ++ (4n + 1) = n(2n + 3)
(d) 1 + 4 + 9 ++ n2 =
(e) 1.2 + 2.3 + 3.4 ++ n(n + 1) =
(f) 1 + 23 + 3 ++ n3 =
(g) (1 + 25 + 35 ++ n5) + (1 + 27 + 37 + ... + n7) = 2

3. Considere a progressao aritmetica (P.A.) de razao r e primeiro termo a1.

(a) Estabeleca uma formula para an, o n-esimo termo, e demonstre-a por inducao.

(b) Mostre que a soma Sn dos n primeiros termos desta progressao e dada por Sn = (a1 + an)n

4. Considere a progressao geometrica (P.G.) de razao q 6= 1 e primeiro termo a1.

(a) Estabeleca uma formula para an, o n-esimo termo, e demonstre-a por inducao.

(b) Mostre que a soma Sn dos n primeiros termos desta progressao e dada por Sn = anq − a1 q −1

5. Encontre a lei geral augerida e em seguida demonstre-a por inducao.

6. Mostre por inducao que:

7. Use o Princıpio da Boa Ordenacao para provar que qualquer subconjunto dos inteiros nao vazio e limitado superiormente tem um maior elemento.

CAPITULO 1. OS PRINCIPIOS DE INDUC AO MATEMATICA E DA BOA ORDENAC AO 10

8. Prove que nao existe inteiro m tal que 0 < m < 1.

9. Se a e b sao dois inteiros positivos quaisquer, prove que existe um inteiro positivo n tal que na > b. (Use o PBO).

10. A equivalencia dos Princıpios de Inducao e da Boa Ordenacao.

(a) Prove que a primeira forma do PIM e equivalente ao PBO. (b) Conclua que:

i. a segunda forma do PIM e equivalente ao PBO. i. as duas formas do PIM sao equivalentes.

Capıtulo 2 Divisibilidade

2.1 Relacao de divisibilidade em Z

Definicao 2.1 Dados dois inteiros a e b, dizemos que b divide a se, e somente se, existe um inteiro q tal que a = bq.

Observacao 2.1 Se b divide a tambem dizemos que: • b e um divisor de a.

1. A notacao b | a nao deve ser confundida com a fracao b

2. A relacao R, no conjunto Z dos numeros inteiros, definida por: b R a ⇔ b | a, denomina-se relacao de divisibilidade em Z.

Proposicao 2.1 Sejam a,b,c e d inteiros quaisquer. Podemos afirmar que:

CAPITULO 2. DIVISIBILIDADE 12

Prova:

CAPITULO 2. DIVISIBILIDADE 13

Observacao 2.3

Se a | bk, para k = 1,2,...,n, entao a | (b1x1 + b2x2 ++ bnxn) para todo inteiro x1,x2,...,xn.

1. A propriedade 10 pode ser generalizada:

2.2 Conjunto dos divisores de um inteiro

Exemplo 2.2

Observacao 2.4

2.3 Divisores comuns de dois inteiros

Observacao 2.5

CAPITULO 2. DIVISIBILIDADE 14

2.3.1 Exercıcios

1. Decida se as afirmacoes abaixo sao verdadeiras ou falsas, dando a demonstracao ou um contraexemplo. Sejam a,b e c inteiros.

2.4 Algoritmo da Divisao

Lema 2.1 (Lema da divisao de Euclides) Sejam a e b inteiros com a > 0 e b > 0. Entao existem unicos inteiros q e r tais que a = bq + r, onde q > 0 e 0 6 r < b.

Prova:

Teorema 2.1 (Algoritmo da Divisao) Sejam a e b inteiros com b 6= 0. Entao existem unicos inteiros q e r que satisfazem as condicoes a = bq + r e 0 6 r < |b|.

E o lema da divisao de Euclides mostrado anteriormente. 2o caso: a > 0 e b < 0

CAPITULO 2. DIVISIBILIDADE 15

Observacao 2.6

1. Os inteiros q e r sao denominados, respectivamente, o quociente e o resto da divisao de a por b.

2. b e divisor de a (b | a) se, e somente se, r = 0. Neste caso a = bq e o quociente q na divisao exata de a por b indica-se por ab ou a/b.

2.4.1 Exercıcios

1. Encontre q e r na divisao de a = 59 por b = −14 que satisfacam as condicoes do algoritmo da divisao.

9. Prove que, de n numeros consecutivos, um e multiplo de n. 10. Prove que todo inteiro da forma 6k + 5 e tambem da forma 3k + 2, mas nao vale a recıproca. 1. Mostre que o cubo de um inteiro qualquer e de uma das formas: 9k, 9k + 1 ou 9k + 8. 12. Mostre que, se a | (2x − 3y) e a | (4x − 5y), entao a | y, onde a,x e y sao inteiros. 13. Determine os inteiros positivos que divididos por 17 deixam um resto igual ao quadrado do quociente. 14. Para todo inteiro a, prove que 4 | (a2 + 2).

CAPITULO 2. DIVISIBILIDADE 16

15. Prove que, se a e b sao inteiros com b > 0, entao existem unicos inteiros q e r tais que a = bq + r, com 2b 6 r < 3b.

16. Mostre que se a e b sao inteiros ımpares, entao a2 − b2 e divisıvel por 8.

17. Na divisao de dois inteiros positivos o quociente e 16 e o resto e o maior possıvel. Encontre os dois inteiros, sabendo que a sua soma e 341.

18. Mostre que o produto de dois inteiros ımpares e um inteiro ımpar. 19. Sendo a um inteiro, mostre que a2 deixa resto 0,1 ou 4 quando dividido por 8. 20. Mostre que todo inteiro ımpar pode ser escrito como diferenca de dois quadrados.

21. Sejam a,b,m ∈ Z, com m 6= 0. Mostre que se m | b − a, entao a e b deixam o mesmo resto quando divididos por m.

2. Prove que:

(a) A soma dos quadrados de dois inteiros ımpares nao pode ser um quadrado perfeito. (b) A diferenca de dois cubos de inteiros consecutivos nao e divisıvel por 2.

23. (a) Demonstre que todo quadrado perfeito e da forma 5k ou 5k ± 1. (b) Como aplicacao, indique em quais algarismos pode terminar um quadrado perfeito.

(c) Demonstre que, se tres inteiros positivos a,b,c verificam a condicao a2 = b2 + c2, entao, entre eles ha um multiplo de 5 e um multiplo de 2.

2.5 Representacao de um numero em uma base qualquer

(Parte 1 de 3)

Comentários