Exerćıcios de Algebra I

Semana I.

Exercicios 1 até 17 do Capitulo 1 do Milies/Coelho.

Exerćıcio 1. Dar uma ordem em Z tal que Z é bem ordenado.

Semana II. Milies/Coelho: exercicios 1 até 7, pag 30; ex 10 pag 33, ex 12, 13, 14, pag 35.

Exerćıcio 2. Seja A Ď Z e seja ´A :“ t´a | a P Au. Supomos que m P Z é um mı́nimo para A (ou seja queque m P Z verifica 1) m P A, 2) m ď a,@a P A). Provar que ´m é um máximo para ´A, ou seja, satisfaz àscondições de máximo para ´A ou seja 1) ´m P ´A, 2) ´m ě ´a @a P A. Viceversa, se M é um máximopara A, provar que ´M é um mı́nimo para ´A.

Exerćıcio 3. Sejam a, b P Z, os dois inverśıveis multiplicativamente. Sem usar que UpZ, ¨q “ t1,´1u,e só usando a definição, provar que ab é inverśıvel multiplicativamente. Generalizar ao caso de um anel

comutativo e não comutativo1

Exerćıcio 4. Prove por indução:

1. 1` 3` 5` ¨ ¨ ¨ ` p2n´ 1q “ n2,@n ě 1.

2. 1` 2` 3` ¨ ¨ ¨ ` n “ npn`1q2 ,@n ě 1 (Números triangulares).

3. 1` 2` 22 ` ¨ ¨ ¨ ` 2n´1 “ 2n ´ 1,@n ě 1.

4. 12 ` 22 ` 32 ` ¨ ¨ ¨ ` n2 “ 16 p2n3 ` 3n2 ` nq,@n ě 1 (Números piramidais).

5. 13 ` 23 ` 33 ` ¨ ¨ ¨ ` n3 “ 14n2pn` 1q2,@n ě 1.

6. 1 ¨ 2` 2 ¨ 3` 3 ¨ 4` ¨ ¨ ¨ ` n ¨ pn` 1q “ 13npn` 1qpn` 2q,@n ě 1.

7. 2` 6` 18` ...` 2 ¨ 3n “ 3n`1 ´ 1,@n P N.

8. 12! `23! `

34! ` ¨ ¨ ¨ `

npn`1q! “ 1´

1pn`1q! ,@n ě 1.

9. 1 ¨ 1!` 2 ¨ 2!` 3 ¨ 3!` ¨ ¨ ¨ ` n ¨ n! “ pn` 1q!´ 1,@n ě 1.

10. n ă 2n,@n P N. (Dica: comece a recursão de 1, e trate n “ 0 a parte.)

11. 2n ă n!,@n ě 4.

12. 2n3 ą 3n2 ` 3n` 1 para todo n ě 3

13. 7n ` 2 é divis̀Ivel por 3,@n P N.

1No caso de um anel não comutativo, a inverśıvel multiplicativamente se e somente se existe b tal que ab “ ba “ 1.

1

14. n2 ą n` 1,@n ą 1.

15. p1` xqn ě 1` nx,@x ą 0,@n P N (Desigualdade de Bernoulli).

16. Seja Hpnq “ 1` 12 `13 `¨ ¨ ¨`

1n . Prove que: Hp2nq ě 1`

n2 ,@n ě 3. (Divergência da série harmônica).

17. Prove que @n ą 0,˜

nÿ

k“1k

¸2

“nÿ

k“1k3.

18. Provar por indução que, para todo n P N, 52n`1 ` 1 é multiplo de 6.

19. Provar que a soma dos angulos internos de um poligono convexo de n lados é 2πpn´ 2q.

Exerćıcio 5. Seja a proposição

@n ě 1, 1` 2` . . .` n “ 12

ˆ

n` 12

˙2

.

A proposição é falsa, porém Joãozinho deu a seguinte demonstração por indução dela:

Supomos por indução que a propriedade é verdadeira para n ě 1, e vamos deduzir que é verdadeira paran` 1:

1` 2` . . .` n` pn` 1q “`

1` 2` . . .` n˘

` pn` 1q

“ 12

ˆ

n` 12

˙2

` pn` 1q (por hipótese de indução)

“ 12

ˆˆ

n2 ` n` 14

˙

` p2n` 2q˙

“ 12

˜

ˆ

n` 1` 12

˙2

´ 3n´ 94` n` 1

4` p2n` 2q

¸

“ 12

ˆ

pn` 1q ` 12

˙2

.

Conclúımos por indução.

Explique ao Joãozinho o erro que ele cometeu (a questão NÃO É explicar porque a proposição é falsa,

mas qual é o erro da demonstração). Provar que P pnq não é verdadeira para nenhum n.

Exerćıcio 6. Dado o predicado P pnq : 1` 2` ¨ ¨ ¨ ` n “ npn`1q2 ` 1, definido em N˚, provar que

1. Para todo n P N˚, Se P pnq é verdadeiro, então P pn` 1q é verdadeiro.

2. P pnq não é verdadeira para nenhum n P N˚.

Exerćıcio 7. Seja e o número de Nepero (2.7 ă e ă 2.8). Joãozinho quer demonstrar que,

@n P N n2 ě 6n´ 8` e´n .

Joãozinho faz a sua demonstração por indução, da forma seguinte.

Caso base. n “ 0. Temos02 “ 0 ě ´7 “ 6 ¨ 0´ 8` e0 .

2

Então a formula val por n “ 0.Passo indut́ıvo. Supomos que a fórmula valha por um certo n0 arbitrario, ou seja, que por um certo n0

arbitrario, n0 P N, temosn20 ě 6n0 ´ 8` e´n0 .

Então

pn0 ` 1q2 “ n20 ` 2n0 ` 1 desenvolvendo

ě 6n0 ´ 8` e´n0 ` 2n0 ` 1 por hipótese indut́ıva

“ 6n0 ` 6´ 6´ 8` e´n0 ` 2n0 ` 1 somando e subtraendo 6

“ 6pn0 ` 1q ´ 8` 2n0 ´ 5` e´n0 pondo a fator o 6 e somando o ´6 e 1

ě 6pn0 ` 1q ´ 8` e´n0 porquê 2n0 ´ 5 é positivo por n0 genérico

ě 6pn0 ` 1q ´ 8` e´pn0`1q porquê a função e´x è decrescente.

Isto mostra o passo indut́ıvo. Então a fórmula esta mostrada por indução por cada n P N.

1. Encontrar o conjunto de verdade do predicado P pnq : n2 ě 6n´ 8` e´n no universo Z.

2. Dizer se a demonstração do Joãozinho è correta ou não. Em caso não seja correta, encontrar o erro.

Motivar adequadamente.

3. È possivel corrigir o enunciado do Joãozinho, e demonstrar o enunciado correto por indução? Se sim,

corrigir e demonstrar por indução.

Exerćıcio 8. Provamos agora, por indução matemática, que todos os inteiros não negativos são iguais. Se

P pnq é o predicado 0 “ 1 “ ¨ ¨ ¨ “ n´ 1 “ n, é suficiente mostrar a afirmação p@n P NqpP pnqq.Caso base n “ 0, P p0q é verdadeira, porquê 0 “ 0.Passo indut́ıvo. Supomos P pnq verdadeira por um certo n fixado. Então 0 “ 1 “ ¨ ¨ ¨ “ n ´ 1 “ n. Masentão n ´ 1 “ n. Mas somando 1 aos dois lados, obtemos n “ n ` 1. Mas então 0 “ 1 “ ¨ ¨ ¨ “ n “ n ` 1.Ou seja, mostramos P pn` 1q.Por indução então demostramos que P pnq é sempre verdadeira e todos os inteiros são iguais.

O que esta errado nesta demonstração?

Exerćıcio 9. 1. Provar o seguinte

Teorema. [Principio de Indução Matemática Descendente] Seja s P Z e seja P pnq um predicado definido emZďs “ tn P Z |n ď su. Supomos que

• P psq seja verdadeira;

• Para todo n P Zďs, se P pnq é verdadeira, então P pn´ 1q é verdadeira.

Provar que P pnq é verdadeira para todo n P Z, n ď s.2. Reformular o prinçipio em termo de um conjunto S Ď Zďs.

Semana III

Exerćıcio 10. Provar a seguinte variante do Prinćıpio de Indução Forte. [Principio de Indução Forte,

Variante]Seja c P Z. Seja P pnq um predicado ”definido”sobre Zěc. Seja d P Zěc e supomos que

3

• Se k P Z com c ď k ď d então P pkq “ V ;

