Baixe o app para aproveitar ainda mais
Prévia do material em texto
Jaime Evaristo Eduardo Perdigão Introdução à Álgebra Abstrata Manual de Soluções Introdução à Álgebra Abstrata (soluções dos exercícios) 2 Apresentação As páginas seguintes contêm as soluções dos exercícios do livro Introdução à Álgebra Abstrata e algumas observações sobre incorreções já detectadas. Mesmo com o risco da repetitividade, as soluções foram apresentadas da forma mais detalhada possível, isto sendo feito para que a tarefa do leitor seja facilitada quando da tentativa da compreensão de alguma solução. Naturalmente, o estudante só deve recorrer às soluções apresentadas após esgotar todas as suas possibilidades no sentido da obtenção de uma solução encontrada por si mesmo. Considerando que o leitor poderá imprimir este manual em editores com configurações diferentes, não me preocupei em formatar corretamente as expressões matemáticas corretamente no sentido de escrevê-las numa única linha ou repetir, se for o caso, na linha seguinte o operador que concluiu a linha. Espero (e agradeço antecipadamente) receber sugestões de soluções diferentes daquelas apresentadas ou críticas e comentários sobre estas e sobre o livro como um todo. Qualquer crítica ou sugestão deve ser enviada para jaime@ccen.ufal.br e será muito bem vinda. Em Maceió, novembro de2002. mailto:jaime@ccen.ufal.br Introdução à Álgebra Abstrata (soluções dos exercícios) 3 Capítulo 1 1.1. As peculiaridades da raça humana não permitem garantir que a relação "x ama y" é reflexiva (existe alguém que não ame a si mesmo?). Infelizmente para os apaixonados, a relação não é simétrica: "Ada ama Pedro" não obriga que "Pedro ama Ada". A relação também não é antissimétrica: se "Ada ama Pedro" e "Pedro ama Ada" não temos, obviamente, Pedro = Ada; e também não é transitiva: se "Ada ama Pedro" e "Pedro ama Andréa" não podemos concluir que "Ada ama Andréa" (em geral, a conclusão é: "Ada odeia Andréa"). 1.2 a) Pela propriedade da igualdade dos conjuntos, devemos provar que A A A e que A A A. Porém, estas duas inclusões são óbvias, pois se x A A, então, por definição, x A ou x A, o que resulta x A. Reciprocamente, se x A, pela própria definição de união, x A A. b) Decorre da própria definição de união de conjuntos. c) Devemos mostrar que A (B C) (A B) C e que (A B) C A (B C). Mostremos apenas que A (B C) (A B) C, pois a demonstração da outra inclusão é semelhante. Temos que, e x A (B C), então (x A) (x B C). Daí, (x A) ((x B) (x C)). Temos então, pela associatividade da disjunção, ((x A) (x B)) (x C), o que significa que x (A B) C, como queríamos. d) Por definição, temos que A = {x U| (x A) (x )}. Porém, como x define uma contradição em U, temos que (x A) (x ) também é uma contradição em U. Daí, A = . Uma outra solução é a seguinte: por redução ao absurdo (discutido no exercício 1.12), suponhamos que A possui elementos. Assim, existe x A . Daí, pela definição de interseção de conjuntos, x A e x , o que é um absurdo. Logo A não possui elementos. e) Decorre imediatamente da definição de interseção de conjuntos. f) Vamos mostrar apenas que A (B C) (A B) C. Temos que, se x A (B C), então (x A) ((x B) (x C)). Assim, pela associatividade da conjunção, ((x A) (x B)) (x C) e, então, x (A B) C, como queríamos. g) Devemos mostrar que A (B C) (A B) (A C) e que (A B) (A C) A (B C). Para a primeira inclusão, seja x A (B C). Então, (x A) (x B C), o que implica (x A) ((x B) (x C)). Daí, pela distributividade da conjunção em relação à disjunção, ((x A) (x B)) ((x A) (x C)). Segue então que (x A B) (x A C), o que dá x (A B) (A C). A demonstração da segunda inclusão é, praticamente, um caminho de volta na demonstração acima. h) Vamos mostrar apenas que A (B C) (A B) (A C), já que a demonstração da outra inclusão é o caminho de volta. Seja então x A (B C). Daí, (x A) (x B C) e, portanto, (x A) ((x B) (x C)). Segue então que ((x A) (x B)) ((x A) (x C)), o que resulta em (x A B) (x A C). Daí, x (A B) (A C). 1.3. Suponhamos inicialmente que A B = A e provemos que A B. Para isto, seja x A. Daí, e da hipótese, x A B e, portanto, x B. Reciprocamente, suponhamos que A B e provemos que A B = A. Por definição temos que A B A e se x A, como A B, x B de onde se conclui que x A B. Logo, A A B. 1.4. a) Se x A, x CB(A) e, portanto, x CB(CB(A)). Assim, A CB(CB(A)). Reciprocamente, se x CB(CB(A)), x CB(A) e, portanto, x A. Assim, CB(CB(A)) A. b) Seja x A. Então x CB(A) e, então, como CB(A') CB(A), x CB(A'). Daí, x A'. MAceio Destacar MAceio Destacar MAceio Destacar MAceio Destacar Introdução à Álgebra Abstrata (soluções dos exercícios) 4 c) Seja x CB(A A'). Então, x A A' o que gera três possibilidades: x A e x A'; x A' e x A; e x A e x A'. Da primeira segue que x CB(A); da segunda, x CB(A’); e da terceira x CB(A) CB(A'). Segue então que x CB(A) CB(A'). Reciprocamente, se x CB(A) CB(A'), x CB(A) ou x CB(A') e, portanto, x A ou x A'. Isto só acontece se x A A' o que mostra que x CB(A A'). Daí, CB(A) CB(A') CB(A A'). 1.5. a) Sejam os conjuntos A = {a, b, c}, B = {b, d} e C = {a, d}. Evidentemente, B C, mas A B = A C = {a, b, c, d}. b) Considere os conjuntos A = {a, b, c}, B = {a, b, d} e C = {a, b, e}. Evidentemente, B C, mas A B = A C = {a, b}. 1.6. Pela propriedade da igualdade dos conjuntos, basta provar que B C e que C B. Para a primeira, seja x B. Então x A B, e, como por hipótese, A B = A C, x A C. Desta última relação temos que x A ou x C. Se x C, temos o que queríamos, todo elemento de B é elemento de C; se x A, então x A B e, portanto, x A C, pois, por hipótese, A B = A C. Daí, x C, dando então, também, o que queríamos. A demonstração de que C B é idêntica, mutatis mutandis. 1.7. Sejam P, Q e R predicados num conjunto A. Devemos mostrar que P (Q R) = (P Q) R. Como predicados são funções do conjunto A no conjunto {V, F}, basta mostrar que (P (Q R))(x) = ((P Q) Q)(x), para todo x A. Podemos verificar esta igualdade na seguinte tabela, de acordo com os possíveis valores de P(x), Q(x) e R(x). P Q R Q R P Q P (Q R) (P Q) R V V V V V V V V V F V V V V V F V V V V V V F F F V V V F V V V V V V F V F V V V V F F V V F V V F F F F F F F Uma tabela como esta é chamada, de um modo geral, tabela verdade e a construção de tabelas verdade pode ser utilizada para a verificação de igualdade de predicados. 1.8. a) P Q R Q R P Q P R P (Q R) (P Q) (P R) V V V V V V V V V V F V V F V V V F V V F V V V V F F F F F F F F V V V F F F F F V F V F F F F F F V V F F F F F F F F F F F F MAceio Destacar MAceio Destacar MAceio Destacar MAceio Destacar Introdução à Álgebra Abstrata (soluções dos exercícios) 5 b) P Q R Q R P Q P R P (Q R) (P Q) (P R) V V V V V V V V V V F F V V V V V F V F V V V V V F F F V V V V F V V V V V V V F V F F V F F F F F V F F V F F F F F F F F F F 1.9. a) P Q ~P ~Q P Q ~(P Q) (~P) (~Q) V V F F V F F V F F V F V V F V V F F V V F F V V F V V b) P Q ~P ~Q P Q ~(P Q) (~P) (~Q) V V F F V F F V F F V V F F F V V F V F F F F V V F V V 1.10. P Q ~P P Q (~P) Q V V F V V V F F F F F V V V V F F V V V 1.11 P Q ~P ~Q P Q (~Q) (~P) V V F F V V V F F V F F F V V F V V F F V V V V 1.12. P Q C ~Q P (~Q) (P (~Q)) C P Q V V F F F V V V F F V V F F F V F F F V V F F F V F V V 1.13. Se P(x) = Q(x) = V, então (P Q)(x) = V e (Q P)(x) = V e, portanto, ((P Q) (Q P))(x) = (P Q)(x) = V. Se P(x) = V e Q(x) = F, então (P Q)(x) = F e, assim, ((P Q) (Q P))(x) = (P Q)(x) = F. Se P(x) = F e Q(x) = V, então (Q P)(x) = F e, por conseguinte, (P Q) (Q P))(x) = (P Q)(x) = F. Introdução à Álgebra Abstrata (soluções dos exercícios) 6 1.14. a) Seja y f(X). Queremos mostrar que y f(Y). De y f(X) segue que existe x X tal que y = f(x). Como, por hipótese, X Y, temos que x Y e, portanto, y = f(x) f(Y). b) Seja y f(X Y). Então existe x X Y tal que y = f(x). Daí, existe x X tal y = f(x) ou existe x Y tal que y = f(x). Segue então que y f(X) ou y f(Y) o que resulta y f(X) f(Y). Reciprocamente, seja y f(X) f(Y). Então y f(X) ou y f(Y). Daí, existe x X ou x Y tal que y = f(x) e, portanto, existe x X Y tal que y = f(x). Logo, y f(X Y). c) Seja y f(X Y). Então existe x X Y tal que y = f(x). De x X Y, segue que x X e x Y. Como y = f(x), temos que y f(X) e y f(Y) o que mostra que y f(X) f(Y) d) Sejam A = {a, b, c, d}, B = {a, b, c}, f = {(a, a), (b, b), (c, c), (d, a)}, X = {a, b, c} e Y = {b, c, d}. Temos, X Y = {b, c}, f(X) = {a, b, c}, f(Y) = {a, b, c}, f(X Y) = {b, c} e f(X) f(Y) = {a, b, c}. e) Seja y f(X) - f(Y). Então y f(X) e y f(Y). Daí, existe x X tal que y = f(x) e, para todo z Y, y f(z). Logo, x Y, o que implica x X - Y e y f(X - Y). f) Sejam A = {a, b}, B = {c}, X = {a}, Y = {b} e a função f = {(a, c), (b, c)} definida de A em B. Temos que X - Y = {a}, f(X - Y) = {c}, f(X) = {c}, f(Y) = {c} e f(X - Y) = . 1.15. a) Seja x f -1(Y). Então f(x) Y e, portanto, f(x) Z, já que Y Z. De f(x) Z segue que x f -1(Z). b) Suponhamos inicialmente que x f -1(Z Y). Então f(x) Z Y e, por conseguinte, f(x) Z ou f(x) Y. Daí, x f -1(Z) ou x f -1(Y), o que mostra que x f -1(Z) f -1(Y). Agora, suponhamos que x f -1(Z) f -1(Y). Assim, x f -1(Z) ou x f -1(Y) e, por conseguinte, f(x) Z ou f(x) Y, o que mostra que f(x) Z Y. Daí, x f -1(Z Y). c) Provemos apenas que f -1(Z) f -1(Y) f -1(Z Y), pois a outra inclusão é, como no item anterior, o caminho de volta. Seja, então, x f -1(Z) f -1(Y). Assim, x f -1(Z) e x f -1(Y) donde se conclui que f(x) Z e f(x) Y. Logo, f(x) Z Y e x f -1(Z Y). d) Como no anterior, basta provar uma das inclusões. Seja, então, x f -1(Z) - f -1(Y). Assim, x f -1(Z) e x f -1(Y) donde se conclui que f(x) Z e f(x) Y. Segue que f(x) Z - Y e x f -1(Z - Y). 1.16. a) Sejam a1 e a2 elementos distintos de A. Devemos provar que (g o f)(a1) (g o f)(a2). Como f é injetora e a1 a2 temos que f(a1) f(a2). Como g é injetora g(f(a1)) g(f(a2)). b) Seja c C. Devemos provar que existe a A tal que (g o f)(a) = c. Como g é sobrejetora, existe b B tal que g(b) = c. Como f é sobrejetora, existe a A tal que b = f(a). Daí, g(f(a)) = c. c) Suponhamos, por redução ao absurdo (ver exercício 1.12) que f não é injetora. Assim existem elementos a1 e a2 em A, com a1 a2, tais que f(a1) = f(a2). Desse modo, como g é uma função, segue que g(f(a1)) = g(f(a2)) o que implica (g o f)(a1) = (g o f)(a2). Daí se conclui que g o f não é injetiva, o que contraria a hipótese. d) Sejam b1 e b2 em B, com b1 b2. Devemos mostrar que g(b1) g(b2). Como f é sobrejetiva, existem a1 e a2 tais que b1 = f(a1) e b2 = f(a2). Evidentemente, a1 a2 pois, do contrário, f não seria uma função. Daí e da hipótese de que g o f é injetiva, temos que (g o f)(a1) (g o f)(a2) o que implica g(f(a1)) g(f(a2)). Portanto, g(b1) g(b2). e) Seja c C. Necessitamos mostrar que existe b B tal que g(b) = c. Da hipótese de que g o f é sobrejetora segue que existe a A tal que (g o f)(a) = c, o que resulta em g(f(a)) = c. Tomando b = f(a) temos que g(b) = c como precisávamos. MAceio Destacar MAceio Destacar MAceio Destacar MAceio Destacar MAceio Destacar MAceio Destacar MAceio Destacar MAceio Destacar MAceio Destacar MAceio Destacar MAceio Destacar MAceio Destacar MAceio Destacar MAceio Destacar MAceio Destacar MAceio Destacar MAceio Destacar MAceio Destacar Introdução à Álgebra Abstrata (soluções dos exercícios) 7 f) Seja b B. Queremos mostrar que existe a A tal que b = f(a). Para isto seja c = g(b). Como g o f é sobrejetora, existe a A tal que (g o f)(a) = c ou g(f(a)) = c. Das igualdades c = g(b) e c = g(f(a)) e da hipótese de que g é injetora segue que b = f(a), como queríamos. g) Segue dos itens a e b acima. h) Como f é bijetora, segue que f -1 existe (página 24). Além disto f -1 é inversível (página 23). Então, , f -1 é bijetiva. 1.17. Sejam os conjuntos A = {a, b}, B = {c, d, e} e C = {g, h} e as funções f = {(a, c), (b, d)}, de A em B, e g = {(c, g), (d, h), (e, h)}, de B em C . Temos que g o f = {(a, g), (b, h)} é bijetora e f e g não o são. 1.18. Inicialmente, suponhamos que existe uma função g de B em A tal que f o g = IB e provemos que f é sobrejetora. Para isto, seja b B. Assim, g(b) A e f(g(b)) = Ib(b) = b, o que mostra que f é sobrejetora. Agora suponhamos que f é sobrejetora e construamos uma função g de B em A tal que f o g = IB. Como f é sobrejetora, para todo y B existe x A tal que y = f(x). Definamos então g de B em A associando a cada y B um, e somente um, dos x A tal que y = f(x). Assim, claramente g está bem definida, f(g(y)) = f(x) = y e f o g = IB. 1.19. Inicialmente, suponhamos que existe uma função g de B em A tal que g o f = IA e provemos que f é injetora. Para isto sejam x1, x2 A com x1 x2. Se, por redução ao absurdo, f(x1) = f(x2), então g(f(x1)) = g(f(x2)), (g o f)(x1) = (g o f)(x2) e, assim, x1 = x2, contrariando a hipótese levantada acima. Agora suponhamos que f é injetora e construamos uma função g de B em A tal que g o f = IA. Dado y B, se y f(A), defina g(y) como sendo o único x A tal que y = f(x) (a unicidade de x é garantida pela injetividade de f) e se y F(A) defina g(y) como sendo qualquer valor em A. Assim, claramente g está bem definida e g(f(x)) = g(y) = x, o que mostra que g o f = IA. Capítulo 2 2.1 a) Pelo axioma 3, basta provar que P(1) = V e que se P(n) = V, então P(S(n)) = V. Temos que P(1) = V pois 1 = 12. Suponhamos que 1 + 3 + ... + (2n – 1) = n2 e provemos que 1 + 3 + ... + (2n – 1) + (2(n+1) – 1) = (n + 1)2. Temos que 1 + 3 + ... + (2n – 1) + (2(n+1) – 1) = n2 + (2(n+1) – 1) = n2 + 2n + 1 = (n + 1)2. b) Temos que P(1) = V pois 2 = 1 . (1 + 1). Suponhamos que 2 + 4 + ... + 2n = n . (n + 1) e provemos que 2 + 4 + ... + 2n + 2(n+1) = (n + 1) . (n + 2). Temos que 2 + 4 + ... + 2n + 2(n+1) = n . (n + 1) = 2(n + 1) + n . (n + 1) = (n + 1) . (n + 2). 2.2 Se m = 1, a afirmação decorre do postulado 2. Se m > 1, então n + m > n + 1 > 1. 2.3 Observações 1. Para coerência com os itens da questão, o enunciado deveria ser: Representando por n – m a solução da equação solúvel m + x = n... 2. A igualdade apresentada no item (e) está errada. A igualdade correta é: e) (n – m) . (p – q) = (n . p + m . q) – (m . p + n . q) a) Sendo n – m a solução da equação m + x = n, temos que m + (n – m) = n. Segue então que (m + p) + (n – m) = (n + p). Assim a equação (m + p) + x = (n + p) tem solução igual a n – m. Pela notação fixada no exercício, temos então que n – m = (n + p) – (m + p). b) Sendo n – m a solução da equação m + x = n, temos que m + (n – m) = n e, portanto, m + p = n. Daí, pela comutatividade da adição p + m = n e, assim, m é solução da equação p + x = n. Pela notação fixada, m = n – p. MAceio Destacar MAceio Destacar MAceio Destacar MAceio Destacar MAceio Destacar MAceio Destacar MAceio Destacar MAceio Destacar MAceio Destacar MAceio Destacar MAceio Destacar MAceio Destacar Introdução à Álgebra Abstrata (soluções dos exercícios) 8 c) Sendo n – m a solução da equação m + x = n, temos que m + (n – m) = n e, então, p . (m + (n – m)) = p . n. Daí, p . m + p . (n – m) = p . n e, assim, p . (m – n) é solução da equação p . m + x = n . p. A igualdade segue da notação adotada. d) De q + (p – q) = p e m + (n – m) = n segue que (m + q) +((n + m) + (p – q)) = (n + p). Daí, a igualdade. e) De q + (p – q) = p segue, por multiplicação por (n – m), q . (n – m) + (p – q). (n – m) = p. (n – m). Daí, (q . n – q . m) + (p – q) . (n – m) = p. n – p . m e, por conseguinte, (p – q) . (n – m) = (p. n – p . m) - (q . n – q . m). Assim, pelo item 2.4. Temos, por aplicações sucessivas da distributividade da multiplicação em relação à adição, (m + p) . (n + q) = (m + p) . n + (m + p) . q = m . n + p . n + m . q + p . q. 2.5 Temos n m = n + m + n . m = m + n + m . n = m n o que mostra que é comutativa. Da mesma forma, n (m p) = n + (m p) + n . (m p) = n + m + p + m . p + n . (m + p + m . p) = n + m + p + m . p + n . m + n . p + n . m . p = (n + m + n . m) + p + (m . p + n . p + n . m . p) = (n m) + p + (m + n + n . m) . p = (n m) + p + (n m) . p = (n m) p. 2.6 Observação: A afirmação do item (c) não tem sentido pois o conjunto dos naturais não contém nenhum elemento simbolizado por 0. a) Se a + c b + c, então a + c = b + c ou a equação (a + c) + x = (b + c) é solúvel. Se a primeira acontece, pela proposição 2.2, a = b. Se existe natural r tal que (a + c) + r = (b + c), então, pela mesma proposição, a + r = b e a equação a + x = b é solúvel.. b) Se a b e c d, a = b ou a + x = b é solúvel e c = d ou c + x = d é solúvel. Se a = b e c = d, então a + c = b + d. Se a = b e existe r tal que c + r = d, então (c + a) + r = (d + b) e a equação (a + c) + x = (b = d) é solúvel. Se existe r tal que a + r = b e c = d, o raciocínio é semelhante. Finalmente, se existem r e r´ tais que a + r = b e c + r´ = d, temos (a + c) + (r + r´) = (b + d) e a equação (a + c) + x = (b + d). c) Ver observação acima. d) De a < b e b < c segue a b e a b e b c e b c. Daí, por transitividade, a c. Se a = c, teríamos c < b, contrariando a hipótese b < c. e) De a < b segue que a b e a b. Daí, como b c, temos por transitividade, a c. Se a = c, teríamos b a, contrariando a hipótese a < b. g) De a < b temos a b e a b. Assim, pelo item (a) a + c b + c, para qualquer natural c. Se a + c = b + c, teríamos a = b, contrariando o fato de que a b. 2. 7 a) De a < b, segue a b e a b. Daí, pela proposição 4.2, a . c b . c. Se a . c = b . c, pela lei do corte (proposição 3.2), a = c, contrariando o fato de que a b. 2.8. Observação A desigualdade que se pretende provar é: n . (t – r) + m . (s + r) n . t + m . s. Observe que a desigualdade pretendida poderia ser escrita, de maneira mais simples, da seguinte forma: n . s + m . t n . t + m . s. Foi dada a preferência pela forma anterior para que a solução por indução fosse pensada. Façamos uma indução sobre r. Se r = 1, de m n e s s + 1 segue n . s + m . (s + 1) = n . s + m . s + m n . s + m . s + n = n . (s + 1) + m . s. Suponhamos que n . s + m . (s + r) n . (s + r) + m . s e provemos que n . s + m . (s + r + 1) n . (s + r + 1) + m . s. MAceio Destacar MAceio Destacar Introdução à Álgebra Abstrata (soluções dos exercícios) 9 Temos n . s + m . (s + r + 1) = n . s + m . (s + r) + m n . (s + r) + m . s + m n . (s + r) + m . s + n = n . (s + r + 1) + m . s 2.9. A questão é que não está definido o que é número pequeno. 2.10. f(n) = 1 se n = 1 e f(n) = n – 1, se n > 1. Capítulo 3 3.1. a) Basta adicionar -c a ambos os termos da igualdade: (a + c) + (-c) = (b + c) + (-c) e, portanto, a + (c - c) = b + (c - c). b) Basta adicionar -a a ambos os termos da igualdade c) Se, por contradição, 2 . a = a, teríamos a + a = a e, pelo item anterior, a = 0, contrariando a hipótese de que a 0. 3.2. a) Pela proposição 2.3, -(a + b) = (-1) . (a + b). Daí, por (AM), -(a + b) = (-1) . a + (-1) . b. Aplicando novamente a proposição 2.3, -(a + b) = -a + (-b) = -a - b. b) Calculemos (a + b) . (a - b) de acordo com a seguinte seqüência de igualdades, justificadas ao lado. (a + b) . (a - b) = (a + b) . a + (a + b) . (-b) (AM) (a + b) . (a - b) = a . a + b . a + a . (-b) + b . (-b) (AM) (a + b) . (a - b) = a . a+ a . b - a .b - b . b (M2 e proposição. 2.5) (a + b) . (a - b) = a2 - b2 (simbologia e A4) 3.3. Suponhamos que a e b são inversíveis. Então existem a-1 tal que a . a-1 = 1 e b-1 tal que b . b-1 = 1. Assim (a . b) . (a-1 . b-1) = ((a . b) . a-1) . b-1 (M1) (a . b) . (a-1 . b-1) = (a-1 . (a . b)). b-1 (M2) (a . b) . (a-1 . b-1) = ((a-1 . a) . b) . b-1 (M1) (a . b) . (a-1 . b-1) = (1 . b) . b-1 (definição de inverso) (a . b) . (a-1 . b-1) = b . b-1 (M3) (a . b) . (a-1 . b-1) = 1 (definição de inverso). Reciprocamente, suponhamos que a . b é inversível. Então existe x A tal que (a . b) . x = 1. Daí, por (M1), a . (b . x) = 1 e a é inversível. Agora, aplicando sucessivamente (M2) e (M1), b . (a . x) = 1 e b também é inversível. 3.4. a) De a2 = 0 segue que a . a = 0. Como D é um domínio de integridade, por (M4), a = 0 ou a = 0. b) De a . b = a, segue a. b - a = 0 e a . (b - 1) = 0. Como D é um domínio de integridade, por (M4), a = 0 ou b - 1 = 0, o que dá a = 0 ou b = 1. c) Basta fazer b = a no item anterior. 3.5. a) Basta, aplicando a compatibilidade com a adição da relação de ordem, adicionar -c a ambos os termos da desigualdade. b) De a b segue que a + c b + c e de c d segue que b + c b + d. Daí, por transitividade, a + c b + d. MAceio Destacar MAceio Destacar MAceio Destacar MAceio Destacar MAceio Destacar MAceio Destacar MAceio Destacar MAceio Destacar MAceio Destacar MAceio Destacar MAceio Destacar Introdução à Álgebra Abstrata (soluções dos exercícios) 10 c) De c 0 segue, aplicando a proposição 5.3, que -c 0. Agora, de a b segue, aplicando a compatibilidade com a multiplicação, a . (-c) b . (-c). Daí, -(a. c) -(b . c), -(a. c) + b . c -(b . c) + b . c e -(a. c) + b . c + a . c 0 + a. c, chegando, finalmente, a b . c a . c. d) De a < b e b < c segue que a b e a b e que b c e b c. Por transitividade, segue que a c. Se a = c, de a < b seguiria que c < b, contrariando a hipótese b < c. Logo, a c e a c o que implica a < c. e) De a < b segue que a b e a b. Como b c, por transitividade, segue que a c. Se a = c, de a < b seguiria que c < b, contrariando a hipótese b c. Logo, a c e a c o que implica a < c. g) De a < b segue que a b e a b. Pela compatibilidade com a adição, a + c b + c. Se a + c = b + c teríamos, pelo exercício 2.1, a = b, contrariando a b. Logo a + c b + c e a + c b + c o que implica a + c < b + c. 3.6. a) Se a 0, pela compatibilidade com a multiplicação, a . a 0 o que dá a2 0. Se a 0, pela proposição 5.3, -a 0 e então, mais uma vez pela compatibilidade com a multiplicação, a . (-a) 0. Daí, -a2 0 e então, pela proposição já citada, a2 0. b) Como 1 = 12 temos, do item anterior, que 1 0. Como, por definição, 1 0, temos que 1 > 0. c) De 1 0 segue que -1 0. Se -1 = 0 teríamos 1 = 0, contrariando a definição de elemento neutro da multiplicação. Logo, -1 0 e -1 = 0 o que dá -1 < 0. 3.7. a) De a < b segue que a b e a b. De c > 0 segue que c 0 e c 0. Aplicando a compatibilidade com a multiplicação à desigualdade a b temos que a . c b . c. Agora, se a . c = b . c teríamos, pela lei do cancelamento, a = b. Logo, a . c b . c e a . c b . c o que implica a . c < b . c. b) Se, por redução ao absurdo, tivéssemos a > b, pelo item anterior teríamos a . c > b . c contrariando a hipótese a . c b . c. c) De a . c b . c segue que -(b . c) -(a . c) e que, aplicando a proposição 2.3, b . (-c) a . (-c). Como c < 0 temos -c > 0 e então, pelo item anterior, b a. Observe que estes dois últimos itens garantem uma lei do cancelamento para desigualdades em domínios de integridade, bastando observar que se o termo a ser cancelado for negativo o sinal da desigualdade será invertido. 3.8. Observação: O enunciado do item (ii), é o seguinte:. ii) a - b A' e a . b A' quaisquer que sejam a, b A'. a) Se A' é um subanel de A, como 1A = 1A', 1A A'. Além disso, como as operações de A' são as restrições das operações de A, se a, b A', a - b = a -A' b A' e a . b = a .A' b A'. Reciprocamente, suponhamos que 1A A' e que a - b A' e a . b A', quaisquer que sejam a, b A' e provemos que A' é uma subanel de A. A condição a . b A' quaisquer que sejam a, b A' garante que .A' é uma operação em A'. Agora observe que, como 1A A', 0 = 1A - 1A A' e que se a A', -a = 0 - a A. Podemos deduzir daí também que se a, b A', a +A' b = a - (-b) A' o que mostra que +A' é uma operação em A'. Como +A' e .A' são restrições das operações do anel A, elas, naturalmente, herdam todas as propriedades destas operações. Assim, (A', +A', .A') é uma anel tal que 1A' = 1A e, portanto, A' é um subanel de A. b) Como f é um homomorfismo, f(1A) = 1B e 1B f(A). Assim a primeira condição do item anterior está satisfeita. Agora se z, y f(A), existem a, b A tais que z = f(a) e y = f(b) e, então, z - y = f(a) - f(b) = = f(a - b) e z . y = f(a) . f(b), sendo as últimas igualdades decorrentes da aplicação da proposição 2.6 e da definição de homomorfimo. Daí, z - y f(A) e z . y f(A). Logo, pelo item anterior, f(A) é um subanel de B. MAceio Destacar MAceio Destacar MAceio Destacar MAceio Destacar MAceio Destacar MAceio Destacar Introdução à Álgebra Abstrata (soluções dos exercícios) 11 3.9. a) Sejam m, n A. Temos que fa(m + n) = a . (m + n) = a . m + a . n = fa(m) + fa(n) e a primeira condição para que uma função seja um homomorfismo é satisfeita. Agora, fa(m . n) = a . (m . n) e fa(m) . fa(n) = (a . m) . (a . n) e a segunda condição não é satisfeita. Além disto, fa(1) = a . 1 = a que só é igual a 1 se a = 1. b) Suponhamos que fa é sobrejetora. Então, existe m A tal que fa(m) = 1 e, portanto, existe m A tal que a . m = 1 o que mostra que a é inversível. Reciprocamente, suponhamos que a é inversível e que b A. Devemos mostrar que existe m A tal que fa(m) = b. Para isto, basta tomar m = a-1 . b, pois fa(a-1 . b) = a . (a-1 . b) = b. c) Se m, n A e fa(m) = fa(n), então a . m = a . n e, como A é um domínio de integridade e a 0, m = n, o que mostra que fa é injetora. 3.10. Utilizando a nomenclatura da sugestão, vamos provar que g o f é um isomorfismo. Temos, tomando a, b A i) (g o f)(a + b) = g(f(a + b)) = g(f(a) + f(b)) (f é isomorfismo) (g o f)(a + b) = g(f(a)) + g(f(b)) (g é isomorfismo) (g o f)(a + b) = (g o f)(a) + (g o f)(b) (definição de função composta) ii) (g o f)(a . b) = g(f(a . b)) = g(f(a) . f(b)) (f é isomorfismo) (g o f)(a . b) = g(f(a)) . g(f(b)) (g é isomorfismo) (g o f)(a . b) = (g o f)(a) . (g o f)(b) (definição de função composta) iii) (g o f)(1A) = g(f(1A)) = g(1B) = 1C. 3. 11. a) Se c' e c" são dois elementos máximos, c' c" (levando em conta que c" é elemento máximo) e c" c' (levando em conta que c' é elemento máximo). Pela antissimetria da relação de ordem, c' = c". b) Inicialmente, suponhamos que todo subconjunto não vazio limitado superiormente possui elemento máximo e provemos que todo subconjunto não vazio limitado inferiormente possui elemento mínimo. Seja S limitado inferiormente e considere o conjunto -S = {x A| -x S}. Como S é não vazio, -S também o é. Como S é limitado inferiormente, existe a A tal que x a, para todo x S. Daí, -x -a para todo x A e, portanto, para todo y -S, y -a, o que mostra que -S é limitado superiormente. Assim, -S tem um elemento máximo b. Ou seja, existe b -S tal que y b, para todo y -S. Como b -S, -b S e dado x S, -x -S o que implica -x b. Daí, x -b, para todo x S e, portanto, S é tem elemento mínimo, exatamente o simétrico do elemento mínimo de -S. A demonstração da afirmação recíproca é idêntica, mutatis mutandis. 3.12. O erro acontece na aplicação da lei do cancelamento à igualdade 2 . (a2 - a . b) = 1 . (a2 - a . b), pois, como supomos acima que a = b, a2 - a . b = 0 e a lei do cancelamento não pode ser aplicada. 3.13. A adição em F(A) é comutativa e associativa, decorrências da comutatividade e da associatividade do anel A: para todo x A, (f + g)(x) = f(x) + g(x) = g(x) + f(x) = (g + f)(x) (o que mostra que f + g = g + f) e ((f + g) + h))(x) = (f + g)(x) + h(x) = (f(x) + g(x)) + h(x) = f(x) + (g(x) + h(x)) = (f + (g + h))(x) (o que mostra que (f + g) + h = f + (g + h). A adição tem elemento neutro: a função 0 definida por 0(x) = 0, para todo x A (a função 0 é chamada identicamente nula); o elemento simétrico de uma função f F(A) é a função -f definida por (-f)(x) = -f(x). A associatividade e a existência de elemento neutro da composição foram discutidas na seção 1.12. Porém a composição não é distributiva em relação à adição: sejam as funções f, g e IZ, de Z em Z, dadas por f(x) = x2, g(x) = 1 e IZ(x) = x. Temos (f o (g + IZ))(x) = = f((g + IZ)(x)) = f(g(x) + IZ(x)) = f(1 + x) = (1 + x)2 e (f o g + f o IZ)(x) = (f o g)(x) + (f o IZ)(x) = = f(g(x)) + (f(IZ(x)) = f(1) + f(x) = 1 + x, e, portanto, f o (g + IZ) f o g + f o IZ. 3.14. De z < 0 segue -z > 0 e, então, pela proposição 3.1, -z 1 e, assim, z -1. Introdução à Álgebra Abstrata (soluções dos exercícios) 12 3.15. Observação: Aproveitando a oportunidade, retificamos o enunciado do item d da proposição 3.3, onde há o engano destacado em negrito, engano este que não ocorre na demonstração: |z| y se e somente se -y z y. a) A segunda desigualdade é a desigualdade triangular apresentada no item e da proposição 3.3. Para a primeira, temos |z| = |z + y - y| |z + y| + |-y| e, então, |z| - |y| |z + y|, já que |-y| = |y|. Do mesmo modo, |y| = |y + z - z| |z + y| + |-z| e, assim, |z| - |y| -|z + y|. Daí, pelo item d da proposição 3.3 (com a correção observada acima), ||z| - |y|| |z + y|. b) Para a segunda desigualdade, temos |z - y| = |z + (-y)| |z| + |-y| = |z| + |y|. Para a primeira, |z| = |z + y - y| |z - y| + |y| e, então, |z| - |y| |z - y|, já que |-y| = |y|. Do mesmo modo, |y| = |y + z - z| |-z + y| + |z| e, assim, |z| - |y| -|z - y|, já que |-z + y| = |z - y|. Daí, pelo item d da proposição 3.3 (com a correção observada acima), ||z| - |y|| |z - y|. 3.16. a) Fixemos m e façamos uma indução sobre n. Para n = 0 temos am . a0 = am . 1 = am = am+0, e a afirmação é verdadeira. Suponhamos que am . an = am+n e provemos que am . an+1 = am+n+1. Temos am . an+1 = am . (a . an) (definição de potência) am . an+1 = (am . an) . a (comutatividade/associatividade) am . an+1 = am+n . a (hipótese indutiva) am . an+1 = am+n+1 (definição de potência) b) Como acima, fixemos m e façamos uma indução sobre n. Para n = 0 temos (am)0 = 1 = a0 = am.0, e a afirmação é verdadeira. Suponhamos que (am)n = am.n e provemos que (am)n+1 = am.n+m. Temos (am)n+1 = am . (am)n (definição de potência) (am)n+1 = am . (am.n) (hipótese indutiva) (am)n+1 = am.n+m (item a) c) Façamos uma indução sobre m. Para m = 0, (a . b)0 = 1 = 1 . 1 = a0 . b0 e a afirmação é verdadeira. Suponhamos que (a . b)m = am . bm e provemos que (a . b)m+1 = am+1 . bm+1. Temos (a . b)m+1 = (a . b) . (a . b)m (definição de potência) (a . b)m+1 = (a . b) . (am . bm) (hipótese indutiva) (a . b)m+1 = (a . am) . (b . bm) (associatividade/comutatividade) (a . b)m+1 = am+1 . bm+1 (definição de potência) 3.17 a) Se 0 a b, como a2 0, temos 0 a . a2 b . a2 b . b2. Se a < 0 e b > 0, temos a3 < 0 e b3 > 0 e , então, a3 b3. Finalmente, se a b < 0, temos 0 < -b -a e, então, pela primeira parte, (-b)3 (-a)3 e, portanto, a3 b3. b) De forma semelhante ao item anterior, temos que se a < b, então a7 < b7. c) Se a . b 0, então -(a . b) 0 e a compatibilidade de com a soma garante que a2 - a . b + b2 0, já que a2 + b2 0. Se a . b > 0, como (a - b)2 0, temos a2 – 2 . a . b + b2 0, a2 - a . b + b2 a .b e a2 - a . b + b2 > 0, por transitividade. d) Suponhamos inicialmente que m > n e provemos que am > an. De m > n segue que m - n = p, com p > 0. Assim, m = n + p e ap > 1, já que a > 1. Então, am = an+p = an . ap e, portanto, am > an, já que ap > 1. Reciprocamente, suponhamos que am > an e provemos que m > n. Suponhamos por Introdução à Álgebra Abstrata (soluções dos exercícios) 13 absurdo que m n. Se m = n, am = an, contrariando a hipótesee se m < n, pela demonstração anterior, am < an, contrariando, mais uma vez, a hipótese. 3.18. Seja x z w 2 2 . . Assim, 2 . x = z + 2 . w e z = 2 . (x - w) o que mostra que x w z 2 . Daí, x z w 2 . 3.19. Indução sobre z. Se z = 1, 1 = 2 )11(.1 e a igualdade é verdadeira. Suponhamos que 1 + 2 + ... + z = 2 )1(. zz e provemos que 1 + 2 + ... + z + (z + 1) = 2 )2(.)1( zz . Temos 1 + 2 + ... + z + (z + 1) = 2 )1(. zz + (z + 1) = 2 )2(.)1( 2 )1(.2)1(. zzzzz . 3.20. Realizemos uma indução sobre n. Para n = 1, A e B possuirão apenas um elemento e, trivialmente, só existe uma função de A em B e esta é bijetiva. Como 1! = 1, temos que a afirmação é verdadeira para n = 1. Suponhamos que se |A| = |B| = n, então o número de bijeções de A em B é n! e provemos que se |A| = |B| = n + 1, então o número de bijeções de A em B é (n + 1)!. Seja então dois conjuntos A = {x1, x2, ..., xn+1} e B = {y1, y2, ..., yn+1} e considere os conjuntos C = A - {xn+1} e D = B - {yn+1}. Assim, |C| = |D| = n e, então, pela hipótese de indução, o número de funções bijetivas de C em D é n!. Agora a cada função bijetiva f de C em D corresponderão n + 1 funções bijetivas de A em B, a saber: g x y se j i e j n f x se j n f x se j i e j n i j n i j ( ) , ( ), ( ), 1 1 1 1 Assim, o número de funções bijetivas de A em B é (n + 1) . n! = (n + 1)!. 3.21. Provemos por indução sobre n. i) Para n = 1 temos (1 + z)1 = 1 + z = 1 + 1 . z e a afirmação é verdadeira. ii) Suponhamos que (1 + z)n 1 + n . z e provemos que (1 + z)n+1 1 + (n + 1) . z. Como z > -1, z + 1 > 0 e, então, aplicando a compatibilidade com a multiplicação à hipótese indutiva (1 + z)n . (z +1) (1 + n . z) . (1 + z). Daí, (1 + z)n+1 1 + (n + 1) . z + n . z2 1 + (n + 1) . z, sendo esta última desigualdade obtida da compatibilidade com a adição aplicada a n . z2 0. 3.22. Provemos por indução sobre n. i) Para n = 0, A = , P(A) = {} e |P(A)| = 1 = 20. ii) Suponhamos agora que se |A| = n, então |P(A)| = 2n e provemos que se |A| = n + 1, então |P(A)| = 2n+1. Seja A = {x1, ..., xn+1}. Evidentemente, os subconjuntos de A podem ser separados em subconjuntos que não contêm xn+1 e os subconjuntos que contêm este elemento. Os primeiros são subconjuntos do conjunto B = A - {xn+1} e, como |B| = n, eles são em número de 2n subconjuntos. Evidentemente, os subconjuntos que contêm xn+1 são da forma S {xn+1}, onde S é subconjunto de B, e, portanto, são também em número de 2n. Assim, |P(A)| = 2n +2n = 2 . 2n = 2n+1. 3.23. Fixemos m e provemos, por indução sobre n, que a afirmação é verdadeira para todo n 0. i) Para n = 0, (m . 0)(a . b) = 0(a . b) = 0 = (ma) . (0b), e a afirmação é verdadeira. Introdução à Álgebra Abstrata (soluções dos exercícios) 14 ii) Suponhamos que (m . n)(a . b) = (ma) . (na) e provemos que (m . (n+1))(a . b) = (ma) . ((n+1)b). Temos (m . (n+1))(a . b) = (m . n + m)(a . b) (distributividade nos inteiros) (m . (n+1))(a . b) = (m . n)(a . b) + m(a . b) (proposição 3.8, item b) (m . (n+1))(a . b) = (ma) . (nb) + m(a . b) (hipótese indutiva) (m . (n+1))(a . b) = (ma) . (nb) + (ma) . b (proposição 3.8, item e) (m . (n+1))(a . b) = (ma) . (nb + b) (distributividade no anel) (m . (n+1))(a . b) = (ma) . ((n+1)b) (proposição 3.8, item b). Agora, se n < 0, temos que -n > 0 e (m . n)(a .b) = ((-m) . (-n))(a . b) = ((-m)a) . ((-n)b) = (-(ma)) . (-(ma)) = (ma) . (ma). 3.24. a) O deslocamento dos n discos da origem para o destino pode ser realizado em três etapas: (1) deslocamento dos n - 1 primeiros da origem para a haste auxiliar; (2) deslocamento do maior disco da origem para o destino; (3) deslocamento dos n - 1 primeiros da haste auxiliar para o destino. Logo, an = an-1 + 1 + an-1 = 2 . an-1 + 1. c) Indução sobre n. i) Para n = 1, a1 = 1 = 21 - 1 e afirmação é verdadeira. ii) Suponhamos que an = 2n - 1 e provemos que an+1 = 2n+ 1 - 1. Isto é imediato pois, pelo item a, an+1 = 2 . an + 1 = 2 . (2n - 1) + 1 = 2n+1 - 1. Capítulo 4 4.1. x := x + y; y := x - y; x := x - y; 4.2. A idéia do algoritmo a seguir é colocar na posição 1 o menor dos elementos e em seguida ordenar os outros dois, utilizando o algoritmo Ordena dois números. Se os números dados forem armazenados nas variáveis a, b e c, para se colocar em a o menor dos elementos, só é necessário fazer alguma coisa se a for maior do que b ou for maior do que c. algoritmo Ordena três números leia(a, b, c); se a > b ou a > c então se b > c então a := a + c; c := a - c; a := a - c; senão a := a + b; b := a - b; a := a - b; se b > c então Introdução à Álgebra Abstrata (soluções dos exercícios) 15 b := b + c; c := b - c; b := b - c; 4.3. algoritmo Verifica quadrado perfeito leia(z); i := 1; repita enquanto i . i z e i < z i := i + 1; se i . i = z então escreva('o número dado é quadrado perfeito') senão escreva('o número dado não é quadrado perfeito') 4.4 algoritmo Maior de três números leia(a, b, c); se a > b e a > c então maior := a senão se b > c então maior := b senão maior := c; escreva(maior) Capítulo 5 5.1 a) Sejam q a b ' e q z a b ' ' . . Assim, a = b . q' e z . a = b . q". Além disto, z a b z q. . ' . Substituindo a = b . q' em z . a = b . q", temos z . b . q' = b . q" e, então, como b 0, z . q' = q". Daí, z a b z a b . . . b) Se q a b , então a = b . q e, assim, b a b b q a. . . 5.2. Para o quociente e o resto de um divisão a b, basta encontrar q e r tais que a = b . q + r, com 0 r < |r|. a) Como 7 = 0 . 12 + 7 e 0 7 < 12, temos q(7, 12) = 0 e r(7, 12) = 7. b) Como -25 = (-5) . 6 + 5 e 0 5 < 6, temos q(-25, 6) = -5 e r(-25, 5) = 5. c) Como 32 = (-5) . (-6) + 2 e 0 2 < |-6|, temos q(32, -6) = -5 e r(32, -6) = 2. d) Como -37 = 6 . (-7) + 5 e 0 5 < |-7|, temos q(-37, -7) = 6 e r(-37, -7) = 5 5.3 a) Devemos encontrar a = (-b) . q’ + r’, tal que 0 r’ < |b|. De a = b . q + r, 0 r < |b|, segue que a = (-b) . (-q) + r, 0 r < |b| e, portanto, q(a, -b) = -q e r(a, -b) = r. Introdução à Álgebra Abstrata (soluções dos exercícios) 16 b) De a = b . q + r, 0 r < |b|, segue que -a = (-b) . q - r, 0 r < |b| e, portanto, -a = (-b). q - r + b - b, de onde resulta -a = (-b ) . (q + 1) + (b - r), com 0 b - r < |b|. Daí, q(-a, -b) = q + 1 e r(-a, -b) = b - r. c) De a = b . q + r, 0 r < |b|, segue que -a = b . (-q) - r, 0 r < |b| e, portanto, -a = b . (-q) - r + b - b, de onde resulta -a = b . (-q - 1) + (b - r), com 0 b - r < |b|. Dai', q(-a, b) = -q - 1 e r(a, -b) = b - r. 5.4. De a = b . q + r, 0 r < |b| e a' = b . q' + r', 0 r' < |b|, segue que a + a' = b . (q + q') + (r + r'), com 0 r + r'< 2 . |b|. Se r + r' < |b|, q(a + a', b) = q + q' e r(a + a', b) = r + r'. Se |b| r + r' < 2 . |b| fazemos a + a' = b . (q + q') + (r + r') + b - b = b . (q + q' + 1) + (r + r' - b), o que mostra que, na hipótese acima, q(a + a', b) = q + q' + 1 e r(a + a', b) = r + r' - b. 5.5. A afirmação de que todo inteiro é da forma 2 . n ou da forma 2 . n + 1 segue imediatamente da divisão euclidiana: z = 2 . q + r, com 0 r < 2, e, portanto r = 0 ou r = 1. Para os itens a, b, c e d, sejam dois inteiros z e y. a) Se z = 2 . n e y = 2 . m, então z + y = 2 . (n + m), o que mostra que z + y é par. b) Se z = 2 . n + 1 e y = 2 . m + 1, então z + y = 2 . (n + m) + 2, o que mostra que z + y é par. c) Se z = 2 . n, então z . y = (2 . n) . y = 2 . (n . y), o que mostra que z . y é par. d) Se z = 2 . n + 1 e y = 2 . m + 1, então z . y = (2 . n + 1) . (2 . m + 1) = 4 . m . n + 2 . ( m + n) + 1, o que mostra que z . y é ímpar. 5.6 a) Se z é par z2 também é par e a soma de dois números pares é par. Se z é ímpar z2 também é ímpar e a soma de dois números ímpares é ímpar. b) Se z fosse ímpar, pelo item b anterior, z2 seria ímpar o que contrariaria a hipótese. Logo, z é par. 5.7 Se m e n são ímpares, então existem inteiros t e u tais que m = 2 . t + 1 e n = 2 . u + 1. Daí, m2 - n2 = = (4 . t2 + 4 . t + 1) - (4 . u2 + 4 . u +1) = 4 . (t2 + t) - 4 . (u2+ u). Agora, pelo exercício anterior, t2 + t e u2 + u são pares e, portanto, t2 + t = 2 . p e u2 + u = 2 . r, para p e r inteiros. Daí, m2 - n2 = 4 . (2 . p) - 4 . (2 . r) = = 8 . (p - r). 5.8 a) Seja q = q(m, a). Assim, m = a . q + r, com 0 r < a. Agora, se 1 q' q, então a . q' a . q e, portanto, a . q' a . q + r, o que implica a . q' m. Logo {1, 2, ..., q} A. Além disto, se q’ > q, então q’ A. De fato, se existisse q’ > q com q’ A, teríamos a . q’ m, com q’ > q, a . q’ a . q + r, com q’ > q, a . q’ < a . q + a (pois r < a), com q’ > q, a . q’ < a . (q + 1), com q’ > q, q’ < q + 1 (pois a 0), o que é um absurdo, pois esta última desigualdade gera q’ q, contrariando o fato q’ > q. Logo {1, 2, ..., q} = A e |A| = q. b) Sejam A = {z Z | 0 < z < m e a|z}, B = {z Z | 0 < z n e a|z} e C = {z Z | n < z < m e a|z}. Naturalmente, C = A - B e, como B A, |C| = |A| - |B|. Pelo item anterior, |B| = q(n, a). Para |A|, temos de analisar dois casos: se m não é múltiplo de a, A = {z Z | 0 < z m e a|z} e |A| = q(m, a); se a|m, A = {z Z | 0 < z m - 1 e a|z} e |A| = q(m - 1, a) = q(m, a) - 1. Logo, se m não é múltiplo de a, |C| = q(m, a) - q(n, a); caso contrário, |C| = q(m, a) - q(n, a) - 1. 5.9. a) Para n = 1, a afirmação é óbvia. Vamos mostrar, por indução sobre n, que an - bn = (a - b) . (an-1 + an-2 . b + ... + a . bn-2 + bn-1) para n 2. Para n = 2, a2 – b2 = (a - b) . (a + b) e a igualdade é verdadeira. Suponhamos que an - bn = (a - b) . (an-1 + an-2 . b + ... + a . bn-2 + bn-1) e provemos que an+1 - bn+1 = (a - b) . (an + an-1 . b + ... + a . bn-1 + bn). Multiplicando a hipótese de indução por a, temos an+1 = (a - b) . (an + an-1 . b + ... + a2 . bn-2 + a . bn-1) + bn . a e subtraindo bn+1, Introdução à Álgebra Abstrata (soluções dos exercícios) 17 an+1 – bn+1 = (a - b) . (an + an-1 . b + ... + a2 . bn-2 + a . bn-1) + bn . a – bn+1, que resulta em, an+1 – bn+1 = (a - b) . (an + an-1 . b + ... + a2 . bn-2 + a . bn-1) + bn . (a – b). Daí, an+1 – bn+1 = (a - b) . (an + an-1 . b + ... + a2 . bn-2 + a . bn-1 + bn). b) Para n = 1, a afirmação é óbvia. Como n é ímpar positivo, existe um inteiro positivo ou nulo k tal que n = 2 . k + 1. Vamos mostrar, por indução sobre k, que a2. k + 1 + b2 . k + 1 = (a + b) . (a2 . k - a2 . k - 1 . b + ... - a . b2 . k - 1 + b2 . k) para todo k 1. Para k = 1, a igualdade é trivialmente verdadeira. Suponhamos então que a2. k + 1 + b2 . k + 1 = (a + b) . (a2 . k - a2 . k - 1 . b + ... - a . b2 . k - 1 + b2 . k) e provemos que a2. (k + 1) + 1 + b2 . ( k + 1) + 1 = (a + b) . (a2 . (k + 1) - a2 . (k+1) - 1 . b + ... - a . b2 . (k + 1) - 1 + b2 . (k + 1)), isto é, provemos que a2. k + 3 + b2 . k + 3 = (a + b) . (a2 . k + 2 - a2 . k + 1 . b + ... - a . b2 . k + 1 + b2 . k + 2). Multiplicando a hipótese de indução por a2 e, em seguida, somando b2 . k + 3, temos a2. k + 3 + b2 . k + 3 = (a + b) . (a2 . k + 2 - a2 . k + 1 . b + ... - a3 . b2 . k - 1 + a2 . b2 . k) - a2 . b2 . k + 1 + b2 . k + 3, o que dá a2. k + 3 + b2 . k + 3 = (a + b) . (a2 . k + 2 - a2 . k + 1 . b + ... - a3 . b2 . k - 1 + a2 . b2 . k) + b2 . k + 1 . (b2 - a2). Daí, a2. k + 3 + b2 . k + 3 = (a + b) . (a2 . k + 2 - a2 . k + 1 . b + ... - a3 . b2 . k - 1 + a2 . b2 . k) + b2 . k + 1 . (b - a) . (b + a), de onde resulta a2. k + 3 + b2 . k + 3 = (a + b) . (a2 . k + 2 - a2 . k + 1 . b + ... - a3 . b2 . k - 1 + a2 . b2 . k + b2 . k + 2 - a . b2 . k + 1), que é a igualdade procurada. c) Como n é par positivo, existe um inteiro positivo k tal que n = 2 . k. Vamos mostrar, por indução sobre k, que a2. k - b2 . k = (a + b) . (a2 . k - 1 - a2 . k - 2 . b + ... +a . b2 . k - 2 - b2 . k - 1). Para k = 1, temos a2 - b2 = (a + b) . (a - b) que é uma igualdade verdadeira. Suponhamos que a2. k - b2 . k = (a + b) . (a2 . k - 1 - a2 . k - 2 . b + ... +a . b2 . k - 2 - b2 . k - 1) e provemos que a2. k + 2 - b2 . k + 2 = (a + b) . (a2 . k + 1 - a2 . k . b + ... +a . b2 . k - 2 - b2 . k + 1). Multiplicando a hipótese de indução por a2 e, em seguida subtraindo b2 . k + 2, temos a2. k + 2 - b2 . k + 2 = (a + b) . (a2 . k + 1 - a2 . k . b + ... +a . b2 . k - 2 - b2 . k + 1) + a2 . b2 . k - b2 . k + 2, que resulta em a2. k + 2 - b2 . k + 2 = (a + b) . (a2 . k + 1 - a2 . k . b + ... +a . b2 . k - 2 - b2 . k + 1) + (a + b) . (a - b) . b2 . k, que, aplicando a distributividade no sentido contrário, dá igualdade procurada. 5.10. Temos m = n . q + r e, portanto, m - r = n.q. Daí, 2 1 2 1 2 1 2 1 m r n n q n . é inteiro (item a do exercício anterior, com a = 2n e b = 1). Agora, aplicando o item b do exercício 5.0, 2 2 1 2 1 2 1 2 2 1 2 2r n m r n r m r m r. ( ) . . ( ) e portanto 2 1 2 2 1 2 1 2 1 2 1m r m r n n r . . . Resta mostrar que 0 2r - 1 < 2n - 1. A primeira desigualdade segue do fato de que r 0 e a segunda segue da aplicação do exercício 3.3, já que r < n. 5.11. Observação: Introdução à Álgebra Abstrata (soluções dos exercícios) 18 Observe que houve engano no enunciado ao não se exigir p 0. Indução sobre n. i) Para n = 1, p = 0 ou p = 1 e p! = 1. ii) Suponhamos que para todo 0 p < n, p! divide n . (n -1) . (n - 2) . ... . (n - p + 1) e provemos que para todo 0 p < n + 1, p! divide (n + 1) . n . (n -1) . (n - 2) . ... . (n - p + 2). Se p = n, como (n + 1) . n . (n -1) . ... . (n - p + 2) = (n + 1) . n!, temos que p! divide a expressão. Se p < n, basta observar que n + 1 = (n - p +1) + p, e, então, (n + 1) . n . (n -1) . ... . (n - p + 2) = (n - p + 1) . n . (n -1) . ... . (n - p + 2) + p . n . (n -1) . ... . (n - p + 2). Agora, p! divide estas duas parcelas: a primeira pela hipótese de indução e a segunda pelo fato de que, ainda pela hipótese de indução, (p - 1)! divide n . (n -1) . (n - 2) . ... . (n - p + 2) e p! = p . (p - 1)!. b) Temos que n! = n . (n -1) . (n - 2) . ... . (n - p + 1) . (n - p)! e a afirmação segue de imediato do item anterior. 5.12. É fácil provar que n i n i n i 1 1 1 , quaisquer que sejam os inteiros positivos n e i, com i n. Esta relação é conhecida como relação de Stifel e será usada na indução sobre n a seguir. Para n = 1, a afirmação é trivialmente verdadeira. Suponhamos então que ( ) . . . . . . . . . .a b a n a b n i a b b n n n n i i n 1 1 e provemos que ( ) . . ... . . ...a b a n a b n i a b bn n n n i i n 1 1 1 1 1 1 1 . Temos que (a + b)n+1 = (a + b) . (a + b)n = (a + b) . ( . . ... . . ... )a n a b n i a b bn n n i i n 1 1 e, portanto, ( ) ( . . . . ... . . . . ) ( . . . . ... . . . . a b a n a b n a b n n a b n n a b n a b n a b n n a b n n a b n n n n n n n n n 1 1 1 2 2 1 1 2 2 1 1 2 1 0 1 2 1 n nb 1 ). Daí, ( ) ( ) . . ( ) . . ... ( ) . . ( ) . . ), a b a n n a b n n a b n n n n a b n n n n a b b n n n n n n n 1 1 1 2 2 1 1 1 0 2 1 1 2 1 de onde, com a aplicação da relação de Stifel, resulta a expressão procurada. Introdução à Álgebra Abstrata (soluções dos exercícios) 19 5.13. Considerando que n n n0 1 , basta aplicar a fórmula do Binômio de Newton ( ) . . . . . . . . . .a b a n a b n i a b b n n n n i i n 1 1 , para o binômio (1 + 1)n. 5.14. Temos a5 = a . 10 + b e, assim, (a5)2 = (a . 10 + 5)2 = a2 . 100 + 100 . a + 25 = (a2 + a) . 100 + 25 = a . (a + 1) . 102 + 25 = a . (a + 1)25. 5.15. Devemos ter 54 = (105)b. Assim, 54 = 1 . b2 + 0 . b + 5, o que b2 - 49 = 0 e, portanto, b - 7 = 0 ou b + 7 = 0. Da primeira,b = 7 e da segunda, b = -7. Como b > 1, temos b = 7. 5.16. Deveríamos ter 24 = (108)b e, assim, 24 = 1 . b2 + 0 . b + 8, o que dá b2 - 16 = 0. Daí, b - 4 = 0 ou b + 4 = 0. Logo, b = 4. Porém, 8 não é um algarismo do sistema de numeração de base 4 e isto mostra que não existe base b tal que 24 = (108)b. 5.17. Seja z o maior inteiro que no sistema binário tem n dígitos. Assim z = (11...1)2, com n dígitos, e, portanto, z = 2n-1 + 2n-2 + ... + 2 + 1. Porém, pela solução do exercício 5.9, 2n - 1n = (2 - 1) . (2n-1 + 2n-2 + ... + 2 + 1) e, assim, z = 2n - 1. 5.18. Seja z = (anan-1...a1a0)3. Assim z = an . 3n + an-1 . 3n-1 + ... + a1 . 3 + a0 e, levando em conta as propriedades apresentadas no exercício 5.4, z é par se o número de parcelas de valor ímpar na expansão 3- ádica de z for par. Porém, considerando que 3i é ímpar qualquer que seja o inteiro positivo (ou nulo) i, a parcela ai 3i é ímpar se e somente se ai = 1. Logo z = (anan-1...a1a0)3 é par se e somente o número de dígito iguais a 1 o for. 5.19. Vamos provar que todo inteiro z escreve-se de modo único da forma z = 3 . s + t, com s {-1, 0, 1}. Pela divisão euclidiana, z = 3 . q + r, com r = 0 ou r = 1 ou r = 2. Se r = 0 ou r = 1, basta tomar s = q e t = r. Se z = 3 . q + 2, temos z = 3 . q + (-1) + 3 = 3 . (q + 1) – 1 e, então, basta tomar s = q + 1. Agora, com demonstração idêntica à demonstração do teorema 2.5, pode-se provar que qualquer inteiro z escreve-se da forma z = cn . 3n + cn-1 . 3n-1 + ... + c1 . 3 + c0, com c = -1 ou c = 0 ou c = 1. Assim, dada uma massa de z gramas, escrevemos z como acima e colocamos no prato da balança que contém a massa os pesos correspondentes aos coeficientes negativos e no outro prato os pesos correspondentes aos coeficientes positivos. Capítulo 6 6.1. a) Aplicando o lema 1.6 e as propriedades do máximo divisor comum, temos mdc(2 . n + 1, 3 . n +1) = mdc(2 . n + 1, (3 . n + 1) - 1 . (2 . n +1) = mdc(2 . n + 1, n) = mdc(n, (2 . n + 1) - 2 . n) = mdc(n, 1) = mdc(1, n - n . 1) = mdc(1, 0) = 1. b) Como no item anterior, mdc(n! + 1, (n + 1)! + 1) = mdc(n! + 1, (n + 1)! + 1 - (n + 1) . (n! + 1)) = mdc(n! + 1, -n) = mdc(n! + 1, n) = mdc(n, n! + 1 - n . (n - 1)!) = mdc(n, 1) = 1. 6.2. Pelo algoritmo de Euclides, temos 1 14 4 3 12 7 311 6 831 480 111 36 3 480 111 36 3 0 Assim, 3 = 111 - 3 . 36 = 111 - 3 . (480 - 4 . 111) = (-3) . 480 + 13. 111 e, portanto, 3 = (-3) . 480 + 13 . (6 831 - 14 . 480) = 13 . 6 831 -185 . 480. Substituindo, agora, o 480, 3 = 13 . 6 831 - 185 . (7 311 - 1 . 6 831) = (-185) . 7 311 + 198 . 6 831. Logo, os números procurados são m = 198 e n = -185. MAceio Destacar MAceio Destacar MAceio Destacar Introdução à Álgebra Abstrata (soluções dos exercícios) 20 6.3. Sejam d = mdc(a1, a2, ..., an), m = mdc(a1, a2) e k = mdc(m, a3, ..., an). Queremos mostrar que d = k. Da primeira temos que d|a1, d|a2, ..., d|an e se um inteiro d' é tal que d'|a1, d'|a2, ..., d'|an, então d' d e da segunda temos que k|m, k|a3, ..., k|an e se um inteiro k' é tal que k'|m, k'|a3, ..., k'|an, então k' k. Como m = mdc(a1, a2), por um lado, k|a1 e k|a2 e, e então k|a1, k|a2, ..., k|an o que mostra que k d. Por outro, como d|a1 e d|a2, d|m e, portanto, k|m, k|a3, ..., k|an o que mostra que d k. Por antissimetria da relação , temos d = k. 6.4. Sejam m z d e n y d . Assim, z = m . d e y = n . d. Como d = mdc(z, y), pelo algoritmo de Euclides, existem inteiros t e u tais que z . t + y . u = d e, então, por substituição de z e y, temos m . d . t + n . d . u = d. Assim, aplicando a lei do cancelamento, m . t + n . u = 1 e, portanto, pela proposição 6.2, mdc(m, n)|1. Logo mdc(m, n) = 1. 6.5. Sejam d = mdc(a . b, c) e k = mdc(b, c). Por um lado temos que k|b e k|c. Daí, k|(a . b), qualquer que seja a, e, portanto, pela definição de máximo divisor comum, k|d. Assim k d. Por outro lado, d|(a . b) e d|c. Se d = 1, existem inteiros t e u tais que (a . b) . t + c . u = 1 e, então, existem inteiros (a . t) e u tais que b . (a . t) + c . u = 1, o que mostra, como aplicação da proposição 6.2, que k = 1. Se d > 1, temos que, como a e c são primos entre si, d e a são primos entre si. Como d|(a . b), a proposição 6.1 garante que d|b. Assim d|b e d|c o que implica d|k e, portanto, d k. 6.6. Seja d = mdc(am, bn). Se d > 1, pela proposição 6.4, d tem um divisor primo p que, por conseqüência, também é divisor de am e de bn. Porem, como p é primo, a propriedade fundamental dos números primos (proposição 6.3) garante que p é divisor de a e de b, o que contraria a hipótese de que mdc(a, b) = 1. 6.7. Seja d = mdc(p, (p - 1)!). Então d|p e d|(p - 1)!. Da primeira, levando em conta que p é primo, segue que d = 1 ou d = p. Se d = p, a aplicação da proposição 6.3 a d|(p - 1)!, implica p|1 ou p|2 ou ... p|(p - 1) o que é um absurdo. Logo d = 1. 6.8. Houve um erro grave no enunciado da questão em não se estabelecer que o mínimo múltiplo comum de dois inteiros z e y é o menor inteiro positivo que é múltiplo de z e múltiplo de y. a) Sejam m = mmc(z, y) e d = mdc(z, y), t y d e u z d . Por um lado temos que de z|(z . t) e y|(u . y) segue que z t u y z y d . . . é múltiplo comum de z e y e, então, z y d m . . Por outro lado, de z z y m m y . . e de y z y m m z . . segue que z y m z . e z y m y . o que implica z y m d . . b) Seja m = mmc(z, y). Então, existem t e u tais que m = z . t e m = y . u. Observe inicialmente que mdc(t, u) = 1. De fato, se d = mdc(z, y) e d > 1, então existem inteiros t' e u' tais que t = d . t' e u = d . u'. Daí, m = z . d . t' e m = y . d . u', o que implica z . d . t' = y . d . u', portanto, z . t' = y . u'. Assim, m' = z . t' = y . u' é múltiplo de z e de t e m' < m, o que contraria o fato de que m é o mínimo múltiplo comum. Agora, seja a = z . r e a = y . s. Multiplicando a primeira por m = y . u e a segunda por m = z . t obtemos a . m = z . y . u . r e a . m = z . y . t . s que gera u . r = t . s. Daí, t|(u . r) e, pela proposição 6.1, considerando que mdc(t, u) =1, t|r. Logo existe um inteiro i tal que r = t . i. Agora, substituindo este valor em a = z . r temos a = z . t . i e, portanto, a = m . i e m|a. 6.9. Seja a equação a . x + b . y = c, com a, b > 0. Como se quer soluções positivas deve-se ter a . x > 0 e b . y > 0. Ora, pela propriedade arquimediana dos inteiros, proposição 3.5, existem inteiro x0 e y0 tais que a . x0 > c e b . y0 > c o que implica a . x0 + b . y0 > 2 . c > c. Dai', se (x, y) é solução da equação x < x0 e y < y0. Como queremos soluções positivas, x {1, 2, ..., x0} e y {1, 2, ..., y0} e estes conjuntos são finitos. 6.10. Pelo exercício 5.10, MAceio Destacar Introdução à Álgebra Abstrata (soluções dos exercícios) 21 a - 1 = (a - 1).q + a - 1, com m = n. t + r a - 1 = (a - 1).q + a - 1, com n = r . t + r a - 1 = (a - 1).q + a - 1, com r = r . t + r m n 1 r 1 1 n r 2 r 1 2 2 r r 3 r 1 2 2 3 1 1 2 1 2 3 . . . e, pelo algoritmo de Euclides, existe i tal que ri+1 = 0 e ri = d = mdc(m, n). Quando isto acontece a ri 1 1 0 , e então, novamente pelo algoritmo de Euclides, mdc(am - 1, an - 1) = ad - 1. 6.11. Suponhamos que p, p + 2 e p + 4 sejam primos e p 3. Então, pela divisão euclidiana, p = 3 . q + 1 ou p = 3 . q + 2. Na primeira hipótese, p + 2 = 3 . q + 3 e, então, 3|(p + 2). Na segunda, p + 4 = 3 . q + 6 e 3|(p + 4). Logo p = 3. 6.12. Observemos inicialmente que, se z = 4 . n + 1 e y = 4 . m +1, com m e n inteiros, então z . y = 4 . (4 . m . n + m + n) + 1, o que mostra que produto de inteiros da forma 4 . n + 1 também é da forma 4 . n + 1. Agora, suponhamos que pk é o maior primo da forma 4 . n + 3 e consideremos o número x = 4 . (7 . 11 . ... . pK) + 3, onde A = {3, 7, 11, ..., pk} é o conjunto de todos os primos da forma 4 . n + 3. Seja x q q qe e s es 1 21 2. . ... . a decomposição em fatores primos de x. Como x é da forma 4 . n + 3, existe i tal que qi é da forma 4 . n + 3, pois, do contrário, x seria, de acordo com a observaçãoacima, da forma 4 . n + 1. Se qi = 3, teríamos, pelas proposições 5.3 e 6.3, que qi divide 4 ou algum outro elemento de A, pois qi divide x. Mas isto seria um absurdo, pois o único divisor de 4 é 2 e os elementos de A são primos. Se qi A, pelas proposições citadas, qi|3, o que é também é um absurdo. Assim qi é um primo da forma 4 . n + 3 e não pertence a A o que é uma contradição, pois supomos que A era o conjunto de todos os primos da forma 4 . n + 3. Logo não existe o maior primo desta forma e A, na verdade, é infinito. 6.13. Seja f(x) = a . x2 + b . x + c, com a, b e c inteiros. Podemos supor que a > 0, pois do contrário, raciocinamos com a função -f(x). Se para todo inteiro m, f(m) é composto, a afirmação está verificada. Seja, então, m tal que f(m) = p, com p primo positivo, e considere um inteiro positivo h tal que (a . p) . h > -b - 2 . a . m (a proposição 10.3 garante a existência de h). Temos que f(m + p . h) = a . (m + p . h)2 + b . (m + p . h) + c, f(m + p . h) = (a . m2 + b . m + c) + p . (p . a . h2 + b . h + 2 . a . m . h), f(m + p . h) = p + p . (p . a . h2 + b . h + 2 . a . m . h), f(m + p . h) = p . (1 + p . a . h2 + b . h + 2 . a . m . h). Agora, como h > 0 e a . p . h + b + 2 . a . m > 0, temos a . p . h2 + b . h + 2 . a . m . h > 0, 1 + a . p . h2 + b . h + 2 . a . m . h > 1 e, portanto, f(m + p . h) é composto. 6.14. Vamos supor que n > m. Isto é, vamos supor que n = m + x, com x > 0. Como 2 1 2 1 2 12 2 21n n n . , temos que 2 1 2 1 2 1 2 1 2 1 2 1 2 1 2 1 2 1 2 1 2 1 2 2 2 2 2 2 2 2 2 2 2 1 1 1 2 2 1 2 2 m x m x m x m x m x m x m x m x m x m m . . . ... . . . ... . . , Introdução à Álgebra Abstrata (soluções dos exercícios) 22 e, portanto, 2 12 m é divisor de 2 12 n . Daí, existe um inteiro q tal que 2 12 n = 2 12m q . e, então, 2 1 2 1 22 2n m q . . Assim, se d = mdc(Fn, Fm), então d|2 o que implica d = 2 ou d = 1. Como cada Fn é ímpar, d = 1. Do fato de que mdc(Fn, Fm) = 1, segue que dois números de Fermat quaisquer não possuem um fator primo comum. Como, evidentemente, é infinito o conjunto dos números de Fermat, o conjuntos dos números primos tem que ser infinito para que cada um deles, pelo menos, seja fator de um número de Fermat. 6.15 Como 32 + 42 = 52, temos que para todo inteiro positivo n, 32 . n2 + 42 . n2 = 52 . n2 e, portanto, (3 . n)2 + (4 . n)2 = (5 . n)2, o que mostra que (3 . n, 4 . n, 5 . n) é um trio pitagórico, qualquer que seja o inteiro positivo m. Capítulo 7 7.1. Basta levar em conta que a relação "a e b possuem o mesmo número de divisores é de equivalência". 7.2 Considere o seguinte contra-exemplo: 18 12 , pois 18 e 12 possuem dois divisores primos 2 e 3 7 11 , pois 7 e 11 são primos enquanto que 25 33 , pois 25 tem um divisor primo, 5, e 33 tem dois divisores primos, 3 e 11. 7.3. Sejam d1 = mdc(i, n) e d2 = mdc(j, n). De i j segue que n|(i - j) e, então i - j = n . q, para algum inteiro q. Daí, como d1|i e d1|n, temos que d1|j e, portanto, d1 é divisor comum de j e n. como d2 é o maior divisor comum de j e n temos que d1 d2. Com raciocínio idêntico, mostra-se que d2 d1. 7.4. Tome n = 6 e a = 5. Temos mdc( 5, 6) = 1 e 56 -1 = 55 = 3125 5 mod 6. 7.5. Como pelo Pequeno Teorema de Fermat, ai . ap-i-1 = ap-1 1 mod p, temos que a ai p i 1 1 . 7.6. Temos que 102 0 mod 4 e, portanto, 10i 0 mod 4, para todo i 2. Sabemos que, se a = anan-1...a1a0, então a = an . 10n + an-1 . 10n-1 + ... + a2 . 102 + a1 . 10 + a0. Assim a 0 mod 4 se e somente se (a1 . 10 + a0) mod 4. 7.7. Pelo critério de divisibilidade por nove, temos que se a = anan-1...a1a0, então a (an + an-1 + ... +a1 + a0) mod 9. Daí, 9|( a - (an + an-1 + ... +a1 + a0)). 7.8. a) Como p é primo e 13 também é primo, pelo Pequeno Teorema de Fermat, 13p-1 1 mod p. Logo r(13p-1, p) = 1. b) Pelo Pequeno Teorema de Fermat, 211-1 1 mod 11 e, então, 210 1 mod 11. Por potenciação de congruências, 2100 1 mod 11 e, por conseguinte, r(2100, 11) = 1. c) Pelo Pequeno Teorema de Fermat, temos 710 1 mod 11 e, então, 71000 1 mod 11. Multiplicando por 7, 71001 7 mod 11 e, portanto, r(71001, 11) = 7. Introdução à Álgebra Abstrata (soluções dos exercícios) 23 d) Temos 56 1 mod 7 e, portanto, 518 1 mod 7. Como 52 4 mod 7, temos que, multiplicando as duas congruências, 520 4 mod 7 e r(520, 7) = 4. e) Temos 430 = 418 . 412 412 mod 19, pois 18 = 19 - 1, 19 é primo e mdc(4, 19) = 1, o que garante que 418 1 mod 19. Agora, 49 = 218 1 mod 19 e 42 (-3) mod 19 e, assim, 412 = 49 . 42 . 4 (-12) mod 19 7 mod 19. Logo r(430, 19) = 7. f) Temos que 6 (-1) mod 7 e, então, 611 (-1) mod 7. Como 9 2 mod 7, temos, por multiplicação, 9 . 611 (-2) mod 7 5 mod 7 e, por conseguinte, o resto procurado é 5. 7.11. Temos 24 (-1) mod 17 e, portanto, 28 1 mod 17. Por outro lado, para 4 < i < 8, 2i = 24 . 2i-4 (-2i-4) mod 17 (17 - 2i-4) mod 17 e 17 - 2i-4 > 1. Logo i = 8. 7.10. Vamos realizar uma indução sobre n i) Para n = 1, temos que 15 = 1 1 mod 10. ii) Suponhamos que n5 n mod 10 e provemos que (n + 1)5 (n + 1) mod 10. Temos, pela fórmula do Binômio de Newton (n + 1)5 = n5 + 5 . n4 + 10 . n3 + 10 . n2 + 5 . n + 1 o que implica (n + 1)5 - 1 = n5 + 5 . (n4 + n) + 10 . (n3 + n2). Porém, n5 n mod 10 (pela hipótese de indução) 5 . (n4 + n) 0 mod 10 (n4 + n sempre é par) 10 . (n3 + n2) 0 mod 10 (evidente), e somando estas congruências, temos (n + 1)5 - 1 n mod 10, o que implica o que queríamos. 7.11. Se n é par, então n = 2 . k, para algum inteiro k, e, portanto, n2 = 4 . k2. Assim, 4|n . Se n é ímpar, n = 2 . k + 1, para algum inteiro k, e, portanto, n2 = 4 . k2 + 4 . k + 1 = 4. (k2 + 1) + 1. Assim, r(n2, 4) = 1. 7.12. Como p é primo, mdc(i, p) = 1, para todos i = 1, 2, ..., p-1. Daí, pela proposição 7.7, 1 2 1, , . . . , p são inversíveis em Zp. Do fato de que 1 11 e p 1 1 , o que implica p p 1 11 , segue que no conjunto 2 3 2, , . . . , p estão os inversos destes próprios elementos. Assim, 1 2 2 1 1 1 1. . . . . . .p p p e, portanto, ( )!p 1 1 e (p - 1)! (-1) mod p. 7.13. Como n é composto, pela proposição 5.6, n = p . y, com p primo e 2 y < n. Se y p, p e y são fatores de (n - 1)! e isto garante que n | (n - 1)!. Se y = p e n > 4, temos p > 2 o que implica 2 . p < p . p, ou seja, 2 . p < n. Assim, p e 2 . p são fatores de (n - 1)! e, como n = p . p, mais uma vez, n | (n - 1)!. Observe que este exercício mostra que a primalidade de p é indispensável para o teorema de Wilson. 7.14. Seja d = mdc(u, v). Então pelo algoritmo de Euclides, existem inteiros x e y tais que u . x + v . y = d. Agora, de au 1 mod n segue, pela proposição 7.3, au . x 1x mod n e de av 1 mod n segue, pela mesma Introdução à Álgebra Abstrata (soluções dos exercícios) 24 proposição, av . y 1y mod n. Daí, aplicando o item b da proposição citada, au . x . av . y = 1 . 1 mod n e, então, au . x + y . v 1 mod n. 7.15. Pelo modelo equiprobabilístico de probabilidade, basta determinar o número de elementos não inversíveis de Zn. Se este número for indicado por x, a probabilidade procurada é x n . Naturalmente, x = n - (n) = n - (p . q) = n - (p - 1) . (q - 1), onde esta última igualdade foi obtida através das aplicações sucessivas das proposições 7.10 e 7.8. Assim, x = n - p . q + p + q - 1 e então, como n = p . q, x = p + q - 1. Daí, a probabilidade pedida é p q n p q p q q p p q 1 1 1 1 1 . . . 7.16. a) De 5 . x + 7 10 mod 15 segue que 15 | (5 . x + 7 - 10) e, portanto, existe um inteiro t tal que 5 . x - 3 = 15 . t. Daí, 5 . x - 15 . t = 3. Como mdc(5, 15) = 5, pois 5 | 15, e 5 não divide 3, a proposição 7.8 garante que a congruência não tem solução. b) De 3 . x - 4 0 mod 4 segue que 4 | (3 . x - 4) e, portanto, existe um inteiro t tal que 3 . x - 4 = 4 . t o que implica 3 . x+ 4 . t = 4. Como 1 = 4 - 3 . 1, temos que 4 = 3 . (-4) + 4 . 4 e, então, x = -4 é uma solução da congruência dada. 7.17. Temos que 19 2 mod 17 e, portanto, 194 24 mod 17. Como 24 = 16 e 16 (-1) mod 17, temos que 194 (-1) mod 17. Daí, (194)2 (-1)2 mod 17 e, então, para todo inteiro positivo n, 198 . n 1 mod 17. 7.18. Naturalmente, o algarismo das unidades de um inteiro n igual ao resto da divisão de n por 10. Como 32 = 9 (-1) mod 10, (32)61 (-1)61 mod 10 (-1) mod 10. Como (-1) 9 mod 10, temos que 3122 9 mod 10 e o algarismo das unidades de 3122 é 9. 7.19. Observação: Houve um pequeno engano no enunciado da questão. Na verdade da forma em que está enunciada a questão não tem solução. Destacando o engano do enunciado, este seria: Determine o menor inteiro positivo múltiplo de nove ... . Precisamos resolver o sistema x 1 mod 2 x 1 mod 5 x 1 mod 7 e depois considerar que x deve ser múltiplo de 9. Da primeira congruência, temos x = 2 . t + 1, para algum inteiro t, e, substituindo este valor na segunda, obtemos 2 . t + 1 1 mod 5 e, portanto, 2 . t 0 mod 5. Como mdc(2, 5), pela proposição 7.4, t 0 mod 5 e, portanto, t = 5 . u, para algum inteiro u. Substituindo t em x = 2 . t + 1, obtemos x = 10 . u + 1. Agora, substituindo x na terceira congruência, 10 . u + 1 1 mod 7, de onde resulta 10 . u 0 mod 7. Mais uma vez pela proposição 7.4, como mdc(10, 7) = 1, obtemos u 0 mod 7 e, então, u = 7 . v, para algum inteiro v. Segue então, substituindo u em x = 10 . u + 1, que x = 70 . v + 1. Como x deve ser múltiplo de nove, existe y tal que x = 9 . y, e chegamos a equação diofantina 9 . y - 70 . v = 1. Para resolvê-la, temos, aplicando o algoritmo de Euclides 7 1 2 70 9 7 2 7 2 1 e, portanto, 1 = 7 - 3 .2 = 7 - 3 . (9 - 1 . 7) = (-3) . 9 + 4 . 7 = (-3 . 9) + 4 . (70 - 7 . 9) = (-31) . 9 + 4 . 70. Introdução à Álgebra Abstrata (soluções dos exercícios) 25 Daí, y = -31. Como para este valor de y, x é negativo, consideramos em Z70, y 70 31 39 e, assim, x = 9 . 39 = 351. 7.20. Precisamos resolver o sistema x 2 mod 3 x 3 mod 5 x 4 mod 7 Da primeira congruência, x = 3 . t + 2, para algum inteiro t e, substituindo este valor na segunda, 3 . t + 2 3 mod 5 o que dá 3 . t 1 mod 5. Como, em Z5, 3 2 , temos t 2 mod 5. Daí, t = 5 . u + 2, para algum inteiro u. Substituindo t em x = 3 . t + 2, obtemos x = 15 . u + 8. Assim, a terceira congruência fica 15 . u + 8 4 mod 7 que se transforma em 15 . u (-4) mod 7 ou 15 . u 3 mod 7. Como, em Z7, 15 1 , obtemos u 3 mod 7. Daí, u = 7 . v + 3, para algum inteiro v, cuja substituição em x = 15 . u + 8 gera a equação x = 105 . v + 53. Como queremos o menor inteiro positivo, tomamos v = 0 e, assim, x = 53. 7.21 a) Como 625 = 54, pela proposição 7.9, (54) = 4 . 53 = 500. b) (8!) = (2 . 3 . 22 . 5 . (2. 3) . 7 . 23) = 1 . 2 . 2 . 4 . (1 . 2) . 6 . 4 = 768 c) Como 5 900 = 22 . 52 . 59, temos, pelo corolário 4.7, (5 900) = 22 - 1 . 52 - 1 . (2 - 1) . (5 - 1) . (59 - 1) = 2 320. 7.22. a) Como 10 = 11 - 1 e 11 é primo, temos, pela proposição 8.7, n = 11. b) Seja n = p pe k ek 1 1 . ... . a decomposição de n em fatores primos. Assim, pelo corolário 4.7, p p p pe k e k e 1 1 1 1 1 1 1 14 . ... . . ( ) . ... . ( ) e, como 14 = 2 . 7, devemos ter p1 = 2, e1 = 2 e existir algum inteiro positivo i tal que pr = 7 e er = 2. Mas, deste modo, necessitamos do fator 7 - 1 = 6. Logo, não existe n tal que (n) = 14. 7.23. Como m|n, se a decomposição em fatores primos de m for m = p pe k ek 1 1 . ... . , então a decomposição em fatores primos de n será da forma n = ( ) . ... . ( ) . . ... .p p p pe f k e f k e r ek k k r 1 1 1 1 1 . Assim, pelo corolário 4.7, m . n = p p p pe f e k e f e k e r ek k k k r 1 1 1 1 1 1. .. ... . . . ... . (m . n) = p p p p p pe f e k e f e k e r e r k k k k r 1 1 1 1 1 1 1 1 1 1 1 1 1. .. ... . . . ... . . ( ) . ... . ( ) ou (m . n) = p p p p p pe e f k e k e f r k k k 1 1 1 1 1 1 1 1 1 1. . ... . . . ( ) . ... . ( ). . ou, ainda, (m . n) = ( . ... . ) . ( . ... . . ( ) . ... . ( )). .p p p p p pe k e e f k e f r k k k 1 1 1 1 1 1 1 1 1 1 que dá (m . n) = m . (n). MAceio Destacar Introdução à Álgebra Abstrata (soluções dos exercícios) 26 Capítulo 9 9.1. a) De a b c d segue que a . d = b . c. Daí, a . d + b . d = b . c + b . d e, portanto, (a + b) . d = b . ( c + d), o que implica a b b c d d . b) De a b c d segue que a . d = b . c. Daí, 2 . a . d = 2 . b . c e, portanto, a . d - b . c = = -a . d + b . c. Assim, a . d - b . c + a . c - b . d = -a . d + b . c + a . c - b . d, o que implica (a - b) . (c + d) = = (a + b) . (c - d). Dai', a b b d c d c d . c) De a b c d segue que a . d = b . c. Daí, a . d - b . d = b . c - b . d e, portanto, (a - b) . d = (c - d) . b, o que implica a b b c d d . d) De a b c d segue que a . d = b . c. Daí, a . d + c . d = b . c + c . d e, portanto, (a + c) . d = (b + d) . c, o que implica a c b d c d . e) De a b c d segue que a . d = b . c. Daí, a . d = c . b e, portanto, a c b d . 9.2. Seja z = p pe k ek 1 1 . ... . a decomposição do inteiro z em fatores primos. Como a equação x2 - z = 0 não tem solução em Z existe um inteiro i tal que ei é ímpar. Seja então z = p p pe i e k ei k 1 1 . ... . . ... . . Agora, suponhamos que a equação x2 - z = 0 tem solução em Q. Assim, existem inteiros a e b, com mdc(a, b) = 1, tais que a b z 2 2 . Daí, a2 = z . b2 e, como pi|z, pi|a2. Segue então da proposição 6.3, que pi|a. Assim a = pi . x1, para algum inteiro x1 e, portanto, ( . ) ( . ... . . ... . ) .p x p p p bi e i e k ei k 1 2 1 21 , o que implica ( ) ( . ... . . ... . ) .x p p p be i e k ei k 1 2 1 2 21 . Logo, pi|(x1)2 e, então, pi|x1. Portanto, x1 = pi . x2, para algum inteiro x2, e, assim, ( . ) ( . ... . . ... . ) .p x p p p bi e i e k ei k 2 2 1 2 21 , o que implica ( ) ( . ... . . ... . ) .x p p p be i e k ei k 2 2 1 4 21 . Continuando este raciocínio, obteremos ( ) ( . ... . . ... . ) .x p p p be e i k e i k 1 2 1 21 . Daí, p xi ei| ( )1 2 , o que implica p xi ei| 1 . Logo, x p xe i ei i 1 . , para algum inteiro xei , e, então, ( . ) ( . ... . . ... . ) .p x p p p bi e e i k e i k2 1 21 , que gera p x p p bi e e k e i k. ( ) ( . ... . ) .2 1 21 . Assim, pi|b2 e, por conseguinte, pi|b. Mas isto é uma contradição, pois supomos mdc(a, b) = 1 e obtivemos pi|a e pi|b, com pi primo. 9.3. De a b a b ' ' segue que a . b' a' . b. Daí, aplicando a compatibilidade com a multiplicação da relação de ordem em Z e considerando que d2 > 0, a . b' . d2 a' . b . d2. Agora, aplicando a compatibilidade com a adição em Z, a . b' . d2 + b . c . b' . d a' . b . d2 + b . c . b' . d. Assim, pela distributividade em Z, Introdução à Álgebra Abstrata (soluções dos exercícios) 27 (a . d + b . c) . (b' . d) (a' . d + b' . c) . (b . d) e, por conseginte, a d b c b d a d b c b d . . ' . ' . ' . . Daí, a b c d a b c d ' ' , como queríamos. 9.4. Sejam a p q e b p q ' ' . Temos que a > b > 0 se e somente se p . q' > p' . q > 0 se e somente se q p q p ' ' 0 se e somente se b-1 > a-1 > 0. 9.5. Seja D um domínio de integridade finito. Precisamos mostrar que se a D e a 0, então a é inversível. Seja, então, a D com a 0 e considere a função de D em D definida por fa(x) = a . x. Pelo item c do exercício 2.9, fa é injetora e, como D é finito, o corolário 3.6 garante que fa é sobrejetora. Assim, existe x0 D tal que fa(x0) = 1, o que dá que existe x0 D tal que a . x0 = 1 e, portanto, a é inversível. 9.6. Seja r r r 1 2 2 . Temos que r r r r r r r r r r 1 1 2 1 1 2 1 2 1 2 2 2 2 0 . , sendo esta última desigualdade decorrente de r r1 2 . Daí, r r 1 . Do mesmo modo, r r r r r r r 2 2 1 2 2 1 2 2 0 , o que mostra que r r 2 . 9.7. Suponhamos que Stem um elemento mínimo e. Assim, e > 0 e, então, pelo exercício anterior, 0 2 e e . Daí, e não é elemento mínimo de S. Jaime Evaristo Eduardo Perdigão Introdução à Álgebra Abstrata Manual de Soluções Apresentação Capítulo 3 Capítulo 4 Capítulo 5 Capítulo 6 Capítulo 7 Capítulo 9
Compartilhar