• p@n ě dqrpP pcq “ V q ^ ¨ ¨ ¨ ^ pP pnq “ V q - P pn` 1qs

Então p@n ě cqpP pnq “ V q.

Exerćıcio 11. Consideramos um tabuleiro de xadrez 2 ˆ 2. Um triomino é a peça que se obtem tirandouma casa do tabuleiro 2 ˆ 2. Provar que, por cada n ě 1, um tabuleiro 2n ˆ 2n, ao qual for tirada umaqualquer casa, se pode pre-encher de triominos.

Exerćıcio 12. Sejam2 a, b P R, com |a| ą 1. Consideramos a sequencia, definida por recursão:

a0 “ a

an`1 “ a ¨ an ` b @n ě 0

• Provar que|an| ď |a|n`1pn|b| ` 1q @n ě 0 .

• Encontrar uma fórmula fechada para an e prova-la por indução.

Exerćıcio 13. Seja an a sequencia definida por recursão

a0 “ 1

a1 “ 2

a2 “ 4

an`1 “ an ` an´1 ` an´2 @n ě 2

• Provar que an ď 2n por cada n.

Supomos agora que a0 “ 1, a1 “ 1, a2 “ 3, e que val a mesma recursão an`1 “ an ` an´1 ` an´2, por cadan ě 2. Provar que existe α P Q, com 0 ă α ň 2 tal que an ď αn por cada n ě 0.

Exerćıcio 14. Encontrar todos os valores que podem ser pagos com notas de vinte reais e de cinquenta

reais (sem receber troco). Justificar matematicamente a resposta.

Exerćıcio 15. Consideramos a função f : N - Z definida por recursão3

fp0q “ 1

@n ě 0, fpn` 1q “#

fpkq ` 2fpk ´ 1q se n` 1 “ 2k, Dk P N;fp2kq ´ 1 se n` 1 “ 2k ` 1, Dk P N

• Provar por que, por cada n ě 0fpnq ď 2n .

• Provar, de fato, quefpnq ď p3

2qn ` 1

2assumimos que o estudante tenha uma mı́nima familiaridade com os números reais; se não, usar racionais. Usar as

disugualdades do valor absoluto3Não é o teorema de recursão que enunciamos em sala: tentar de dar um enunciado de um teorema de recursão que funcione

para este caso: isto vai ser mais facil quando falarmos formalmente de relações e funções

4

• Provar que, por todo n P N,fpnq ě n

2´ 1 .

Semanas IV-V,

Milies/Coelho: Seção 2.1 (Divisão Euclidiana): Exercicios 1 - 20;

Seção 2.2 (Numeração): Exercicios 1 - 14;

Seção 2.3 (Mcd): Exerćıcios: 1,2.

Exerćıcio 16. Seja I um ideal de Z. Provar que I “ Z se e somente se 1 P Z ou ´1 P Z.

Exerćıcio 17. Sejam I1, I2 dois ideais de Z. Provar que I1 X I2 é um ideal de Z. Em geral, provar que seI1, . . . , In são n ideais de Z, provar que I1 X ¨ ¨ ¨ X In é um ideal de Z. Quem é 6ZX 14Z?

Exerćıcio 18. Sejam I, J ideais de Z. Definimos IJ o subconjunto de Z de todas as somas finitasř

k ikjk,

onde ik P I, jk P J . Provar que IJ é um ideal de Z. Provar que IJ Ď I X J . É sempre verdadeiro queIJ “ I X J?

Exerćıcio 19. Sejam I, J ideais de Z. Definimos ĂIJ o subconjunto de Z definidos como

ĂIJ “ tij | i P I, j P Ju.

É ĂIJ um ideal de Z? Se sim, coincide com algum outro ideal já visto?

Exerćıcio 20. Provar que por cada n P N˚ existem m P N, α1, . . . , αm P N tais que

• n “řmk“1 αk ¨ k!

• 0 ď αk ă k ` 1

• αm ‰ 0

Semanas VI-VII. Milies/Coelho: Seção 2.3: exerćıcios 3, 4, 5 - 10, exerćıcios 11 - 17.

Seção 2.4: exerćıcios 1 - 5.

Seção 2.5: exerćıcios 1 - 6

Seção 2.6: exerćıcios 1 - 4, exerćıcios 5 - 10.

Exerćıcio 21. A sequencia de Fibonacci Fn é definida recursivamente por F0 “ 0, F1 “ 1, e por n ě 1,temos

Fn`1 “ Fn ` Fn´1 .

Mostre que quaisquer dois elementos consecutivos Fn e Fn`1 na sequência de Fibonacci são primos entre si.

Exerćıcio 22. Os números de Fermat são definidos por Fn “ 22n ` 1, isto é, F0 “ 3, F1 “ 5, F2 “ 17,. . .

1. Prove que Fn`1 “ 2` F0F1 ¨ ¨ ¨Fn.

2. Mostre que quaisquer dois números de Fermat distintos são primos entre si.

Nota histórica: Pierre de Fermat (1601?–1665) conjecturou que esta fórmula produzia apenas números primos. Isso de

fato funciona para 0 ď n ď 4. A conjectura foi refutada por Leonhard Euler, que fatorou (em 1732) F5 “ 641 ¨ 6700417.

Exerćıcio 23. Discutir, por cada n inteiro, o mdc p3n2 ` 2, 3n` 1q.

Exerćıcio 24. Discutir, por cada n inteiro, o mdc p3n2 ` 7, 3n` 1q.

5

Exerćıcio 25. Indicando ra, bs o mı́nimo múltiplo comum de a e b, provar que se c P Z, temos

rac, bcs “ ra, bsc .

Semana VIII

Milies/Coelho, seção 2.6: exercicios 11 - 17.

seção 2.7: exerćıcios 3,4, 5, 6, 7, 8, 9,10, 11, 12, 13

seção 3.1: exerćıcios 1 - 13.

Exerćıcio 26 (Olimpiada Matemática de Moscovo, 1935). Sejam a, b, c P Z. Provar que

ra, b, cs ¨ pa, bq ¨ pa, cq ¨ pb, cq “ abc ¨ pa, b, cq .

Questão (***): como generalizar a fórmula precedente para n inteiros?

Exerćıcio 27. Provar que se a, b, P Z e que se pa, bq „ 1, então, por qualquer m P Z, temos

pab,mq “ pa,mq ¨ pb,mq

rab,ms “ ra,ms ¨ rb,ms{m

Exerćıcio 28. Um ideal I de Z se diz primo se é proprio e se ab P I implica que a P I ou que b P I. Provarque um ideal I de Z é primo se e somente se I “ pZ, com p primo.

Exerćıcio 29. Sejam I, J ideais de Z. Indicamos com I ` J o conjunto

I ` J “ ti` j | i P I, j P Ju .

Provar que I ` J é ideal de Z.

Exerćıcio 30. Sejam I, J ideais de Z. Dizemos que I, J são coprimos, ou relativamente primos, se I`J “ Z.Supomos agora que I “ aZ, J “ bZ. Provar que I, J são relativamente primos se e somente se pa, bq “ 1.

Exerćıcio 31. Um ideal I de Z se diz maximal se é proprio e se, chamado J outro ideal de Z, temos#

I Ď JJ ‰ Z

ùñ I “ J .

Provar que I é maximal se e somente se I “ pZ, com p irredut́ıvel.

Exerćıcio 32. Seja I um ideal de Z. Usando só as definições (sem usar a caraterização dos ideais de Z comoprincipais) provar que se I é maximal, então I é primo. (Dica: provar que se I é maximal, por cada a P Ztal que a R I, então existe x P Z tal que ax´ 1 P I. Tomar agora ab P I tal que a R I...).

Deduzir que um elemento irredut́ıvel é sempre primo.

Exerćıcio 33. Seja Ii, i P N, uma familia infinita, parametrizada por N de ideais de Z. Supomos que

I0 Ď I1 Ď I2 Ď I3 Ď ¨ ¨ ¨ Ď In Ď In`1 Ď ¨ ¨ ¨

Provar que a reuniãoď

iPNIi

é um ideal de Z.

6

Exerćıcio 34. Provar que não pode existir uma cadeia infinita de ideais Ii de Z tais que

I0 Ĺ I1 Ĺ I2 Ĺ I3 Ĺ ¨ ¨ ¨ Ĺ In Ĺ In`1 Ĺ ¨

ou seja, em que, cada ideal é stritamente contido no ideal que segue. (Uma tal cadeia se diz estritamente

crescente, ou estritamente ascendente). Dica: tomar a reunião YiPNIi, e exprimi-la como ideal aZ, por alguma P Z. Agora a P YiPNIi, ou seja, a P Ij por um certo j...Deduzir uma contradição.

Exerćıcio 35. Um ideal I de Z se diz primario se ab P I ùñ pa P Iq _ pbr P I, Dr P N˚q. Provar que se Ié primo, então I é primario.

Exerćıcio 36. Seja I um ideal de Z. Denotamos com?I “ tn P Z | nr P I, Dr P N˚u .

• Provar que?I é ideal de Z e que I Ď

?I. O ideal

?I se diz o radical de I. Em geral, um ideal I se

diz reduzido se I “?I.

• Encontrar?

2100Z.

• Provar que um ideal I de Z é reduzido se e somente se I “ nZ, com n privo de quadrados, ou seja, talque cada primo associado de n apareça com expoente 1 na fatoração de n.

• Seja I “ nZ, seja?I “ mZ. Provar que Pn “ Pm, onde Pa são os primos (positivos) associados a a.

• Provar que se I é primario, então?I é primo.

Exerćıcio 37 (Decomposição primaria). Seja I um ideal de Z. Dizemos que I é irredut́ıvel se chamadosP,Q ideais de Z, temos

I “ P XQ ùñ pI “ P q _ pI “ Qq .

• Provar que qualquer ideal de Z se escreve como interseção finita de ideais irredut́ıveis.

• Caraterizar os ideais irredut́ıveis

• Provar que cada ideal irredut́ıvel é primario.

• Provar que cada ideal de Z se escreve como interseção finita de ideais primarios.

• Provar que cada ideal de Z se escreve como interseção finita de potencias de ideais primos.

Exerćıcio 38. Determinar como tem que ser escolhido k P Z afim que a reta 28x ´ 42y “ k tenha pontosde coordenadas inteiras dentro do circulo de raio 10 e de centro p5, 0q. Por qual deste k assim determinados,os numeros de pontos no circulo é máximo?

Exerćıcio 39. Determinar todos os inteiros n tais que a reta p4n ` 2qx ` p3n ´ 1qy ` n “ 0 tenha pontosde coordenadas inteiras.

Exerćıcio 40. Determinar todos os inteiros n tais que a reta p4n`2qx`p3n´1qy`n`3 “ 0 tenha pontosde coordenadas inteiras.

Exerćıcio 41. Discutir a existência e encontrar todas as eventuais soluções da equação diofantina: 12x `18y ` 24z “ 36

Semanas IX-X-XI

Milies/Coelho: Seção 2.7: exercicios 1,2

7

Exerćıcio 42. (Para quem sabe a definição de limite). O teorema dos números primos afirma que, dado

πpxq “ |tp P N | p primo , p ď xu| ,

então

limxÑ`8

πpxqx{ log x “ 1 .

Provar que o enunciado do Teorema dos Números Primos é equivalente ao enunciado seguinte. Seja pn o

n-esimo primo positivo, por exemplo p1 “ 2, p2 “ 3, p3 “ 5, p4 “ 7, etc. Então

limnÑ`8

pnn log n

“ 1 .

Isto quer dizer que pn é, por n muito grande, aproximativamente do tamanho n log n.

Exerćıcio 43. Seja R uma relação entre o conjunto A e o conjunto B, de grafico ΓR. Seja R˚ a relação

entre B e A, simétrica de R, definida pelo grafico ΓR˚ Ď B ˆA, da forma seguinte:

ΓR˚ :“ tpb, aq P B ˆA | aRbu

• Provar que bR˚a ðñ aRb;• Provar que DpR˚q “ IpRq;• Provar que IpR˚q “ DpRq.• Provar que pR˚q˚ “ R.

Exerćıcio 44. É verdade que R é injetiva se e somente se R˚ é sobrejetiva?

Provar que R é injetiva se e somente se R˚ é univalente e que R é univalente se e somente se R˚ é injetiva.

Provar que R é sobrejetiva se e somente se R˚ é total a esquerda e que R é total a esquerda se e somente se

R˚ é sobrejetiva.

Exerćıcio 45. É verdade que uma relação R bijetiva é uma função? Provar ou encontrar um contraexemplo.

E se R é univalente e bijetiva?

E se R é total a esquerda e bijetiva?

Exerćıcio 46. Sejam R, S, T relações de A em B, de B em C, de C em D, respeitivamente. Provar que

T ˝ pS ˝Rq “ pT ˝ Sq ˝R

ou seja, que a composição de relações é associativa.

Exerćıcio 47. Sejam R, S relações de A em B e de B em C, respeitivamente. Provar que se R e S são

funções, então S ˝R é função.

Exerćıcio 48. Seja A “ t1, 2, 3, 4u, e B “ tn P Z | n “ m2 , Dm P Z, m ď 3u. Provar que AˆB Ď Nˆ N.Desenhar AˆB como subconjunto de Nˆ N. Quantos elementos tem AˆB?

Exerćıcio 49. Provar as seguintes propriedades do produto cartesiano de dois conjuntos:

1. AˆB “ H ðñ ppA “ Hq _ pB “ Hqq;2. AˆB “ B ˆA ðñ

“

ppA “ Hq _ pB “ Hqq _ pA “ Bq‰

;

3. Se A ‰ H, e AˆB Ď Aˆ C, então B Ď C;4. Se B Ď C, então AˆB Ď Aˆ C;

8

5. Se tBλuλPΛ é uma famı́lia4 de conjuntos, então provar que AˆŞ

λPΛBλ “Ş

λPΛAˆBλ

Exerćıcio 50. SejaR a relação de R em si definida pelo grafico ΓR :“ tpx, yq P Q2 | px2`4y2´4qpx´2yq “ 0u.• Desenhar o grafico da relação.• Provar que o grafico de R˚ é dado por ΓR˚ “ tpx, yq P Q2 | p4x2 ` y2 ´ 4qp2x ´ yq “ 0u. Desenhar o

grafico de R˚.

Exerćıcio 51. Seja R uma relação entre um conjunto A e um conjunto B; seja S uma relação do conjunto

B até o conjunto C. Definimos a relação composição S ˝R de A até C como a relação definida pelo graficoΓS˝R :“ tpa, cq P A ˆ C | pDb P BqppaRbq ^ pbScqqu. Seja agora A “ t1, 2, 3, 4u, B “ t0, 1, 2, 3u, C “t1, 2, 5u e seja ΓR “ tp1, 0q, p1, 1q, p3, 0q, p3, 4q, p4, 0qu e ΓS “ tp0, 1q, p0, 5q, p3, 5qu. Quem é ΓS˝R? Dar umarepresentação grafica em termos de diagramas de Venn de R, S e S ˝R.

Exerćıcio 52. Seja A um conjunto e R uma relação em A. Provar que

• R é simétrica ðñ R “ R˚;• R é transitiva ðñ R ˝R Ď R;

Deduzir que R é uma relação de equivalencia se e somente se DpRq “ X, R “ R˚ e R ˝R “ R.

Exerćıcio 53. Seja n P Z. Provar que se a, b, a1, b1 P Z, então#

a ” a1 mod nb ” b1 mod n

ùñ#

a` b ” a1 ` b1 mod nab ” a1b1 mod n

Exerćıcio 54. Consideramos a relação de divisibilidade em Z, ou seja, a relação R tal que, se a, b P Z, entãoaRb se e somente se a � b. Provar que é uma relação de pre-ordem em Z.

Exerćıcio 55. Seja X “ tjogadores de futebol do brasileirão 2017u. Consideramos a relação em X: xRyðñ x e y vestem a mesma camisa (camisa de desenho igual com iguais cores). Provar que R é uma relaçãode equivalencia. Descrever o conjunto quociente.

Exerćıcio 56. Provar que a relação de inclusão Ď entre subconjuntos de um conjunto X é uma relação deordem em PpXq. É verdade que a relação Ĺ é uma relação de ordem em PpXq?

Exerćıcio 57. Consideramos a relação em X “ R2ztp0, 0qu dada por px, yqRpx1, y1q ðñ existe λ P Q,λ ą 0 tal que x “ λx1, y “ λy1. Provar que a relação é de equivalencia e desenhar as classes de equivalencia.Provar que por cada ponto racional do circulo unitário5 em R2, existe uma e uma única classe de equivalenciaque o contem.

Exerćıcio 58. Consideramos o circulo unitario C “ tpx, yq P R2 | x2 ` y2 “ 1u em R2. Seja R a relação emC definida por px, yqRpx1, y1q ðñ [ (x “ ´x1 e y “ ´y1) ou (x “ x1, y “ y1)]. Determinar a cardinalidadede cada classe de equivalencia. Provar que se ` é uma reta passante pela origem, a interseção dela com o

circulo C é uma classe de equivalencia. Viceversa, dada qualquer classe de equivalencia, existe sempre uma

reta ` pela origem que a contem.

Exerćıcio 59. Determinar uma partição de N tal que todos os conjuntos da partição sejam finitos e tal quedois conjuntos distintos da partição tenham um número diferente de elementos. Fazer o mesmo por Z.

4Se tiverem problemas com uma famı́lia arbitraria, demonstrem por un numero finito de conjuntos B1, . . . , Bm a fórmula

Aˆ pB1 XB2 X ¨ ¨ ¨ XBnq “ pAˆB1q X pAˆB2q X ¨ ¨ ¨ X pAˆBnq

5chamamos o circulo unitario em R2 o conjunto tpx, yq P R2 | x2 ` y2 “ 1u

9

Exerćıcio 60. Sejam R1 e R2 duas relações de equivalencia definidas num conjunto A, A ‰ H. Seja a umelemento arbitrario de A. Denotamos com ras1 a classe de equivalencia de a relativamente a primeira relaçãoe ras2 a classe de equivalencia de a relativamente à segunda relação. Consideramos a relação R :“ R1 XR2em A, definida pelo grafico ΓR :“ ΓR1 X ΓR2 Ď AˆA, onde ΓRi é o grafico da relação Ri.

• Provar que R é uma relação de equivalencia• Se a é um elemento arbitrario de A, e se denotamos com ras a classe de equivalencia do elemento a

relativamente à relação R, provar que ras “ ras1 X ras2.

Exerćıcio 61. Seja A um conjunto não vazio e sejam tSλuλPΛ e tTµuµPM duas partições de A. SejaN :“ tpλ, µq P ΛˆM | Sλ X Tµ ‰ Hu. Provar que tSλ X Tµupλ,µqPN é partição de A.

Exerćıcio 62. Seja A “ t1, 2, 3, 4, 5u ˆ t1, 2, 3, 4, 5u. Definimos uma relação R em A da forma seguinte:px, yqRpz, wq se e somente se x` z “ y ` w.

1. Provar que R é uma relação de equivalencia.

2. Encontrar todas as classes de equivalencia.

Exerćıcio 63. Encontrar todas as relações de equivalencia definidas em A “ t1, 2, 3u.

Exerćıcio 64. Consideramos a relação em R2 definida por px, yq „ px1, y1q se e somente se x ´ x1 “py ´ y1qpy ` y1q. Provar que é uma relação de equivalencia. Desenhar as classes de equivalencia.

Exerćıcio 65. Seja f : A - B uma função. Provar que f é injetiva se e somente se existe uma função g

(inversa esquerda) tal que g ˝ f “ idA.

Exerćıcio 66. Seja f : A - B uma função. Provar que f é sobrejetiva se e somente se existe uma função

g (inversa direita) tal que f ˝ g “ idB .

Exerćıcio 67. Seja f : A - B uma função. Supomos que f admita uma inversa esquerda g1 e uma

inversa direita g2. Provar então que g1 “ g2 e que f é inverśıvel.

Exerćıcio 68. Quais das seguintes funções é injetiva? sobrejetiva? bijetiva? Em caso seja injetiva, encontrar

uma sua inversa esquerda; em caso seja sobrejetiva encontrar uma sua inversa direita; em caso seja bijetiva,

encontrar uma sua inversa.

1. f : N - N, onde fpnq “ 2n;2. f : N - Z, onde fpnq “ 2n;3. f : N - N, onde fpnq “ n{2 se n é par e fpnq “ pn` 1q{2 se n impar.4. f : tn P Z | n ě ´3u - N; fpnq “ n2 ` 7n` 13.5. f : Q2 - Q2, fpx, yq “ px` 2y, 3´ 4x` 5yq.6. f : N - Nˆ N, fpnq “ pn2, n` 1q.7. f : Nˆ N - Z, fpn,mq “ n2 ´ 2m` 1.

Exerćıcio 69. Sejam X,Y, Z conjuntos e sejam f : X - Y , g : Y - Z funções. Provar as seguintes

afirmações.

1. Se f e g são injetivas, então g ˝ f : X - Z é injetiva.2. Se f e g são sobrejetivas, então g ˝ f : X - Z é sobrejetiva.3. Se g ˝ f é injetiva, então f é injetiva. Mostrar que não é necessário que g seja injetiva.4. Se g ˝ f é sobrejetiva, então g é sobrejetiva. f é necessariamente sobrejetiva?

10

5. Se g ˝ f é bijetiva, então f é injetiva e g é sobrejetiva. É verdade que neste caso g é injetiva e que f ésobrejetiva? Demonstrar ou encontrar um contraexemplo.

6. Se g ˝ f é bijetiva, qual é pg ˝ fq´1?

Exerćıcio 70. Sejam A e B dois conjuntos. Dizemos que A tem o mesmo cardinal de B se existe uma

bijeção de A em B e indicamos |A| “C |B|. Dizemos que o cardinal de A é finito e igual a n se A se podepor em bijeção com t1, . . . , nu. Dizemos que o cardinal de A é infinito se A não se pode por em bijeção comum t1, . . . , nu, ou se A é vazio. Dizemos que o cardinal de A é menor ou igual ao cardinal de B se e somentese existe uma injeção de A em B e escrevemos |A| ďC |B|.

Provar que |A| ďC |B| se e somente se existe uma sobrejeção B -- A.(Cuidado: |A| e |B| não são números!, A e B podem ser infinitos!).

Exerćıcio 71. Provar que |N| “C |N˚| “C |5N| “C |Z|.

Exerćıcio 72. Seja n P N, n ě 1. Consideramos o conjunto In`1 :“ t1, . . . , n ` 1u. Seja m0 P In. Provarque In`1ztm0u pode ser posto em bijeção com In.

Exerćıcio 73. Provar, por indução sobre n, que uma função In - In é injetiva se e somente se é

sobrejetiva se e somente se é bijetiva.

Exerćıcio 74. Provar que se existe uma injeção In Ă - Im, então n ď m. (Dica: raciocinar por absurdo eusar que uma função de In até In é injetiva se e somente se é bijetiva.)

Exerćıcio 75. Seja X um conjunto não vazio. Seja f : X - X uma função. Provar que se existem

duas inversas esquerdas distintas g1, g2 de f (ou seja, duas funções g1 : X - X, g2 : X - X tais que

gi ˝ f “ idX , então existem infinitas tais inversas esquerdas distintas.

˚ Mostrar que a cardinalidade do conjunto de tais inversas esquerdas é maior ou igual ao cardinal doconjunto X.

Exerćıcio 76. Seja X um conjunto não vazio. Seja f : X - X uma função. É verdade que se existem

duas inversas direitas distintas g1, g2 de f (ou seja, duas funções g1 : X - X, g2 : X - X tais que

f ˝ gi “ idX , então existem infinitas tais inversas direitas distintas?)

Exerćıcio 77. Sejam pX,ďXq e pY,ďY q conjuntos totalmente ordenados, com as relaçãos de ordem ďX eďY , respeitivamente. Seja f : X - Y uma função stritamente crescente, ou seja, tal que, se x1 ňX x2,então fpx1q ňY fpx2q. Provar que f é injetiva. Provar a mesma coisa para uma função f stritamentedecrescente.

Exerćıcio 78. Sejam X, Y dois conjuntos finitos não vazios, com m e n elementos, respeitivamente.

• Quantas relações há entre X e Y ?• Quantas funções há entre X e Y ?• Quantas funções injetivas há entre X e Y ?

Exerćıcio 79. Seja f : X - Y uma função entre dois conjuntos não vazios. Seja A Ď X um subconjuntode X. Seja Γf o grafico de f (ou seja, o subconjunto Γf Ď XˆY que define a relação/função f). A restriçãode f a A é a relação de A em Y definida como Γf XAˆ Y Ď Aˆ Y . Provar que esta relação é uma função.Ela se indica com f

ˇ

ˇ

A: A - Y .

Exerćıcio 80. Seja f : X - Y uma função. Seja Ipfq a imagem de f . Provar que Γf é naturalmenteum subconjunto de X ˆ Ipfq e que então f define naturalmente uma função f : X - Ipfq.

11

Exerćıcio 81. Sejam X,Y, Z conjuntos não vazios. Provar que

• pXY qZ pode ser posto em bijeção com XYˆZ .• Se Y X Z “ H, então XYYZ pode ser posto em bijeção com XY ˆXZ .• Provar que pX ˆ Y qZ pode ser posto em bijeção com XZ ˆ Y Z .

Denotamos a potencia |X||Y | de dois cardinais |X| e |Y | como o cardinal do conjunto potencia, ou seja

|X||Y | :“ |XY | .

Interpretar os fatos precedentes como propriedades de potências de cardinais:

• |X|p|Y |`|Z|q “C |X||Y ||X||Z|

• p|X||Y |q|Z| “C |X||Z||Y ||Z|.

Exerćıcio 82. Provar que, se X é um conjunto,

|PpXq| “C |t1, 2uX | “C 2|X|

Denotaremos com m|X| o cardinal do conjunto pImqX .

Exerćıcio 83. Provar que o conjunto RA,B das relações entre um conjunto A e um conjunto B pode serposto em bijeção com o conjunto pI2qX e que então tem cardinal 2|X|.

Exerćıcio 84. Seja f : X - Y uma função entre dois conjuntos X e Y . Se A Ď X, Indicamos comfpAq “ ty P Y | y “ fpxq, x P Au.Provar que fpAYBq “ fpAq Y fpBq.Provar que fpAXBq Ď fpAq X fpBq. Val a igualdade? Provar o dar um contraexemplo.É verdade que fpXzAq “ fpXqzfpAq?Provar que f é injetiva se e somente se val

fpAXBq “ fpAq X fpBq

por cada par de subconjuntos A,B de X.

Exerćıcio 85. Seja f : X - Y função entre dois conjuntos X e Y . Se A Ď Y , indicamos com f´1pAq “tx P X | fpxq P Au. Provar que f´1pAXBq “ f´1pAq X f´1pBqf´1pAYBq “ f´1pAq Y f´1pBqf´1pY zAq “ Xzf´1pAqProvar que, por cada A Ď X, temos

A Ď f´1pfpAqq .

Provar que”

@A Ď X, A Ď f´1pfpAqqı

ðñ f injetiva .

Exerćıcio 86. Seja f : X - Y função entre dois conjuntos X e Y . Provar que, por cada B Ď Y , temos

fpf´1pBqq Ď B .

Provar que”

@B Ď Y, B “ fpf´1pBqqı

ðñ f sobrejetiva .

Exerćıcio 87. Sejam a, b P Z. Consideramos a função f : Z - Z definida por fpxq “ ax`b. Caraterizar6

os inteiros a, b tais que f é bijetiva.

6ou seja, dar condições necessárias e suficientes

12

Exerćıcio 88. Consideramos a tentativa de definição de uma função f : Z{nZ - Z{mZ, que enviariarxsn - rxsm. Caraterizar os n,m P N˚ tais que a tentativa é uma boa definição para a função f .

Exerćıcio 89. Consideramos em R2 a relação px, yqRpx1, y1q se e somente se 3x´ y “ 3x1 ´ y1. Provar queé uma relação de equivalencia e representar no plano Q2 as classes de equivalencia. Consideramos agora atentativa de definição de uma função f : R2{R - Q assim escrita:

fprpx, yqsq “ ax` by ` c

por alguns racionais fixados a, b, c. Dar uma condição necessaria e suficiente sobre a, b, c para que a tentativa

de definição seja uma boa definição para uma função f : R2{R - R.

Exerćıcio 90. Seja f : X - Y uma função entre conjuntos X e Y . A função f induz funções imagem e

imagem inversa

f : PpXq - PpY q

f´1 : PpY q - PpXq

definidas por A - fpAq e B - f´1pBq, respeitivamente.• Provar que se f : X - Y é injetiva se e somente se f : PpXq - PpY q é injetiva.• Provar que f : X - Y é sobrejetiva se e somente se f : PpXq - PpY q é sobrejetiva.• É verdade que f : X - Y injetiva se e somente se f´1 : PpY q - PpXq é injetiva?• É verdade que f : X - Y é sobrejetiva se e somente se f´1 : PpY q - PpXq é sobrejetiva?

Exerćıcio 91. Provar que uma função f : X - Y é bijetiva se e somente por cada y P Y , |f´1ptyuq| “ 1.

Exerćıcio 92. Seja S o conjunto dos naturais da forma 2n3m, por n,m P N˚. Definimos f : S - Q comofp2n3mq “ m{n. É esta uma boa definição? Porquê?

Exerćıcio 93. Seja f : X - Y uma função entre conjuntos não vazios. Provar que a relação xRfy ðñfpxq “ fpyq é uma relação de equivalencia. Provar que f : X - Y se fatora como f “ f̂ ˝ π atraves deuma injeção f̂ : X{Rf Ă - Y , tal que Ipf̂q “ Ipfq.

Exerćıcio 94. Seja f : X - Y uma função entre conjuntos não vazios. Seja S uma relação de equivalencia

em X. Provar que f se fatora como f “ f̂ ˝ π atraves de f̂ : X{S - Y se e somente se xSy ùñxRfy ðñ fpxq “ fpyq, ou seja, se e somente se ΓS Ď ΓRf . Provar que f̂ é injetiva se e somente sefpxq “ fpyq ðñ xRfy ùñ xSy, e então se e somente se Rf “ S.

Provar que f se fatora como f “ f̂ ˝ π atraves de f̂ : X{S - Y se e somente se cada classe deequivalencia rxsS para S é contida numa fibra de f (ou seja, por cada x P X, existe y P Y tal que rxsS Ďf´1ptyuq, ou seja, se e somente se f é contante ao longo das classes de equivalencia).

Exerćıcio 95. Seja A um conjunto não vazio e sejam R e S duas relações de equivalencia em A tais que

xRy ùñ xSy. Indicamos com rxsR e rxsS as classes de equivalencias de x para R e para S. Provar que omapa natural rasR

S- é bem definida e é sobrejetiva como mapa

A{R - A{S .

Exerćıcio 96. Usando o exercicio precedente caraterizar n,m P N tais que a posição rasnm- é bem

definida como função

Z{nZ - Z{mZ .

13

Exerćıcio 97. Sejam a, b, n,m P N. Caraterizar a, b, n,m tais que a posição rax` bsnm- é bem definida

como função

Z{nZ - Z{mZ .

Exerćıcio 98. Seja f : X - Y uma função entre dois conjuntos não vazios. Seja R uma relação de

equivalencia em X e S uma relação de equivalencia em Y . Supomos que xRy ùñ fpxqSfpyq. Provar quef induz uma função f̂ : X{R - Y {S. É verdade que se f é sobrejetiva, então f̂ é sobrejetiva? Provarque se f é bijetiva e se temos xRy ùñ fpxqSfpyq então f̂ é bijetiva.

Exerćıcio 99. Seja X um conjunto finito. Seja f : X - X uma involução de X, ou seja, uma função tal

que f2 “ idX . Provar que se |X| é impar, então f tem pelo menos um ponto fixo (ou seja, um x0 P X talque fpx0q “ x0). Provar mais em geral (para um conjunto finito qualquer X) que o número de pontos fixosé congruente a |X| módulo 2. (Dica: definir uma relação de equivalencia adequada).

Exerćıcio 100. Sejam X e Y conjuntos e sejam R e S relações de equivalencia definidas em X e Y ,

respectivamente. Definimos a relação produto Rˆ S em X ˆ Y da forma px, yqRˆ Spx1, y1q se e somente sexRx1 e ySy1.

• Provar que Rˆ S é uma relação de equivalencia.

• Consideramos a função f : X ˆ Y - X{R ˆ Y {S, que associa px, yq - prxsR, rysSq. Provar que fdesce a uma bijeção f̂ : X ˆ Y {pRˆ Sq - X{Rˆ Y {S.

Exerćıcio 101. Deduzir do exercicio precedente que se n P N, e n “ hk, com ph, kq “ 1, então Z{nZ é embijeção com Z{hZˆ Z{kZ.

Exerćıcio 102. Seja A o intervalo r0, 1s “ tx P R | 0 ď x ď 1u. Consideramos a familia de subconjuntostCλuλPr0,1q dada por C0 “ t0, 1u, e Cλ “ tλu por λ P p0, 1q. Provar que é uma partição de A. Encontrar arelação de equivalencia R associada à partição. Quem é A{ „ a menos de bijeção? Como você descreveriaem palavras a projeção quociente π : A - A{R?

Exerćıcio 103. Seja f : Z - Z da forma fpxq “ ax` b, por inteiros fixados a, b P Z. Encontrar todos osa, b P Z tais que f2 :“ f ˝ f “ idZ.

Exerćıcio 104. Seja X um conjunto finito não vazio com n elementos. Seja f : X - X função. Provar

que existe um m tal que fm “ idX .

Exerćıcio 105. Provar que a relação de associado „ é uma relação de equivalencia em Z. Mostrar que oquociente Z{ „ é em bijeção com N.

Exerćıcio 106. Seja A um conjunto com uma relação de equivalencia R e seja S outra relação. Consideramos

o conjunto quociente A{R. Quando é que a posição

rxsŜrys ðñ xSy

é uma boa definição para uma relação sobre A{R? Neste caso diremos que Ŝ é a relação induzida por Ssobre A{R.

Exerćıcio 107. Seja A um conjunto e seja T uma relação de pre-ordem (reflexiva e transitiva) sobre A.

Consideramos a relação R sobre A definida como aRb ðñ paTbq ^ pbTaq. Provar que R é de equivalenciasobre A e que T induz uma relação de ordem T̂ sobre A{R. Deduzir que a relação de divisibilidade induzuma relação de ordem sobre Z{ „.

14

Exerćıcio 108. Qual destas definições é uma BOA DEFINIÇÃO? Porque?

1. f : Z{4Z - Z{8Z definida como: fprnsq “ r2ns82. f : Z{3Z - Z{9Z definida como: fprnsq “ 4n` 33. f : Z{8Z - t1,´1u definida como: fprnsq “ p´1qn

4. f : Q - Q definida como m{n - 2m{3n.5. f : Z{12Z - Z{8Z, definida como rxs12 - r6x2 ` 5s8.

Exerćıcio 109. Sejam X,Y, Z,W conjuntos não vazios. Seja g : Y - Z uma função.

1. Provar que g é injetiva se e somente se, por cada f1, f2 funções de X - Y ,

g ˝ f1 “ g ˝ f2 ùñ f1 “ f2 .

2. Provar que g é sobrejetiva se e somente se por cada h1, h2 funções de Z - W ,

h1 ˝ g “ h2 ˝ g ùñ h1 “ h2 .

Exerćıcio 110. 1. Seja f : Z - N definida por

x -

#

k se x “ p2kql, por algum k P N, e por algum l P Z|x| se x é impar

.

É esta uma boa definição de função para f? Motivar em detalhe.

2. Seja A “ t1, 2, 3, 4, 5, 9u, B “ t0, 1, 2, 3u, . Seja f : A - B a função definida por

fpxq “#

n´ 1 se x “ n2, n P N3 se x não é um quadrado

Quem são7 f´1p0q, f´1p1q, f´1p2q, f´1p3q? É injetiva? É sobrejetiva? É bijetiva? Se sim, encontraruma inversa direita ou/e esquerda.

Exerćıcio 111. 1. Consideramos a relação em Z definida por aRb ðñ a2 ´ b2 ď 3. É reflexiva? Ésimétrica? É transitiva? É uma relação de equivalencia? Motivar em detalhe. É reflexiva: de fato, se a P Z,a2 ´ a2 “ 0 ď 3.

2. Consideramos a relação em Z dada por aRb ðñ 2a` 5b ” 0 mod 7. Provar que é uma relação deequivalencia. Descrever o conjunto quociente.

3. Seja A “ t0, 1, 2, 3, 4u. Seja Γ “ tpx, yq P AˆA | p2y´ 3x` 1qp2y´xq “ 0u. É reflexiva? É simétrica?É transitiva? É uma relação de equivalencia? É função?

Exerćıcio 112. Seja A “ tm P N | 1 ď m ď 5u. Seja Γ um subconjunto de AˆA tal quei) a relação definida por Γ é reflexiva e simétrica

ii) p1, 2q P Γ, p4, 5q P Γiii) Γ é o mais pequeno subconjunto de AˆA com as propriedades i) e ii).

1. Determinar completamente Γ.

2. A relação definida por Γ é uma função? Motive em detalhe a resposta.

3. Provar que a relação definida por Γ é uma relação de equivalencia.

4. Determinar todas as classes de equivalencia e o conjunto quociente.

7Lembro que, se f : X - Y é uma função e y0 P Y , então f´1py0q “ tx P X | fpxq “ y0u

15

Exerćıcio 113. Consideramos o conjunto A “ R3ztp0, 0, 0qu. Consideramos a relação R em A definida porpx, y, zq „ px1, y1, z1q ðñ Dλ P R, λ ‰ 0, tal que x1 “ λx, y1 “ λy, z1 “ λz. Provar que é uma relação deequivalencia. O conjunto quociente A{R é chamado o plano projetivo real e é indicado com P2R. Provar queé em bijeção com R2

š

S1.

Exerćıcio 114. Com K indicamos o corpo R ou C (o exercicio se pode fazer nos dois casos). Seja n P N.Consideramos o conjunto A “ Kn`1zt0u (aqui 0 é a origem em Kn`1). Consideramos a relação R em Adefinida como px0, . . . , xnqRpy0, . . . , ynq se e somente se existe λ P K˚ tal que xi “ λyi por cada i “ 0, . . . , n.Provar que R é uma relação de equivalencia em A. O conjunto A{R é chamado o espaço projetivo real (seK “ R) ou complexo (se K “ C) de dimensão n, e indicado com PK. Provar que

1. P0K é o cojunto com um elemento (um ponto).

2. PK pode ser posto em bijeção com Knš

Pn´1K (reunião disjunta).

3. P1R pode ser posto em bijeção com S1 “ tpx, yq P R2 | x2 ` y2 “ 1u via a bijeção

S1 Q pcos θ, sin θq - rpcos 2θ, sin 2θqs P P1R

Onde esta θ? A bijeção esta bem definida?

4. P1C pode ser posto em bijeção com S2 “ tpx, y, zq P R3 | x2`y2`z2 “ 1u. (usar a projeção estereografica:projetar um ponto de S2 (fora dos polos) no plano tpx, y, 0q | x, y, P Ru Ď R3 e completar nos polos usandoos pontos precedentes...).

Exerćıcio 115. Consideramos o conjunto A “ R2ztp0, 0qu e a relação R tal que px, yqRpx1, y1q se e somentese existe λ P R, λ ą 0 tal que x “ λx1, y “ λy1.

1. Provar que R é uma relação de equivalencia e que A{R se pode por em bijeção com S1 via a funçãopcos θ, sin θq - rpcos θ, sin θqs. Onde esta θ? A bijeção é bem definida?

2. Provar que existe uma aplicação natural ϕ : A{R - P1R.

3. Depois de identificar A{R com S1 (como feito aqui acima) e de identificar P1R com a bijeção do exercicioprecedente, calcular a composição ϕ : S1

bij- A{R - P1Rbij- S1, onde com bij indicamos as

identificações?

4. Provar que por cada y P S1, o conjunto ϕ´1pyq tem dois elementos (isto é o que se chama recobrimentotopológico 2 : 1).

Exerćıcio 116. Seja R uma relação em C definida da forma seguinte. Sejam z “ x` iy, w “ a` ib. EntãozRw ðñ x2 ´ y2 “ a2 ´ b2. Provar que R é uma relação de equivalencia.Desenhar ris.Tentamos de definir uma função f : C{R - C{R, da forma fprzsq “ rz ` 1s. É uma boa definição? Éinjetiva? É sobrejetiva?

E a função gprzsq “ rz2 ´ zs?

Semana 22/10-27/10.

Milies-Coelho: Seção 3.2: exercicios 1 - 10. Seção 3.3: exercicios: 1 - 4.

Semana 30/10-02/11. Milies-Coelho: Seção 3.3: exercicios: 1 - 4. Seção 3.4: exerćıcios 1 - 7.

Exerćıcio 117. Seja n “ αm10m ` αm´110m´1 ` ¨ ¨ ¨ ` α110 ` α0 uma escritura decimal de n P N, onde,claramente, αi P N, 0 ď αi ď 9 e αm ‰ 0. Provar que

16

• 2 � n ðñ 2 � α0 ðñ α0 ” 0 mod 2

• 3 � n ðñ 3 �řmi“0 αi ðñ

řmi“0 αi ” 0 mod 3

• 5 � n ðñ 5 � α0 ðñ α0 ” 0 mod 5

• 9 � n ðñ 9 �řmi“0 αi ðñ

řmi“0 αi ” 0 mod 9

• 11 � n ðñ 11 �řmi“0p´1qiαi ðñ

řmi“0p´1qiαi ” 0 mod 11.

Exerćıcio 118. Os números de Fermat são definidos por Fn “ 22n ` 1, isto é, F0 “ 3, F1 “ 5, F2 “ 17,. . .

1. Prove que Fn`1 “ 2` F0F1 ¨ ¨ ¨Fn.

2. Mostre que quaisquer dois números de Fermat distintos são primos entre si.

Nota histórica: Pierre de Fermat (1601?–1665) conjecturou que esta fórmula produzia apenas números primos. Isso de

fato funciona para 0 ď n ď 4. A conjectura foi refutada por Leonhard Euler, que fatorou (em 1732) F5 “ 641 ¨ 6700417.

Exerćıcio 119. 1. Prove que para todo n número natural, n ě 1, a sequência pn`1q!`2, pn`1q!`3, pn`1q!` 4, . . . , pn` 1q!` pn` 1q não tem nenhum número primo.

2. Mostre que pn` 1q!` pn` 2q pode ser primo.

Exerćıcio 120. Prove se verdadeiro ou apresente um contra-exemplo caso falso.

(a) Se p é primo tal que mdcpa, pq “ 1 e ab ” ac mod p então b ” c mod p.

(b) Se n é um número inteiro ı́mpar então 209n é múltiplo de 9.

Exerćıcio 121. 1. Verdadeiro ou falso? Justifique sua resposta!

(a) Sejam a, b e m inteiros com m ě 2. Vale ab ” 0 mod m se e somente se a ” 0 mod m ou b ” 0 mod m.

(b) Se a ” b mod m e a1 ” b1 mod m1 ent”o aa1 ” bb1 mod mm1.

(c) Sejam a, b e m inteiros positivos. Então a2 ” b2 mod m se e somente se a ” b mod m.

(d) Se a, b e m são inteiros com m ě 2 então pa` bqm ” am ` bm mod m.

Exerćıcio 122. 1. Faça uma tabela de inversos multiplicativos módulo 11, usando apenas os números de 0

a 10.

2. Encontre todas as soluções do sistema:

2x` 3y ” 1 mod 11

x` 4y ” 4 mod 11

Exerćıcio 123. Seja um número n, e seja p a soma dos seus algarismos. Mostre, usando aritimética módulo

9, que n é diviśıvel por 9 se e somente se p é múltiplo de 9.

Exerćıcio 124. Escrevemos os algarismos 1, 2, 3, 4, 5 (nessa ordem) cinquenta vezes. Chamemos de x o

número obtido, isto é, x “ 1234512345. . .12345. Qual o resto da divisão de x por 9?

Exerćıcio 125. Determine que números possuem raiz quadrada módulo 11. (Isto é, determine para quais

inteiros a existe algum x tal que x2 ” a mod 11.)

Exerćıcio 126. Seja p um número primo e n P N˚. Mostre que existe um inverso multiplicativo de a módulop se e somente se existe um inverso multiplicativo de a módulo pn.

17

Exerćıcio 127. Demonstrar o teorema de Wilson:

Um número inteiro p ą 1 é primo, se e somente se, pp´ 1q! ” ´1 mod p.

Exerćıcio 128. Determinar todos os naturais menores que 3000 que têm resto 9 na divisão por 37 e

simultaneamente resto 15 na divisão por 52.

Exerćıcio 129. Prove que os inteiros k e k5 têm o mesmo algarismo das unidades.

Exerćıcio 130. Determine todas as soluções dos seguintes sistemas:

#

x ” 2 mod 3x ” 3 mod 10

$

’

&

’

%

x ” 3 mod 4x ” 7 mod 3x ” 10 mod 5

$

’

&

’

%

x ” 3 mod 4x ” 7 mod 6x ” 10 mod 5

Exerćıcio 131. Encontrar todas os inteiros x, y, z tais que

$

’

’

’

’

’

’

’

’

’

&

’

’

’

’

’

’

’

’

’

%

7

9x´ 1

9P Z

5

12x´ 11

12P Z

8

15x´ 1

3P Z

Exerćıcio 132. Denotamos com eiθ :“ cos θ ` i sin θ, com θ P R, e i unidade imaginária. Encontrar todasas soluções inteiras de

ei103 πxei8πy “ e´4iπz

Discutir a existência e determinar, em caso existem, todas as soluções do sistema de congruências:

$

’

&

’

%

4x ” 28 mod 647x ” 9 mod 1816x ” 4 mod 84

Exerćıcio 133. Discutir a existência e determinar, em caso existem, todas as soluções do sistema:

$

’

&

’

%

ei20π17 x “ ei 6π17

ei7π6 x “ ei 11π6

ei16π15 x “ ei 8π15

Exerćıcio 134. • Determine o resto da divisão de 3355640 por 641.

• Determine o resto da divisão de p111111 ` 222222 ` 333333q444 por 7.

• Determine o resto da divisão de 2122 ¨ 7203 ` 58 por 9.

• Determine o algarismo das unidades de 37100.

• Determine o algarismo das unidades de 2x, onde x “ 32010.

• Determine o algarismo das unidades de 7x onde x “ 191002.

• Determine o menor inteiro positivo x de modo que 3221 ¨ 7343 ´ x seja diviśıvel por 4.

• Determine o algarismo das unidades de 1772192011 .

• Encontre o inverso multiplicativo de 62420 ` 4128 módulo 103.

18

Exerćıcio 135. • Mostrar que por cada k, h P N, o inteiro

724k`30h ` 7pk6`h6q´k2´h2 ` 7

é diviśıvel por 9.

• Dizer por quais m naturais os inteiros

73m`5 ` 13 ¨ 173m, 73m`5 ´ 13 ¨ 173m

são divisiveis por 20.

• Encontrar todos os k P Z tais que pk2 ` 2kqp101101q é inversivel módulo 24,

• Por cada k encontrado no ponto precedente, calcular o inverso de pk2 ` 2kqp101101q mod 24.

1. Encontrar o mı́nimo natural k P Nzt0u tal que 7k ” 1 mod 15.

2. Provar que 7y ” 1 mod 15 se e somente se y é múltiplo de k. (Dica: seja r o resto da divisão euclidianade y por k: provar que 7r ” 1 mod 15 e obter uma contradição). Deduzir que kϕp15q.

Exerćıcio 136. 1. Mostre que para qualquer n inteiro, 34n`9 ` 4n`3 é multiplo de 7.

2. Mostre que para qualquer n inteiro, n8 ´ n2 é múltiplo de 42.

Exerćıcio 137. Seja p um primo e seja q um inteiro.

1. Mostrar que se q2 ı q mod p, então

1` q ` ¨ ¨ ¨ ` qp´1 ” 1 mod p .

2. Mostrar, mais em geral que se q2 ı q mod p e n P Nzt0u, então

1` q ` ¨ ¨ ¨ ` qn´1 ” tpqr ´ 1q mod p

onde t é o inverso multiplicativo de q ´ 1 módulo p e r é o resto de n na divisão por p´ 1.

3. O enunciado precedente continua a valer se q2 ” q mod p? Discutir os casos q ” 0 mod p e q ” 1 mod p.

Exerćıcio 138. Mostrar que o seguinte sistema tem uma solução inteira ðñ k ” 48 mod 155.#

11x´ 5y “ k9x` 10y “ ´3 .

Exerćıcio 139. 1. Mostre que para qualquer n inteiro, 34n`9 ` 4n`3 é multiplo de 7.

2. Mostre que para qualquer n inteiro, n8 ´ n2 é múltiplo de 42.

Exerćıcio 140. À questão “Determine todas as soluções inteiras da equação diofantina 6x ` 10y “ 76 ”,Joãozinho respondeu:

19

Jõaozinho encontra antes de tudo uma solução particular x0 “ 71, y0 “ ´35: de fato: 6p71q`10p´35q “426´ 350 “ 76.Usando aritmética módulo 6 e módulo 10, a equação implica

#

10y ” 76 mod 66x ” 76 mod 10

.

O sistema se reduz a

#

4y ” 4 mod 66x ” 6 mod 10

, e então

#

y ” 1 mod 6x ” 1 mod 10

.

Assim, todas os x solução são congruentes módulo 10 e todos os y solução são congruentes módulo 6.

Mais precisamente, obtemos todas as outras soluções se escrevem x “ 71` 10 ¨ z, y “ ´35´ 6 ¨ z paraos valores de z inteiro. Verificamos

6x` 10y “ 6 ¨ p71` 10zq ` 10 ¨ p´35´ 6zq “ 426` 60z ´ 350´ 60z “ 76 .

Porém, x1 “ 76, y1 “ ´38 é solução, e não se pode escrever da forma x “ 71 ` 10 ¨ z, y “ ´35 ´ 6 ¨ z.Explique porque esse fato mostra que a resposta do Joãozinho está errada, e explique o erro de Joãozinho.

Exerćıcio 141. O Joãozinho encontrou um método espectacular para resolver sistemas de congruencias.

Por exemplo, dado o sistema de congruencias

$

’

&

’

%

x ” 3 mod 4x ” 1 mod 3x ” 0 mod 5

(1)

Joãozinho pensou: para encontrar todas as soluções é suficiente resolver as congruencias

3 ¨ 5k1 ” 3 mod 4 , 4 ¨ 5k2 ” 1 mod 3 , 4 ¨ 3k3 ” 0 mod 5 , (2)

em k1, k2, k3, respectivamente. Uma vez que foram encontradas todas as soluções k1, k2, k3 das congruencias

acima, a solução geral do sistema inicial vai ser

x “ 3 ¨ 5k1 ` 4 ¨ 5k2 ` 4 ¨ 3k3 ,

onde k1, k2, k3 são soluções quaisquer das congruencias em (2).

1. Aplicar o método do Joãozinho ao sistema (A) e verificar que este metodo fornece corretamente todas as

soluções.

2. O Joãozinho, aplicando o seu metodo espectacular ao sistema

$

’

&

’

%

x ” 3 mod 4x ” 5 mod 6x ” 7 mod 8

(3)

deduz que o sistema (3) não tem nenhuma solução. Porquê Joãozinho deduz que não ha nenhuma solução

da forma

x “ 6 ¨ 8k1 ` 8 ¨ 4k2 ` 4 ¨ 6k3 ,

20

com ki soluções das congruencias

6 ¨ 8k1 ” 3 mod 4, 8 ¨ 4k2 ” 5 mod 6, 4 ¨ 6k3 ” 7 mod 8 ?

3. Aplicar o Teorema Chinês do Resto ao sistema (3) e mostrar que o Joãozinho se enganou.

4. Encontrar todas as soluções do sistema (3).

5. Mostrar que o método do Joãozinho sempre funciona quando temos um sistema$

’

&

’

%

x ” a mod mx ” b mod nx ” c mod r

onde m,n, r são a dois a dois coprimos.

Exerćıcio 142. Encontrar, se existem, todas as soluções da seguinte conguencia$

’

&

’

%

2x ” 2 ¨ p143q18 mod 143x ” 17 mod 283x ” 1 mod 4

Exerćıcio 143. 1. Provar que por cada n P N, n ‰ 0, n ‰ 1, n “ pq, p e q primos distintos, temos que

ma ” m mod n

por cada inteiro m P Z, se a ” 1 mod ϕpnq, onde ϕpnq é a função de Euler de n.

2. Generalizar a n da forma n “ p1 ¨ pr, com pi primos distintos.

3. Funciona para n qualquer? Provar ou dar um contraexemplo.

4. Quanto val ϕp10q, ϕp14q, ϕp7q?

5. Usando os pontos precedentes, resolver o sistema$

’

&

’

%

7x5 ” 1 mod 5x7 ” 5 mod 145x7 ” 4 mod 7 .

Exerćıcio 144. Consideramos o sistema de congruencias:#

3x2 ” 13 mod 147x ” 11p8341q mod 24 .

(A)

1. Dizer, com menos contas posśıvel, se o sistema (A) tem ou não solução e motivar a resposta em detalhe.

2. No caso a resposta ao ponto precedente seja afirmativa, encontrar todas as soluções.

Exerćıcio 145. Por quais valores inteiros stritamente positivos de k a equação diofantina

pk ` 1qx` p3k ´ 1qy “ kk ` k (4)

tem soluções inteiras? Justificar em detalhes.

Exerćıcio 146. Sejam n,m dois inteiros tais que

n2 � 540 , p540,mq � 25 .

Provar então que, para todo k P Z,

km ” 0 mod n ùñ k ” 0 mod n .

21

Exerćıcio 147. Calcular os últimos dois digitos de

3p3p3p...

......3 qqqlooooomooooon

2012´vezes.

Exerćıcio 148. Seja pA,`, ¨q um anel comutativo, com elementos neutros 0 e 1. Um elemento a P A se dizdivisor de zero se existe b P A, b ‰ 0 tal que ab “ 0. O elemento 0 é claramente um divisor de zero, chamadodivisor de zero trivial.

• Provar que, em geral, se a P A é divisor de zero, então a não pode ser multiplicamente inverśıvel.

• Provar que Z{nZ tem divisores de zero nontriviais se e somente se n não é primo.

• Seja agora n “ pα11 ¨ ¨ ¨ pαrr uma fatoração de n (então os pi são primos distintos). Calcular todos osdivisores de zero em Z{nZ.

• Calcular todos os divisores de zero em Z{360Z.

Exerćıcio 149. Seja pA,`, ¨q um anel comutativo, com elementos neutros 0 e 1. Um elemento a P A se diznilpotente se e somente se ak “ 0 por algum k P N˚.

• Provar que um elemento nilpotente a é necessariamente divisor de zero.

• Provar que Z{nZ tem divisores de zero se e somente se na fatoração de n “ pα11 ¨ ¨ ¨ pαrr , com pi primosdistintos, algum primo pi aparece com potencia αi ě 2.

• Provar que um elemento Z{nZ tem elementos nilpotentes se e somente se n é diviśıvel por um quadradode um primo. Os n que não satisfazem esta condição de dizem privos de quadrados.

• Calcular todos os nilpotentes em Z{360Z.

Exerćıcio 150. Seja pA,`, ¨q um anel comutativo, com elementos neutros 0 e 1. Um elemento a P A se dizidempotente se a2 “ a. Provar que 0 e 1 são idempontentes (chamados idempotentes triviais). Provar quese a é idempotentes, então 1´ a é idempotente.

O objetivo deste exercicio é encontrar (ou pelo menos compreender) todos os idempotentes em Z{nZ.

• Seja n “ pα11 ¨ ¨ ¨ pαrr , com r ą 0, αi ą 0. Consideramos o isomorfismo de aneis

pf : Z{nZ - Z{pα11 Zˆ ¨ ¨ ¨ ˆ Z{pαrr Z .

que associa rxsn - prxspα11 , . . . , rxspαrr q. Provar que se rasn é idempotente, então raspαii é idempotenteem Z{pαii Z, por todos os i “ 1, . . . , r.

• Provar que Z{pαii contém só idempotentes triviais.

• Deduzir o número de idempotentes em Z{nZ.

• Calcular todos os idempotentes em Z{360Z.

Exerćıcio 151. Sejam m1, . . . ,mk P N, a dois a dois coprimos. Sabemos do teorema Chinês do resto queha um isomorfismo de aneis

pf : Z{m1 ¨ ¨ ¨mkZ - Z{m1Zˆ ¨ ¨ ¨ ˆ Z{mkZ ,

simplesmente dado por rxsm1¨¨¨mk - prxsm1 , . . . , rxsmkq. O objetivo deste exercicio é encontrar explicita-mente a inversa de pf .

22

• Indicamos com xmi :“ m1 ¨ ¨ ¨mi´1mi`1 ¨ ¨ ¨mk “ pm1 ¨ ¨ ¨mkq{mi. Provar que pxmi,miq “ 1. Deduzir queexistem αi, βi P Z tais que xmiαi `miβi “ 1.

• Seja

gpry1sm1 , . . . , rysmkq :“ rkÿ

i“1yiαixmisn .

Provar que g é uma função bem definida

g : Z{m1Zˆ ¨ ¨ ¨ ˆ Z{mkZ - Z{m1 ¨ ¨ ¨mkZ .

• Provar que g é inversa de pf .

Milies-Coelho: Seção 3.4: exerćıcios 1 - 7.

Seção 3.5: exercicios 1 - 16. Seção 3.6: exercicios 1 - 14.

Capitulo 3: exercicios suplementares: 15 - 20.

Exerćıcio 152. Calcular, por cada n P N˚, pn´ 1q! mod n.

Exerćıcio 153. Seja G um grupo e sejam g, h P G tais que ordGpgq e ordGphq sejam finitos. Supomostambém que gh “ hg e que pordGpgq, ordGphqq “ 1. Mostrar que ordGpghq “ ordGpgq ¨ ordGphqs.

Exerćıcio 154. Seja G um grupo ćıclico gerado por g P G. Supomos que G é finito de ordem m. Provarque qualquer outro gerador de G é da forma gs, com s P N˚, ps,mq “ 1.

Exerćıcio 155. Provar que se G é um grupo com p elementos, p P N, p primo, então G é ciclico, gerado porqualquer elemento g P G, g ‰ e.

Exerćıcio 156. Seja G um grupo ciclico (finito ou infinito), gerado por g P G. Seja H um seu subgrupo.Seja t “ mintn P N˚ | gn P Hu. Provar que H é ćıclico gerado por gt. Provar que t � m. Deduzir que hauma correspondencia biunivoca entre os divisores positivos de m e os subgrupos de G.

Exerćıcio 157. Seja G um grupo ćıclico finito (de ordem m) gerado por g P G. Seja d P N˚. Provar que oconjunto

Ad “ tx P G | xd “ 1u

é subgrupo de G. Quantos elementos tem Ad? Qual é o seu indice rG : Ads em G?

Exerćıcio 158. Seja µn “ tz P C | zn “ 1u. Provar que é um subgrupo ćıclico de pC˚, ¨q. Calcular |µn|.Dica: usar a notação z “ ρeiθ para o número complexo z P C˚, onde ρ P Rą0 e θ P R. É bem conhecido queeiθeiϕ “ eipθ`ϕq (se não sabe, provar! usando que eiθ “ cos θ ` i sin θ).

Exerćıcio 159. Sejam Cm e Cn dois grupos ćıclicos finitos, de ordem m e n, respectivamente. Podemos

considerar o grupo produto cartesiano CmˆCn com a estrutura produto (onde a operação é feita componentepor componente). Provar que Cm ˆ Cn, com esta estrutura, é ćıclico se e somente se pm,nq “ 1.

Exerćıcio 160. É verdade ou uma falsidade dizer que @n P N˚, n ě 2, UpZ{nZ, ¨q é ćıclico?

Exerćıcio 161. Encontrar todos os inteiros x (se existem) tais que$

’

’

’

’

’

’

&

’

’

’

’

’

’

%

r7s7x20 “ r3s20

r8s23x49 “ r43s49

r11s5x56 “ r43s56

.

Dica: encontrar, antes de tudo as ordens multiplicativas de r7s20, r8s49, r11s56. Uma calculadora pode ajudar.

23