Embed Size (px)
Citation preview
Ementa detalhada até agora
23 de Novembro de 2017
1. (31/07: Aula 1): Definição informal de produto cartesiano, função, relação (como função de AxB´ ąV, F ), operação interna a um conjunto. Descrição Axiomaticas de Z: Estrutura de dominito comutativo:soma: associatividade, elemento neutro 0, oposto, comutatividade; produto: associatividade, elementoneutro 1, Lei de Anulação de um produto; comutatividade. Propriedade Distributiva. Consequenciasdos axiomas de grupo aditivo: unicidade do 0, unicidade do oposto, notação do oposto ´a de a; lei decancelação aditiva, ´p´aq “ a;. Consequecias dos axiomas de anel: unicidade do elemento neutro 1,a ¨ 0 “ 0; regra dos sinais, p´1q ¨ a “ ´a.
2. (02/08: Aula 2): A Lei de Anulação do produto é equivalente à Lei de Cancelação para o produto.A comutatividade da soma é um axioma dependente dos outros axioma de anel. Relação de ordemem Z e estrutura de dominio comutativo: a relação ď é reflexiva, simétrica, transitiva; a ordem étotal. Simbolos: ď,ě,ă,ą,ň,ŋ. Não todas as relações de ordem são totais: exemplo (informal)da divisibilidade em N˚). A ordem ď de Z é compativel com a adição e com o produto (obs: umadisegualdade é respeitada quando se soma um inteiro qualquer e quando se multiplica para um número. Lei da trichotomia (a ă b, a ą b, a “ b). Variante equivalente só com a “ 0, a ă 0, a ą 0. A Leida trichotomia é equivalente, se a ordem é compativel com a soma, com a totalidade da ordem. a ě 0
sse ´a ď 0; a2 ě 0; 1 ě 0. a ď b, c ď 0 implica que ac ě bc. Temos que postular como axioma que1 ‰ 0 (se não Z “ 0). Então 1 ą 0. Definição de máximo e mínimo para um subconjunto A de Z (oupara um conjunto parcialmente ordenado). Não todos conjuntos ou subconjuntos admitem máximo oumínimo (exemplos de 0 ă x ă 1 em Q ou R). Se A admite máximo, então A não é vazio. Unicidade domáximo e mínimo quando existem. Definição de conjunto bem ordenado: é um conjunto totalmenteordenado tal que qualquer seu subconjunto não vazio tem mínimo. Princípio da Boa Ordenação: oconjunto de inteiros não negativos é bem ordenado com a ordem ď. O princípio da Boa Ordenação nãoval para Q ou R (que são dominio comutativos ordenados). Resumo das propriedades axiomaticas deZ: Existe um único (veremos mais a frente o que isto quer dizer) domínio comutativo ordenado Z talque o conjunto dos seu elementos não negativos seja bem ordenado. Não confundir o Princípio da BoaOrdenação com o Teorema de Boa Ordenação (que diz que em qualquer conjunto não vazio X podemosdar uma ordem total tal que X seja bem ordenado: o Teorema da Boa Ordenação é extremamentepotente e equivalente ao Axioma da Escolha: este Axioma é posto em forte discussão (e removido) pelaescola de Lógica Intuicionista, porquê leva a demonstrar fatos bem surprendentes, como o paradoxo deBanach-Tarski).Exercicio: dar uma boa ordenação em Z (é claro que esta boa ordenação não vai poderser compativel com as operações).
3. (07/08: Aula 3): Comparação entre máximos e mínimos de um conjunto A e do conjunto dos opostos´A; (minA “ ´maxp´Aq, etc...); deduzimos, da unicidade do mínimo, a unicidade do máximo. Cotassuperiores, inferiores; (sub)conjuntos de Z limitados inferiormente, superiormente.
1
Proposition 0.0.1. Todo subconjunto não vazio de Z limitado inferiormente admíte mínimo.
Proposition 0.0.2. Todo subconjunto não vazio de Z limitado superiormente admíte mínimo.
Observação 1. A proposição acima é falsa em Q e em R, mas em R admite um analogo (que na verdadeé um axioma importante), substituendo o conceito de max (ou min) com inf e sup; inf = máximo doconjunto das cotas inferiores; sup = mínimo do conjunto das cotas superiores.
Observação 2. Temos que a proposição acima implica o PBO. A proposição acima, mesmo se parecemais geral do principio de Boa Ordenação, é, na verdade equivalente. De fato conseguimos prova-la apartir do PBO.
Consequencias da boa ordenação.
Proposition 0.0.3. Não ha inteiros estritamente maiores de 0 e estritamente inferiores a 1.
Corolário 1. Não ha inteiros estritamente maiores de n e estritamente inferiores a n` 1.
Corolário 2. Se m ą n, então m ě n` 1. Se m ă n, então m ď n´ 1.
Observação 3. O corolário acima nos faz compreender como os inteiros sejam um conjunto discreto(sentido informal), no sentido que "saltam": coisa que não acontece em Q ou R em outras palavras,por cada n P Z, permite de definir o "sucessor"de n, ou seja, o mínimo inteiro m tal que m ą n:
n` :“ mintm P Z |m ą nu “ n` 1
(necessariamente) O conceito de "sucessor"é fundamental na descrição axiomatica de N “ Zě dadapor Peano, na qual se assume como conceito primitivo.
Proposition 0.0.4 (Propriedade Arquimedeana). Sejam a, b P Z, a ą 0. Então existe n P N˚ tal quena ą b.
Demonstração. Se fosse na ď b por cada n P N, então, dado que a ě 1, teriamos que n ď na ď b, porcada n e N seria superiormente limitado (teria b como cota superior), e teria maximo...abs.
Valor absoluto, definição |a| “ max a,´a. Propriedades |a| ě 0, |a| “ 0 ðñ a “ 0; ´|a| ď a ď |a|,| ´ a| “ |a|; |ab| “ |a||b|; |a` b| ď |a| ` |b|; ||a| ´ |b|| ď |a´ b|.
Definição 1. Seja a P Z. Dizemos que a é inversível (multiplicativamente) se existe b P Z tal queab “ pbaq “ 1. Indicamos com UpZ, ¨q o subconjuntos dos inversíveis de Z.
Observação 4. A definição acima se pode dar em geral para um monóide; de fato ele faz intervir só aestrutura de monoide multiplicativo do anel Z.
Observação 5. Se a é inversível, então a ‰ 0. (Isto não se pode dizer na generalidade de um monóidemultiplicativo, porque só temos o elemento neutro 1).
Proposition 0.0.5. UpZ, ¨q “ t1,´1u.
4. (09/08: Aula 4) A disegualdade |a||b| ě |b| fornece outra demonstração para a propriedade aquimedeana(exercicio). Se a, b P UpZ, ¨q, então ab P UpZ, ¨q. Em geral, se pM, ¨q é monoide multiplicativo, então oconjunto UpM, ¨q dos inversíveis de M é um grupo.
Principio de Indução Matemática: é uma caraterística fundamental do conjunto N, tanto que é assumidocomo axioma na axiomatização de N dada por Peano. Vamos ver isto mais a frente. Temos a primeiraversão
2
Teorema 1 (Principio de Indução Matemática). Seja S Ď N tal que
• 0 P S;
• por cada n P N, se n P S, então n ` 1 P S (ou seja, mais formalmente p@n P Nqppn P Sq ùñpn` 1 P Sqq).
Então S “ N.
Demonstração. Via o Princípio da Boa Ordenação
Observação 6. O Princípio de Indução Matemática diz que os naturais N são o mínimo conjunto talque 0 P N, se n P N, então o sucessor n` P N.
Exemplo 1. Esemplo de aplicação do PIM à demonstração deřnk“0 k “
npn`1q2 .
Observação 7. O PIM não tem nada a ver com a indução empirica. Exemplos: consideramos apropriedade n2 ă 600n`503. Por n “ 0, . . . , 600, a propriedade é verdadeira, e poderiamos ser tentadosde concluir que val para todos, mas já não val para n “ 601. Consideramos a função ϕpnq´n2´n`41
e o predicado, P pnq : ϕpnq é primo. É verdadeiro para n “ 0, . . . , 40, e então poderiamos ser tentadosde concluir que é verdadeiro para todo n. Mas não, por n “ 41, se ve logo que ϕp41q “ 412, que nãoé primo. Para provar um fato, não podemos nunca deduzir a sua verdade, ou a sua prova, de umaverifica de muitos casos particulares.
Observação 8. Existem subconjuntos S de Qě0 que verificam 0 P S, n P S, então n ` 1 P S, masS ‰ Qě0, e nem S ‰ N.
Demos a versão do princípio de Indução com predicados. Do ponto de vista da lógica matemática, umaproposição é uma afirmação declarativa tal que o seu valor lógico (verdade ou falsidade) é completa-mente determinado. Um predicado P pxq, interpretado num conjunto A, é uma familia de proposições,uma por cada x P A, ou seja, em outras palavras, uma função P : A - tProposiçõesu. Temos oseguinte importante axioma da teoria dos conjuntos (axioma da pertinencia restrita): Dado um con-junto A e um predicado interpretado em A, P : A - tProposiçõesu, então a coleção de objetosB :“ tx P A | P pxq “ V u é um conjunto1. Consideramos agora A “ N, e P pnq é um predicadointerpretado em A (uma propriedade que faz sentido em n), então o conjunto
S “ tn P N | P pnq “ V u
é um conjunto. Temos que m P S ðñ P pmq “ V . Com isto explicado,
Teorema 2 (Principio de Indução Matemática). Seja P pnq uma propriedade (afirmação) definida emN. Supomos que
• P p0q “ V
• por cada n P N, se P pnq “ V , então P pn` 1q “ V . (ou seja, mais formalmente p@n P NqpP pnq “V - P pn` 1q “ V q.
1Não é a mesma coisa se consideramos o axioma da pertinencia irrestrita, que diz a coisa seguinte: por cada predicado P pxq(por cada propriedade P pxq), a coleção de objetos B “ tx | P pxqu é um conjunto. Este axioma, que aparecia no tratado de teoriados conjuntos de Frege, foi completamente destroido por Russel, com o seu paradoxo, que se pode formular na maneira seguinte:consideramos o predicado P pxq “ xé um conjunto, então, por o axioma da pertinencia irrestrita, o conjunto B “ tx | P pxqu éo conjunto de todos os conjuntos. Consideramos agora C “ tx P B |x R xu. Então C é um conjunto (por pertinencia restrita,neste caso). Mas as proposiçõs C P C e C R C não podem ser nem verdadeiras nem falsas. Absurdo.
3
Então P pnq “ V por cada n P N. (ou seja p@n P NqpP pnq “ V q)
Exemplo: provar que pn` 4q! ě 2n`4 por indução.
Valem facilemente estas variantes, a partir de um subconjunto de Z, inferiormente limitado.
Teorema 3 (Principio de Indução Matemática). Seja c P Z e S Ď Zěc tal que
• c P S;
• por cada n P Zěc, se n P S, então n ` 1 P S (ou seja, mais formalmente p@n ě cqppn P Sq ùñ
pn` 1 P Sqq).
Então S “ Zěc.
Teorema 4 (Principio de Indução Matemática). Seja c P Z e seja P pnq uma propriedade (afirmação)definida em Zc. Supomos que
• P pcq “ V
• por cada n P Zěc, se P pnq “ V , então P pn ` 1q “ V . (ou seja, mais formalmente p@n ěcqpP pnq “ V - P pn` 1q “ V q.
Então P pnq “ V por cada n ě c. (ou seja p@n ě cqpP pnq “ V q)
Exemplo de possíveis erros. No passo indutívo é sempre preciso deixar o n livre de correr em N, ou emZěc (dependentemente dos casos). Por exemplo, é facil dar uma demonstração errada de 4n2 ě 8n´ 3
se no passo indutívo tomamos n ě 1.
5. (14/08: Aula 5). Exemplo de póssivel erro em que o passo indutívo p@nqpP pnq Ñ P pn` 1qq é sempreverdadeiro, mas onde o caso base P p0q não é verdadeiro e P pnq é sempre falsa.
Duas imagens mentais para o principio de indução matemática: a imagem do "domino": em que o passoindutívo significa que as peças são bem posta (se cai a n-esima, então cai a n` 1 esima); o caso baseque significa que a primeira (a 0-esima) de fato cai; e entào vão cair todas. Segunda imagem: vemosP pnq como rochas em principio separadas uma da outra. O passo indutívo significa que existe umaponte entre a n-esima e a n`1-esima. O caso base é que de fato se parte da 0-esima. Aprofundamentológico da primeira imagem: regras de dedução; modus ponens: se p, q são proposições, então val a regrade dedução (tautologia):
p
p - q
,
/
.
/
-
ùñ q
ou seja, se sabemos que p implica q e temos de fato p, então temos q. O efeito "domino"do principio deindução pode ser re-interpretado com o modus ponens (que é a dedução lógica subjacente, o mecanismológico subjacente) da forma seguinte: assumir p@nqpP pnq Ñ P pn`1qq significa assumir todas as infinitasproposições
P p0q - P p1q
P p1q - P p2q
P p2q - P p3q
P p3q - P p4q
. . .
,
/
/
/
/
/
/
.
/
/
/
/
/
/
-
4
Do outro lado temos que assumir também P p0q (caso base). Então, no final, assumimos:
P p0q
P p0q - P p1q
P p1q - P p2q
P p2q - P p3q
P p3q - P p4q
. . .
,
/
/
/
/
/
/
/
/
.
/
/
/
/
/
/
/
/
-
Mas então, uma aplicação sucessíva do modus ponens da:
P p0q
P p0q - P p1q
P p1q - P p2q
P p2q - P p3q
P p3q - P p4q
. . .
,
/
/
/
/
/
/
/
/
.
/
/
/
/
/
/
/
/
-
ùñ
P p0q
P p1q
P p1q - P p2q
P p2q - P p3q
P p3q - P p4q
. . .
,
/
/
/
/
/
/
/
/
.
/
/
/
/
/
/
/
/
-
ùñ
P p0q
P p1q
P p2q
P p2q - P p3q
P p3q - P p4q
. . .
,
/
/
/
/
/
/
/
/
.
/
/
/
/
/
/
/
/
-
ùñ
P p0q
P p1q
P p2q
P p3q
P p3q - P p4q
. . .
,
/
/
/
/
/
/
/
/
.
/
/
/
/
/
/
/
/
-
e se continuassemos até o infinito, daria todas as P pnq. Obviamente este raciocinio é só euristico enão tem validade formal, porque quando se passa n arbitrariamente grande não temos controlo lógicosobre o que estamos fazendo, e na verdade, estamos usando indução empirica.
De uma certa forma o princípio de induçào permite evitar esta "passagem ao infinito"ou seja, ospontinhos...
Prinçipio de Indução Forte: As vezes as peças do domino não são postas linearmente, mas a disposiçãoé mais complicada, e o que faz diretamente cair a peça n` 1-esima não é necessariamente a n-esima,mas pode ser uma peça k-esima, com k ă n. Temos o
Teorema 5 (Principio de Indução Forte). Seja S Ď N tal que
• 0 P S;
• p@n P Nqpt0, . . . , nu Ď S ùñ n` 1 P Sq
Então S “ N.
Obviamente temos a versão com predicados
Teorema 6 (Principio de Indução Forte). Seja P pnq um predicado definido (interpretado) em N.Supomos que
• P p0q• p@n P NqpP p0q ^ P p1q ^ ¨ ¨ ¨ ^ P pnq ùñ P pn` 1qq
Então p@n P NqpP pnqq.
Demonstração a partir do principio de induçao estandard aplicado ao conjunto T “ tn P N t0, . . . , nu ĎSu.
Explicação do porquê se chama de Indução forte. Em lógica, uma proposição A se diz mais forte deuma proposição B se A ùñ B. Temos que se A é mais forte do que A1, então A1 ùñ B é mais fortedo que A ùñ B. A estrutura do principios de Indução (PIM) e Indução Forte (PIF) é
PIM :1q
A ùñ B
+
ùñ C , PIF1q
A1 ùñ B
+
ùñ C
5
com A1 ùñ A. Mas então pA ùñ Bq ùñ pA1 ùñ Bq e então
1q
A ùñ B
+
ùñ1q
A1 ùñ B
+
e então˜
1q
A1 ùñ B
+
ùñ C
¸
ùñ
˜
1q
A ùñ B
+
ùñ C
¸
ou seja PIF ùñ PIM. Isto quer dizer que PIF é mais forte do que PIM.
Enunciar e demonstrar as versões transladadas por exercicio.
Exemplo: mostrar que todo inteiro n maior ou igual a 12 se pode escrever como n “ 4k ` 5l, pork, l P N.
6. (16/08: Aula 6) Equivalencia entre PBO, PIM, PIF (ver notas separadas). Definições por recursão.
Teorema 7. Seja S um conjunto e seja ϕ : S - S uma função e a0 P S um elemento fixado. Entãoexiste uma única função f : N - S tal que
• fp0q “ a0;
• p@n P Nqpfpn` 1q “ ϕpfpnqqq
Exemplo do fatorial n! e an.
7. (21/08: Aula 7) Considerações e exemplo sobre o teorema de recursão.
Divisibilidade: definição. Unicidade do quociente no caso o divisor não seja zero. Zero só divide zero.Em Z (ou em qualquer domínio comutativo) não existem divisores de zeros não triviais com quocientenão trivial. Comparação entre relação de divisibilidade e ordem (se a � b, então |a| ď |b|). Definição:a, b são associados se a � b e b � a. Prop: a „ b (a associado a b) se e somente se existe u P UpZ, ¨q talque a “ bu (mesmo que a “ 0, b “ 0). Corolário. a „ b se e somente se a “ ˘b. Varias propriedadesda relação de divisibilidade (reflexiva, transitiva, compatibilidade com soma e produto, e combinaçõeslineares inteiras).
Teorema 8 (Algoritmo da Divisão Euclidiana). Se a, b P Z, b ą 0, então existem únicos q, r P Z taisque
• a “ bq ` r
• 0 ď r ň |b|
Demonstração. Existencia: Caso a ě 0, b ą 0 demonstrado em duas maneiras: I, via PBO, II, comindução forte. Extensão (trivial ou quase) aos outros casos.
Obs: falta de unicidade se prescrevemos só : 0 ď |r| ň |b|.
8. 28/08, aula 8
Demonstração da unicidade da divisão euclidiana (com resto 0 ď r ň |b|). Variante do princípio deIndução forte
6
Teorema 9 (Principio de Indução forte, variante). Sejam c1, c2 P Z e seja P pnq um predicado definidoem Zěc1 . Supomos que
• P pc1q “ V, . . . , P pc2q “ V .
• p@n ą c2qpp@i P Z, c1 ď i ă n, P piq “ V q - P pnqq
Então p@n ě c1qpP pnq “ V q
Esta versão do principio de indução forte se pode reformular em palavras assim Seja P pnq um predicadodefinido em Zěc1 . Supomos que uma certa quantidade de casos base seja verificada, ou seja P pc1q “V, . . . , P pc2q “ V . Seja agora n ą c2; supomos que P piq “ V seja verificada por cada i ă n ( e, claro,i ě c1), e supomos que desta hipótese se possa concluir que P pnq “ V . Então P pnq “ V por cadan ě c1.
Teorema 10 (Numeração em base b). Seja b P N, b ě 2. Por cada n P N˚ existem únicos m P N eα0, . . . , αm P N, tais que
• n “ αmbm ` αm´1b
m´1 ` ¨ ¨ ¨ ` α1b` α0;
• 0 ď αi ă b
• αm ‰ 0.
Demonstração. Demonstração da existencia por indução forte considerando como casos bases todos os1 ď j ď b ´ 1. Passo indutívo por n ě b escrevendo a divisão euclidiana n “ bn1 ` α0 e aplicando oteorema para n1 ă n. Unicidade usando a unicidade da divisão euclidiana e o passo indutívo.
Exemplos.
9. 30/08: aula 9
Definição 2. Sejam a, b P Z. Dizemos que um inteiro d P Z é um máximo divisor comum de a e b se
•
#
d � a
d � b
• Se c P Z,
#
c � a
c � bùñ c � d
Observação 9. Se d1, d2 são dois máximos comuns divisores de a e b, então d1 „ d2.
Indicamos um dos mcd(a,b), se existe, com pa, bq.
Observação 10. Dados a, b P Z, existe ao máximo um único máximo divisor comum não negatívo dea, b. (Vamos ver que sempre existe).
Exemplo 2. p0, 0q “ 0; pa, 0q “ a; pa, 1q “ 1.
Definição 3. Sejam a, b, a1, . . . , an, k P Z. Definimos os seguintes subconjuntos de Z:
kZ :“ tkx | x P Zu multiplos inteiros de k
aZ` bZ :“ tax` by | x, y P Zu combinações lineares inteiras de a, b
a1Z` ¨ ¨ ¨ ` anZ :“ ta1x1 ` ¨ ¨ ¨ ` anxn | x1, . . . , xn P Zu combinações lineares inteiras de a1, . . . , an
7
Observação 11. O conjunto kZ verifica as propriedades
• 0 P kZ;
• z, w P kZ ùñ z ` w P kZ;
• z P kZ ùñ ´z P kZ
• z P kZ, α P Z ùñ αz P kZ.
Analogamente o subconjunto a1Z` ¨ ¨ ¨ ` anZ verifica as propriedades
• 0 P a1Z` ¨ ¨ ¨ ` anZ;
• z, w P a1Z` ¨ ¨ ¨ ` anZ ùñ z ` w P a1Z` ¨ ¨ ¨ ` anZ;
• z P a1Z` ¨ ¨ ¨ ` anZ ùñ ´z P a1Z` ¨ ¨ ¨ ` anZ
• z P a1Z` ¨ ¨ ¨ ` anZ, α P Z ùñ αz P a1Z` ¨ ¨ ¨ ` anZ.
Definição 4. Um subconjunto I Ď Z é chamado um subgrupo aditivo de Z (ou um subgrupo do grupoaditivo pZ, 0,`q) se
• 0 P I
• z, w P I, ùñ z ` w P I;
• z P I ùñ ´z P I.
Um subgrupo aditivo I de Z é chamado um ideal de Z, se val também a propriedade
• z P I, α P Z, ùñ αz P I.
(A definição val por qualquer anel comutatívo).
Observação 12. Os conjuntos kZ e, mais em geral a1Z` ¨ ¨ ¨ ` anZ são ideais de Z.
Proposição 1. Seja I um subconjunto de Z. Então I é um ideal de Z se e somente se
• I ‰ H;
• z, w P I ùñ z ` w P I;
• z P I, α P Z, ùñ αz P I.
Observação 13. Temos as seguintes traduções em termos de ideais:
• a � b ðñ bZ Ď aZ;
• a „ b ðñ aZ “ bZ;
• u P UpZ, ¨q ðñ uZ “ Z.
Definição 5. Um ideal I de Z se diz principal se é da forma I “ kZ, por algum k P Z. Neste casoI “ kZ se diz ideal principal gerado por k.
Teorema 11. Todo ideal I de Z é principal. [Z é domínio a ideais principais.]
10. 04/08: aula 10:
8
Teorema 12 (Teorema de Bézout). Sejam a, b P Z. Então existe d “ pa, bq. Além disso, val a relação
aZ` bZ “ dZ .
Em particular existem x0, y0 P Z tais que
d “ ax0 ` by0 .
Observação 14. Sejam a1, . . . , an P Z. Existe maxta1, . . . , anu: dem: mostrar que o elemento
maxtmaxta1, . . . , an´1u, anu
é o maxta1, . . . , anu. Analogamente, existe minta1, . . . , anu e val uma parecida relação recursiva.
Observação 15. Sejam a1, . . . , an. Temos que
b ě ai@i ðñ b ě minta1, . . . , anu
b ď ai@i ðñ b ď maxta1, . . . , anu
Dj0 | b ě aj0 ðñ b ě minta1, . . . , anu
Dj0 | b ď aj0 ðñ b ď maxta1, . . . , anu .
Observação 16. Sejam a, b P Z, tais que pelo menos um dois dois seja não zero. Indicamos com Dpa, bq
os divisores comuns de a e b. Temos que Dpa, bq é um conjunto limitado seja superiormente sejainferiormente. (Se c � a, c � b, então |c| ď |a|, |c| ď |b|, ou seja |c| ď mint|a|, |b|u. Mais em geral sea1, . . . , an são inteiros não todos zeros, Dpa1, . . . , anq é limitado superiormente e inferiormente.
Teorema 13. Sejam a, b P Z, não os dois zero. Então se d “ pa, bq, temos que |d| “ maxDpa, bq.
Definição 6. Definição de mdc para a1, . . . , an.
Observação 17. Se d1, d2 são mdc para a1, . . . , an então d1 „ d2.
Teorema 14 (Teorema de Bézout). Sejam a1, . . . , an P Z. Então existe d “ pa1, . . . , anq. Além disso,val a relação
a1Z` ¨ ¨ ¨ ` anZ “ dZ .
Em particular existem x1, . . . , xn P Z tais que
d “ a1x1 ` ¨ ¨ ¨ ` anxn .
Proposição 2. Sejam a1, . . . , an inteiros. Val a seguinte relação recursiva:
pa1, . . . , anq “ ppa1, . . . , an´1q, anq .
Teorema 15. Sejam a1, . . . , an inteiros não todos zero. Se d “ pa1, . . . , anq temos que |d| “ maxDpa1, . . . , anq.
Teorema 16. Sejam a1, . . . , an inteiros. São equivalentes.
d “ pa1, . . . , anq
a1Z` ¨ ¨ ¨ ` anZ “ dZ
d “ ppa1, . . . , an´1q, anq
9
|d| “ maxDpa1, . . . , anq
11. (06/09: aula 11).
Lema 1 (Lema de Euclides). Sejam a, b P Z. Supomos que
a “ bq ` r
por algum q, r P Z. Entãopa, bq “ pb, rq .
Demonstração. Demonstração via a definição de máximo divisor comum e via Dpa, bq “ Dpb, rq.
Aplicação do lema de Euclides para o cálculo de pa, bq e de coefficientes x0, y0 tais que d “ ax0 ` by0.
Teorema 17 (Algoritmo de Euclides). Sejam a, b P Z, com b ‰ 0. Existem n P N, r0, . . . , rn`1 P Z,q0, . . . , qn P Z tais que
• r0 “ |b|, rn`1 “ 0; rn ‰ 0;
• a “ |b|q0 ` r1, rj´1 “ rjqj ` rj`1 for all j “ 1, . . . , n, 0 ď rj`1 ă rj, for all j “ 0, . . . , n.
• rn “ pa, bq.
Além disso, a algoritmo da uma maneira construtiva para encontrar x0, y0 tais que d “ ax0 ` by0.
Demonstração. Indução forte sobre |b| ě 1.
Exemplos.
Lema 2. Seja u P UpZ, ¨q. Se c � u, então c P UpZ, ¨q.
Proposição 3. Sejam a, b P Z, não os dois nulos e seja d “ pa, bq. Seja a “ a1d, b “ b1d. Entãopa1, b1q „ 1.
Demonstração. É claro que d ‰ 0, porque se não os dois a “ 0 “ b. Seja c P Z tal que#
c � a1
c � b1.
Então a “ a1d “ a2cd, b “ b1d “ b2cd. Mas então cd � a, cd � b e então cd � d. Dado que d ‰ 0, temosc � 1. Mas então c é inversível. Isto mostra que todos os divisores comuns de a1, b1 são inversíveis.Então pa1, b1q é inversível, ou seja pa1, b1q „ 1.
Proposição 4. Sejam a, b, c P Z. Temos pac, bcq “ cpa, bq.
Demonstração. O teorema é trivial no caso a “ 0 “ b (ou seja pa, bq “ 0, ou c “ 0). Supomos entãoque d :“ pa, bq ‰ 0 e c ‰ 0. Seja d :“ pa, bq, e “ pac, bcq. Temos que provar que cd „ e. De um ladotemos
#
d � a
d � bùñ
#
cd � ac
cd � bcùñ cd � e .
Escrevemos então e “ cde1. É suficiente provar que e1 é um inversível. Escrevemos a “ a1d, b “ b1d.Lembramos que pa1, b1q „ 1. Então ac “ a1cd, bc “ b1cd. Mas ac “ eα, bc “ eβ, e então ac “ cde1α,
10
bc “ cde1β. Mas então a “ de1α, b “ de1β, ou seja a1d “ de1α, b1d “ de1β, e por a lei de cancelação,dado que d ‰ 0: a1 “ e1α, b1 “ e1β. Mas então e1 � a1, e1 � b1, mas então e1 � pa1, b1q „ 1. Isto implicaque e1 é inversível, e que, entào cd „ e.
Teorema 18 (Teorema de Euclides). Sejam a, b, c P Z. Temos que#
a � bc
pa, bq „ 1ùñ a � c .
Demonstração I. É claro que a � ac (por definição), a � bc (por hipótese). Então a � pac, bcq “ cpa, bq “
c, porque pa, bq „ 1.
Demonstração II. Temos que a � c se e somente se pa, cq „ a. Mas
pa, cq „ pa, cpa, bqq „ pa, pac, bcqq „ ppa, acq, bcq „ pa, bcq „ a
porque a � bc.
Demonstração III. Se pa, bq “ 1, então existem x0, y0 P Z tais que ax0 ` by0 “ 1. Mas então, multipli-cando por c, apcx0q ` bcy0 “ c. Mas agora bc “ at, porque a � bc. Então
apcx0q ` aty0 “ c
e então a � c.
Definição 7. Um inteiro p P Z, p ‰ 0, p não inversível (p ‰ ˘1) se diz primo se
@a, b P Z p � ab ùñ pp � aq _ pp � bq .
Definição 8. Um inteiro p P Z, p ‰ 0, p não inversível (p ‰ ˘1) se diz irredutível se
@a, b P Z, p “ ab ùñ pa P UpZ, ¨qq _ pb P UpZ, ¨qq .
Lema 3. Seja p P Z, p irredutível e a P Z tal que p ffl a. Então pp, aq „ 1.
Demonstração. Seja d “ pp, aq. Temos p “ dp1, com d � a. Se d 1, então p1 „ 1 e necessariamentep „ d, mas d � a, então p � a, o que é absurdo. Então d „ 1.
Teorema 19. Em Z p é primo se e somente se p é irredutível.
Demonstração. “ ùñ ". Seja p “ ab. Dado que p é primo, então p � a ou p � b. Supomos que p � a.Então a “ a1p. Mas então p “ ab “ a1bp. Mas então, por a lei de cancelação, 1 “ a1b e b P UpZ, ¨q. Sep � b a demonstração é analoga.
“ð”. Seja p irredutível. Supomos que p � ab e que p ffl a. Mas então pp, aq „ 1. Então p � b por oTeorema de Euclides. Então p é primo.
Observação 18. A prova de que se p é primo então p é irredutível é válida por qualquer domíniocomutatívo, enquanto a outra direção faz uso da existencia do mdc.
12. (11/09: aula 12)
11
13. (13/08: aula 13) Definição de injetividade, sobrejetividade, bijetividade para uma função f : A - B.Definição de composição de funções g ˝ f . Prova de que a composição de funções injetivas é injetiva,composição de funções sobrejetiva é sobrejetiva, e que então a composição de funções bijetivas é bijetiva.Prova de que se f : A - B é bijetiva, então existe uma única função g : B - A tal queg ˝ f “ idA, f ˝ g “ idB , chamada a inversa de f e denotada com f´1. Definição de permutação deum conjunto X. Definição do grupo simétrico pSpXq, ˝, idXq. O grupo simétrico sobre n elementos éSn :“ Spt1, . . . , nuq.
Lema 4. Sejam a1, . . . , an P Z. Então existe uma permutação σ P Sn tal que aσpiq ď aσpi`1q por cadai “ 1, . . . , n´ 1.
Demonstração. Por induçao sobre n, com n ě 2. Caso base: n “ 2. Dados a1, a2, se a1 ď a2, defina-seσ como idt1,2u e se a1 ě a2, defina-se σ como σp1q “ 2 e σp2q “ 1. É claro que σ faz o que queremos.
Passo Indutívo.
Lema 5. Sejam a1, . . . , an P Z, onde a1 ď a2 ď ¨ ¨ ¨ an´1 ď an. Então o produto a1 ¨ ¨ ¨ ¨ ¨ an se podeescrever como a1 ¨ ¨ ¨ ¨ ¨ an “ aα1
i1¨ ¨ ¨ ¨ ¨ aαr
ir, onde r P N, r ď n, aij ň aij`1 , por cada j “ 1, . . . , r ´ 1 e
αi P N˚.
Demonstração. Por indução sobre n, o número dos fatores. Caso base n “ 1. Só temos a1. Não ha nadapara mostrar (r “ 1, i1 “ 1, α1 “ 1). Passo indutívo. Supomos o teorema válido para n ě 1 e provamo-no para n ` 1. Consideramos o produto a1 ¨ ¨ ¨ ¨ ¨ an ¨ an`1, com a1 ď a2 ď ¨ ¨ ¨ an ď an`1. O produtoa1 ¨ ¨ ¨ ¨ ¨ an verifica as hipóteses do teorema, e, por indução, se escreve como a1 ¨ ¨ ¨ ¨ ¨ an “ aα1
i1¨ ¨ ¨ ¨ ¨ aαr
ir
onde r P N, r ď n, aij ň aij`1, por cada j “ 1, . . . , r ´ 1 e αi P N˚. Agora, o produto original
a1 ¨ ¨ ¨ ¨ ¨ an ¨ an`1 se escreve comoaα1i1¨ ¨ ¨ ¨ ¨ aαr
ir¨ an`1
onde, an`1 ě aij por cada ij , porque aij P ta1, . . . , anu e já sabiamos que an`1 ě an ě ¨ ¨ ¨ ě a1.Sabemos também que ai1 ‰ ai2 ň ¨ ¨ ¨ ň air e que então air é o maior de todos os aij . Entãoan`1 ě air . Agora temos duas possibilidades: ou an`1 “ air ou an`1 ŋ ar. Na primeira possíbilidade,o produto a1 ¨ ¨ ¨ an`1 se escreve
a1 ¨ ¨ ¨ an`1 “ aα1i1¨ ¨ ¨ ¨ ¨ aαr`1
ir.
Na segunda, pomos ir`1 “ n` 1 e αr`1 “ 1 e então o produto a1 ¨ ¨ ¨ an`1 se escreve
a1 ¨ ¨ ¨ an`1 “ aα1i1¨ ¨ ¨ ¨ ¨ aαr
ir¨ aαr`1
ir`1.
Corolário 3. Qualquer produto a1 ¨ ¨ ¨ ¨ ¨ an de números inteiros se pode escrever como a1 ¨ ¨ ¨ ¨ ¨ an “
aα1i1¨ ¨ ¨ ¨ ¨ aαr
ir, onde r P N, r ď n, aij ň aij`1
por cada j “ 1, . . . r ´ 1 e αi P N˚.
Exercício 1. Provar com a definição, que 2 e 3 são irredutíveis.
Teorema 20 (Teorema Fundamental da Aritmetica, versão I). Todo inteiro n P Z, n ‰ 0, se escrevede forma essencialmente única como produto
n “ up1 ¨ ¨ ¨ ¨ ¨ pr
onde
12
• r P N;
• u P UpZ, ¨q;
• pi são irredutíveis (primos).
A unicidade essencial significa que se n “ up1 ¨ ¨ ¨ ¨ ¨pr “ vq1 ¨ ¨ ¨ ¨ ¨qs, por algum v P UpZ, ¨q, e por algumqj irredutível, então r “ s e existe uma permutação σ P Sr tal que pi „ qσpiq — ou seja, qσpiq “ uipi
por algum ui P UpZ, ¨q — e vu1 ¨ ¨ ¨ur “ u.
Demonstração. Existencia. Por indução forte sobre |n| ě 1. Caso base: supomos |n| “ 1. Entãon P UpZ, ¨q. Posto u “ n e r “ 0, temos a decomposição n “ u do teorema. Fazemos o caso |n| “ 2.Então n é irredutível, e então primo, pelo exercício precedente. Posto u “ 1, temos a decoposiçãon “ 1 ¨ n, com u “ 1, r “ 1, p1 “ n como no enunciado do teorema.
Passo indutívo. Supomos agora |n| ą 2 e supomos que por cada k P Z, 1 ď |k| ň |n| o enunciado daexistencia da decomposição seja verdadeiro. Agora temos duas possibilidades: ou n é irredutível ou nnão é irredutível. Se n é irredutível, pomos u “ 1, r “ 1, p1 “ n e temos a decomposição n “ 1 ¨ n
como no enunciado do teorema. ..............
14. 18/09: aula 14.
Teorema 21 (Teorema Fundamental da Aritmética, versão 2). Todo inteiro n P Z, n ‰ 0 se escrevede forma única como produto
n “ up1 ¨ ¨ ¨ pr
onde
• r P N;
• u “ sgnpnq :“ n{|n|;
• pi são irredutíveis (primos) positívos;
• p1 ď p2 ď ¨ ¨ ¨ ď pr.
Demonstração. Existencia.Unicidade.
Teorema 22 (Teorema Fundamental da Aritmética, versão 2). Todo inteiro n P Z, n ‰ 0 se escrevede forma única como produto
n “ upα11 ¨ ¨ ¨ pαr
r
onde
• r P N;
• u “ sgnpnq :“ n{|n|;
• pi são irredutíveis (primos) positívos;
• p1 ň p2 ň ¨ ¨ ¨ ň pr: em particular pi são primos positivos distintos.
• αi P N.
13
Demonstração. Existencia.Unicidade
Definição 9. Chamamos os primos distintos pi que aparecem com expoente αi P N˚ na fatoração deum inteiro n os primos associados a n.
Lema 6. Sejam n,m dois inteiros diferentes de 0. Então existem p1, . . . , pr primos positivos distintostais que
n “ upα11 ¨ ¨ ¨ pαr
r
m “ vpβ1
1 ¨ ¨ ¨ pβrr
por αi, βi P N.
Demonstração. Fatoramos n como n “ utγ11 ¨ ¨ ¨ tγll onde ti são primos positivos distintos, l P N e
γi P N˚, e onde u “ sgnpnq. Fazemos a mesma coisa com m fatorando-no na forma m “ vzδ11 ¨ ¨ ¨ zδkk ,
onde zi são primos positivos distintos, k P N e δi P N˚, e onde v “ sgnpmq. Consideramos o conjuntoA “ tt1, . . . , tlu Y tz1, . . . , zku e o escrevemos como A “ tp1, . . . , pru por primos positivos distintos pi.Então teremos que
n “ upα11 ¨ ¨ ¨ pαr
r
m “ vpβ1
1 ¨ ¨ ¨ pβrr
onde αi “ 0 se pi R tt1, . . . , tlu e αi “ γh se pi “ th e onde βi “ 0 se pi R tz1, . . . , zku e βi “ δh sepi “ zh.
Observação 19. Observamos que os primos p1, . . . , pr que aparecem nas ambas as decomposições den e m são exactamente os primos associados ao produtos nm. É claro que o procedimento do lemaprecedente pode ser extendido a r inteiros n1, . . . , nk de forma de encontrar p1, . . . , pr primos reuniãodos primos associados às decomposições de n1, . . . , nk, ou, de forma equivalentes, os primos associadosao produto n1 ¨ ¨ ¨nk.
15. 20/08: aula 15
Proposição 5. Sejam a, b inteiros não núlos. Então a � b se e somente se, chamando p1, . . . , pr osprimos associados ao produto ab, e escrevendo as fatorações
a “ upα11 ¨ ¨ ¨ pαr
r
b “ vpβ1
1 ¨ ¨ ¨ pβrr
temos αi ď βi por cada i.
Teorema 23. Sejam a, b inteiros não núlos e sejam p1, . . . , pr os primos associados ao produto ab.Sejam
a “ upα11 ¨ ¨ ¨ pαr
r
b “ vpβ1
1 ¨ ¨ ¨ pβrr
as fatorações em primos distintos. Então
pa, bq „ pγ11 ¨ ¨ ¨ pγrr onde γi “ mintαi, βiu
ra, bs „ pδ11 ¨ ¨ ¨ pδrr onde δi “ maxtαi, βiu
14
Corolário 4. Sejam a, b inteiros não núlos. Temos que a � b se e somente se
@p P Z,@α P N p primo, pα � a ùñ pα � b .
Em particular a „ b se e somente se
@p P Z,@α P N p primo, pα � a ðñ pα � b .
Observação 20. O teorema acima se generaliza a n inteiros a1, . . . , an.
Proposição 6. Sejam a1, . . . , an, b inteiros. Temos as seguintes propriedades distributivas
pra1, . . . , ans, bq “ rpa1, bq, . . . , pan, bqs (1)
rpa1, . . . , anq, bs “ pra1, bs, . . . , ran, bsq (2)
Demonstração. Demonstramos a primeira. Seja p um primo e supomos que pα � pra1, . . . , ans, bq.Então, por definição de máximo divisor comum, pα � ra1, . . . , ans e pα divides b. Mas pα � ra1, . . . , ans
implica que pα � aj0 por um certo j0, porquê a máxima potencia de p que aparece em algum ai temque ser maior ou igual a α. Mas então pα � paj0 , bq e então divide rpa1, bq, . . . , pan, bqs.
Do outro lado, se pα � rpa1, bq, . . . , pan, bqs então tem que dividir um certo paj0 , bq, porque a máximapotencia de p que aparece nos diferentes pai, bq tem que ser maior ou igual a pα. Mas então pα � aj0 epα � b, mas então pα � ra1, . . . , ans e divide b e então divide pra1, . . . , ans, bq.
A segunda igualdade se demonstra analogamente.
Observação 21. As propriedade de distributividade do mdc e mcm relativamente um ao outro podemser expressas em termos de ideais nesta forma
pa1ZX ¨ ¨ ¨ X anZq ` bZ “ pa1Z` bZq X ¨ ¨ ¨ X panZ` bZq
pa1Z` ¨ ¨ ¨ ` anZq X bZ “ pa1ZX bZq ` ¨ ¨ ¨ ` panZ` bZq .
Cuidado: em geral a classe dos aneis tais que a soma de ideais distribui em relação à interseção é muitorestrita: val para aneis mais gerais do que Z, mas não é nada comum.
Teorema 24 (Euclides). Os números primos são infinitos.
Demonstração. Supomos por absurdo que exista só um número finito de primos tp1, . . . , pru, r ą 0,r P N. Consideramos o produto k “ |p1| ¨ ¨ ¨ ¨ ¨ |pr| ` 1. É claro (exercício) que k ŋ pi por cadai P t1, . . . , ru e que então k ‰ pi por cada i P t1, . . . , ru. Então k não pode ser primo. Temos tambémque k ŋ 1. Mas então k admite uma fatoração em primos k “ upα1
1 ¨ pαrr , com pelo menos um dos
αi ‰ 0 (se não teriamos k “ 1, o que vimos que não é). Mas então um dos pi, chamamos pj0 , divide k.Mas então pj0 divide 1. Mas então pj0 é inversível, o que é absurdo, porque pj0 é primo.
Equações Diofantinas.
Proposição 7. Sejam a, b, c P Z. Seja d “ pa, bq. Seja a “ a1d, b “ b1d. Sejam x0, y0 P Z tais queax0 ` by0 “ d. A equação diofantina
ax` by “ c
tem solução se e somente se d � c. Neste caso ela admite infinitas soluções. Uma destas soluções éx “ c1x0, y “ c1y0, onde c “ c1d. Todas e só as soluções da equação se escrevem como
#
x “ c1x0 ` b1t
y “ c1y0 ´ a1t
, t P Z .
15
Demonstração. Se a equação diofantina admite solução, então c P aZ ` bZ “ dZ, e então d � c. Dooutro lado se d � c, temos c “ c1d. Neste caso, existem x0, y0 P Z tais que ax0 ` by0 “ d. Mas então,multiplicando por c1 temos que
ac1x0 ` bc1y0 “ c1d
ou seja, que x “ c1x0, y “ c1y0 é solução da equação diofantina. Então provamos o primeiro enunciado.
Provamos o segundo. É claro que se d “ 0 se e somente se a “ 0 e b “ 0, no qual caso Z2 é o conjuntode todos os pares de soluções. Supomos então que d ‰ 0. Então a ‰ 0 ou b ‰ 0. Supomos, sem faltade generalidade, que b1 ‰ 0. Seja x1, y1 uma solução qualquer da equação diofantina. Temos
ax1 ` by1 “ c
e então, subtraendo apc1x0q ` bpc1y0q “ c, temos
apx1 ´ c1x0q ` bpy1 ´ c
1y0q “ 0
ou sejaapx1 ´ c
1x0q “ bpc1y0 ´ y1q
ou seja, dividendo por d, temosa1px1 ´ c
1x0q “ b1pc1y0 ´ y1q .
Mas agora b1 � a1px1´ c1x0q, mas é primo com a1, então b1 � x1´ c
1x0, ou seja, que x1´ c1x0 “ b1t, por
um certo t P Z, ou seja x1 “ c1x0 ` b1t. Então temos
a1b1t “ b1pc1y0 ´ y1q .
Dividendo por b1, temosc1y0 ´ y1 “ a1t
da qual se deduzy1 “ c1y0 ´ a
1t .
É claro que todas os pares pc1x0 ` b1t, c1y0 ´ a
1tq são soluções, porque
apc1x0 ` b1tq ` bpc1y0 ´ a
1tq “ ac1x0 ` bc1y0 ` tpab
1 ´ a1bq “ c` 0 “ c .
16. 25/09: aula 16: revisão.
17. 27/09: P1
18. 02/10: aula 17. Revisão da soma de uma PG:
1` q ` ¨ ¨ ¨ ` qn “qn`1 ´ 1
q ´ 1
se q P R, q ‰ 1.
Proposição 8. Seja a “ upα11 ¨ ¨ ¨ pαr
r onde pi são primos positivos distintos. Então, indicando npaq onúmero de divisores positivos de a e com spaq a soma dos divisores positivos, temos
npaq “ pα1 ` 1q ¨ ¨ ¨ pαr ` 1q
spaq “rź
i“1
pαi`1i ´ 1
pi ´ 1
16
Crivo de Erathóstenes. Existencia da raiz quadrada:
Teorema 25. Seja x P R, x ě 0. Então existe um único α P R, α ě 0 tal que α2 “ x. Um tal α sediz a raiz quadrada de x.
Sejam α, x P R. As seguintes são equivalentes
#
x ě 0
α “?x
ðñ
$
’
&
’
%
x ě 0
α ě 0
α2 “ x
.
Lema 7. Seja n P N, e seja n “ ab uma qualquer fatoração, com a ě 0, b ě 0. Então temos quea ď
?n ou b ď
?n.
Proposição 9. Seja n P Z, n ‰ 0, n ‰ ˘1. Se n não é primo, então n admite um divisor primopositivo p tal que p ď
a
|n|.
Demonstração. Se n não é primo, podemos escrever n “ uab, onde u “ sgnn, a ą 0, b ą 0, ondea ‰ ˘1, b ‰ ˘1. Mas então |n| “ ab é uma fatoração propria. Pelo lema precedente a ď
a
|n| oub ď
a
|n|. Supomos que a ďa
|n|. Mas dado que |n| “ ab é uma fatoração propria, temos que aadmite primos associados. Seja p um primo positivo associado à a. Então p � a, o que implica p ď a
(tomando os valores absolutos) e entãop ď a ď
a
|n|
.
Corolário 5 (Crivo de Erathóstenes). Seja n P N, n ą 1. Se n não admite nenhum divisor primopositivo p tal que p ă
?n, então p é primo.
Exemplo: encontrar todos os primos positivos menores de 100.
Distribuição dos primos.
Congetura (Congetura dos Primos Gemeos). Por cada n P N, existem p, p ` 2 primos consecutivosmaiores do que n. (Existem infinitos primos gemeos).
O estado atual (03 de Outubro 2017) da congetura é o seguinte:2013: Yitang Zhang provou que por cada n P N existem primos p, q, com q ą p ą n, tais queq ´ p ă 70 ¨ 106.2014: Tao, em conjunto no Projeto Polymath, conseguiram reduzir a cota de 70 milhões até 246. Acota pode ser reduzida até 6 se se assumem outras conjeturas.
Do outro lado é facil provar que existem primos consecutivos afastados quando se quer.
Lema 8. Por cada n P N, existem n inteiros consecutivos tais que nenhum deles é primo.
Demonstração. Tomamos n ě 3 e consideramos os n inteiros
pn` 1q!` 2, pn` 1q!` 3, . . . , pn` 1q!` n` 1 .
Proposição 10. Por cada n P N, existem dois primos positivos consecutivos ph, ph`1 tais que ph`1 ´
ph ą n.
17
Demonstração. Seja ph “ maxtp P N, p primo, p ă pn ` 1q! ` 2u. Então necessáriamente o primoseguinte satisfaz a ph`1 ą pn` 1q!` pn` 1q, o que implica que ph`1 ´ ph ą n.
Relacionado a isso é o
Teorema 26 (Postulado de Bertrand, ou teorema de Bertrand-Chebyshev). Por cada n P N, n ě 3,existe um primo p tal que n ă p ă 2n´ 2.
Observação 22. Outras formulações se podem fazer: por cada n P N, n ą 1, existe um primo p tal quen ă p ă 2n. Isto implica que, dado o k-esimo primo pk, o primo sucessivo pk`1 satisfaz
pk`1 ă 2pk .
Joseph Bertrand enuncio o postulado (congetura) no 1845. Foi demonstrada no 1852 por Chebyshev,e vai hoje sob o nome de Bertrand-Chebyshev.
Observação 23. O teorema de Bertrand-Chevyshev foi redemostrado (com uma prova mais simples) egeneralizado por Ramanujan.NO 1934 Erdös provou o seguinte resultado:
Teorema 27. Por cada inteiro positivo k, existe N P N tal que por cada n ą N , existem pelo menos kprimos entre n e 2n. (Ou seja, o número de primos entre n e 2n vai a infinito quando n vai a infinito).
No 2006 El Bachroui mostrou que, por cada n P N˚, existe sempre um primo p entre 2n e 3n.No 2011 Andy Loo provou que existe sempre um primo entre 3n e 4n. Loo provou também que se mn
é o números de primos entre 3n e 4n então limnÑ`8mn “ `8.
Relacionada a estes fatos mas ainda aberta é a
Congetura (Congetura de Legendre). Por cada n P N˚, existe um primo p entre n2 e pn` 1q2.
"Regularidade"dos Primos. Não se sabe se os primos seguem um "padrão". Quem se aproximoumais a estudar um "padrão"dos números primos foi Riemann, do qual falamos mais a frente. Dequalquer forma eles não podem ser produzidos por uma função polinomial.
Teorema 28 (Binomio de Newton). Sejam a, b P C, n P N, n ě 1. Então
pa` bqn “nÿ
k“0
ˆ
n
k
˙
akbn´k
ondeˆ
n
k
˙
:“n!
k!pn´ kq!.
Corolário 6. Sejam a, b P C, n P N, n ě 1. Então existe um polinômio não trivial ϕnpx, yq, que,ordenado nas potencias de y, tem como monomio de grau mais alto yn´1, tal que
pa` bqn “ an ` bϕnpa, bq .
Demonstração. Temos
pa` bqn “nÿ
k“0
ˆ
n
k
˙
akbn´k “ an `n´1ÿ
k“0
ˆ
n
k
˙
akbn´k “ an ` bn´1ÿ
k“0
ˆ
n
k
˙
akbn´k´1
18
Posto então
ϕnpx, yq “n´1ÿ
k“0
ˆ
n
k
˙
akbn´k´1 “ yn´1 ` nxyn´2 `
ˆ
n
2
˙
x2yn´3 ` ¨ ¨ ¨ ` nxn´1
temos o enunciado.
Proposição 11. Não existe nenhum polinômio ppxq tal que ppnq seja primo por cada n P N.
Demonstração. Supomos que ppxq seja um tal polinômio, ppxq “ amxm ` ¨ ¨ ¨ ` a1x ` a0. Podemos
assumir m ě 1. Seja n0 P N e seja ppn0q “ p primo. Então, por cada t P N, ppn0 ` tpq é primo. Mas éfacil ver, com o lema precedente, que
ppn0 ` tpq “ ppn0q ` tpgpn0, pq
onde gpn0, tpq “ amϕmpn0, tpq`am´1ϕm1pn0, tpq` ¨ ¨ ¨`a1ϕ1pn0, tpq. Mas então ppn0q` tpgpn0, tpq “
pp1` tgpn0, tpqq é primo, e então 1` tgpn0, pq “ ˘1. Agora se m ě 1, gpn0, tpq é de grau m´ 1 e nãozero (se m “ 1, então gpn0, tpq “ 1. ). Ainda gpn0, tpq tem termo dominante em tp igual a amptpqm´1.Então tgpn0, tpq não pode ser constante. Absurdo.
O Teorema dos Números Primos. Seja x P R, x ą 0. Indicamos com πpxq a função que conta osprimos positivos menores ou iguais a x, ou seja:
πpxq “ |tp P N | p primo , p ď xu| .
Estudar esta função é fundamental para perceber como estão distribuidos os primos.
Teorema 29 (Teorema dos Números Primos). A função πpxq é assintotica, por x que tende a `8 à
função x{ logpxq, ou à função2 Lipxq “
ż x
2
dt
log t, ou seja
limxÑ`8
πpxq
x{ log x“ 1 “ lim
xÑ`8
πpxq
Lipxq.
Os primeiros fatos sobre a função πpxq foram determinados por Legendre que enunciou no 1797 queπpxq tinha que ser assintotica à
x
A log x`B. No 1808 melhorou a estimativa, propondo A “ 1 e
B “ ´1.08366.
No 1792, à idade de 15 anos, Gauss conjeturou que πpxq fosse assintotica a Lipxq. Mas ele não publicou.
No 1838 Dirichlet re-encontrou a estimativa assintotica de Gauss πpxq „ Lipxq.
Entre o 1848 e 1852, ao fim de provar a estimativa assintotia para πpxq, Chebyshev fez estudos pro-fundos sobre a função ζpsq, s P C, mais tarde chamada zeta de Riemann, mas já usada e estudada porEuler,
ζpsq “`8ÿ
n“1
1
ns.
Chebyshev conseguiu provar que2É facil provar, usando a regra de De L’Hospital e o teorema fundamental do Calculo, que
limxÑ`8
x{ logpxq
Lipxq“ 1 .
19
• Se limxÑ`8πpxq
x{ log xexiste, então tem que ser 1;
• existem constantes c1, c2, c1 ă 1, c2 ą 1, muito perto de 1, tais que, por x suficientemente grande,
c1 ă πpxq{px{ log xq ă c2 .
Usando estas estimativas, Chebyshev consegui provar o Postulado de Bertrand.
1859. Riemann publica o artigo 3 Über die Anzahl der Primzahlen unter einer gegebenen Grösse, de 9paginas, único artigo de Riemann em teoria dos números. Neste artigo é feita uma analise extremamenteprofunda da função zeta. A função zeta, assim como definida, fornece uma função de variável complexa(holomorfa), na região de C, definida por Rez ą 1. Riemann mostra que ela satisfaz uma equaçãofuncional, que permite de extende-la a todo o plano complexo (com um único polo, ou seja um pontoonde ela vai ao infinito, em z “ 1). Com esta extensão, ela admite, nos inteiros negativos pares, zeroschamados triviais. Riemann mostra que, a parte estes zeros, todos os outros zeros da função zeta estãona faixa critica 0 ă Rez ă 1. Graças à função zeta, Riemann fornece uma formula explicita para πpxq.A prova desta formula foi completada por Von Mangoldt no 1895. Na formulação de Von Mangoldt, aformula explicita de Riemann diz o seguinte. Seja Λpnq a função definida por
Λpnq “
#
log p se n “ pk, com p primo e k ě 1
0 em outros casos
Por exemplo, a função Λ de 1, 2, . . . , 10 é dada por
0, log 2, log 3, log 2, log 5, 0, log 7, log 2, log 3, 0
A função ψ de Chebyshev é dada porψpxq “
ÿ
nďx
Λpnq
A função ψ0pxq de Chebyshev normalizada é dada por
ψ0pxq “ limhÑ0
ψpx` hq ´ ψpx´ hq
2
ou seja, a media dos limites direito e esquerdo, nas discontinuidades de ψ. A fórmula explicita deRiemann, na reformulação de Von Mangoldt diz que
ψpxq “ x´ÿ
w
xw
w´ logp2πq para x não inteiro
onde w corre entre os zeros não triviais na função ζ, e que, para todo x:
ψ0pxq “ x´ÿ
w
xw
w´ logp2πq ´
1
2logp1´
1
x2q
Reparamos que o enunciado do Teorema do Números Primos é equivalente a provar que
limxÑ`8
ψpxq
x“ limxÑ`8
ψ0pxq
x“ 1
3copia escaneada do qual se pode encontrar no sitehttps://upload.wikimedia.org/wikipedia/commons/c/cb/Ueber_die_Anzahl_der_Primzahlen_unter_einer_gegebenen_Grösse.pdf
20
Ou seja, a função ψpxq é uma especie de função que conta os primo numa escala adaptada 4, "mais
natural". Observamos mais de perto o termoÿ
w
xw
w. Dado que w é complexo, w “ ρ` iγ, ρ, γ P R, o
número xw se pode re-escrever como
xw “ eplog xqw “ eplog xqpρ`iγq “ eρ log xeiγ log x “ eρ log xpcospγ log xq ` i sinpγ log xqq
Riemann faz a seguinte Hipótese: seria tudo mais simples se a parte real dos zeros da função zeta fosseconstante 1{2, no qual caso se poderia escrever
xw “?xpcospγ log xq ` i sinpγ log xqq
e a somaÿ
w
xw
wseria, considerando que a parte imaginaria tem que ir a zero:
ÿ
γ
1{2´ iγ
1{4` γ2
?xpcospγ log xq ` i sinpγ log xqq “
ÿ
γ
?x
1{4` γ2p1
2cospγ log xq ` γ sinpγ log xqq
onde γ é tal que 1{2 ` iγ é zero não trivial da função zeta. Observamos que a soma é uma somade ondas nas variavel γ, fato que nos permite de interpretar a formula explicita de Riemann comouma analise de Fourier, numa escala adequada, da função πpxq: ou seja: Riemann consegue explicaros "saltos"da função πpxq gerado pela presencia de um novo primo (e, então, essencialmente, a sua"posição"), com uma soma infinitas de ondas de frequencia γ log x e de amplitude
?x{p1{2 ` 2γ2q e
γ?x{p1{4`γ2q, exactamente como sinais discontinuos (mas periodicos) podem ser produzidos por soma
infinitas de ondas monocromaticas. Re-enviamos o estudante interessado à página web http://web.math.ucsb.edu/~stopple/explicit.html onde simulações ao computador permitem de visualizarquanto a formula explicita aproxima bem a distribuição dos primos.
A hipótese de Riemann é ligada ao Teorema dos Números Primos. De fato, von Koch provou no 1905que a hipótese de Riemann é equivalente à estimativa muito precisa
πpxq “ Lipxq `Op?x log xq
ou seja que existe uma constante C ą 0 tal que, por x suficientemente grande
|πpxq ´ Lipxq| ď C?x log x
o que implica diretamente o Teorema dos Números Primos.
1896. Hadamard e De la Vallée-Poussin demonstram independentemente, usando a função zeta deRiemann, o Teorema dos Números Primos. A demonstração é analitica e dificil. Corre voz que nãoseja possível demonstrar o Teorema dos Números Primos de forma elementar.
1948 Em seguida de estudos profundos de Selberg, o proprio Selberg e, independentemente, Erdös, dãouma demonstração elementar do Teorema dos Números Primos. A prova é elementar, mas ainda longa.
1980. Newman da uma prova elementar e curta do Teorema dos Números Primos.4De fato, fixado x real positivo, se p é primo tal que pk ď x, mas pk`1 ę x, a função ψpxq "conta"o primo p com peso
k logppq. Exemplo ψp11` 12q “ 3 log 2` 2 log 3` log 5` log 7` log 11, em lugar de escrever πp11` 1
2q “ 1` 1` 1` 1` 1 “ 5
21
19. 04/10/2017, Aula 18.
Dado um conjunto X, o axioma do conjunto das partes afirma a existencia do conjunto PpXq “tY | Y Ď Xu, ou seja, o conjunto de todos os subconjuntos de X.
Sejam A e B dois conjuntos. Definição de par ordenado pa, bq, onde a P A, b P B, como
pa, bq :“ ttau, ta, buu P PpPpAYBqq .
Proposição 12. pa, bq “ pc, dq se e somente se a “ c, b “ d.
Definição de produto cartesiano AˆB de dois conjuntos como
AˆB :“ tpa, bq | a P A, b P Bu
Observamos que AˆB é naturalmente subconjunto de P pPpAYBqq. O produto cartesiano de três omais conjuntos é definido indutivamente como
A1 ˆ ¨ ¨ ¨ ˆAn´1 ˆAn :“ pA1 ˆ ¨ ¨ ¨ ˆAn´1q ˆAn .
Definição 10. Sejam A,B conjuntos. Uma relação R entre o conjunto A e o conjunto B é umsubconjunto ΓR do produto cartesiano A ˆ B. Dizemos que a P A é em relação com b P B, eescreveremos aRb se e somente se pa, bq P ΓR. Impropriamente, dizemos que ΓR é o grafico da relaçãoR (mas formalmente é a propria relação).
Varios exemplos de relações, entre os quais as relações de ordem e divisibilidade em Z.
Interpretação de uma relação em termos de Diagramas de Venn, como flechas arbitrarias conectandoelementos de a com elementos de b.
Obs: o conceito de relação não é simétrico nos conjuntos A e B. Na definição de relação ha sempreuma direção (a direção das flechas) que sempre vai de A até B para uma relação entre A e B.
Observação 24. Algumas vezes, sobretudo quando os conjuntos A e B podem variar, é bom consideraruma relação como uma terna pA,B,Γq onde Γ Ď AˆB. Em tal caso, duas relações pA,B,Γq, pA1, B1,Γ1qsão iguais, se e somente se são iguais como ternas, ou seja A “ A1, B “ B1, Γ “ Γ1.
Algumas propriedades das relações.
Definição 11. Sejam A,B dois conjuntos. Seja R uma relação entre o conjunto A e o conjunto B eseja ΓR o seu grafico. Chamamos com DpRq o dominio da relação R, ou seja,
DpRq “ ta P A | pa, bq P ΓRDb P Bu
com IpRq chamamos a imagem da relação R, ou seja,
IpRq “ tb P B | pa, bq P ΓRDa P Au .
Definição 12. Sejam A,B dois conjuntos. Seja R uma relação entre o conjunto A e o conjunto B eseja ΓR o seu grafico. Dizemos que a relação R é
• com unicidade a esquerda, ou injetiva se#
px1, yq P ΓR
px2, yq P ΓRùñ x1 “ x2
equivalentemente: se cada "reta horizontal"A ˆ tyu intersecta o grafico ΓR em ao máximo umponto;equivalentemente: se cada elemento b de B é alvo de ao máximo uma flecha proveniente de A;
22
• com unicidade a direita, ou univalente se#
px, y1q P ΓR
px, y2q P ΓRùñ y1 “ y2
equivalentemente: se cada "reta vertical"tauˆB intersecta o grafico ΓB em ao máximo um ponto;equivalentemente se de cada elemento a de A parte ao máximo uma flecha em direção de B
• total a esquerda, se @a P A, Db P B, tal que pa, bq P ΓR;ou seja, se cada "reta vertical"tau ˆB cruza o grafico ΓR em pelo menos um ponto;equivalentemente se de cada elemento a P A parte pelo menos uma flecha em direção de Bequivalentemente DpRq “ A;
• total a direita, ou sobrejetiva: se @b P B, Da P A tal que pa, bq P ΓR;ou seja, se cada "reta horizontal"Aˆ tbu cruza o grafico ΓR em pelo menos um ponto;equivalentemente, se cada elemento b de B é alvo de pelo menos uma flecha proveniente de A;equivalentemente IpRq “ B.
Definição 13 (Relação R˚, simétrica de uma relação R). Sejam A,B conjuntos e seja R uma relaçãode A em B. Definimos a relação R˚ como
ΓR˚ :“ tpb, aq P B ˆA | pa, bq P ΓRu
Observação 25. A relação simétrica R˚ tem grafico exactamente o simétrico do grafico ΓR. Na intepre-tação com diagramas de Venn e flechas, a relação R˚ se obtem invertendo todas as flechas da relaçãoR. É imediato provar que: DpR˚q “ IpRq; IpR˚q “ DpRq.
Definição 14 (Composição de relações). Sejam A,B, C conjuntos. Seja R uma relação de A em B,e seja S uma relação de B em C. Definimos a relação S ˝R, composição de R e S, como
ΓS˝R :“
#
pa, cq P Aˆ C | Db P B |
#
pa, bq P ΓR
pb, cq P ΓS
+
Exercício 2. A composição de relações é associativa, ou seja, se A,B,C,D são conjuntos. Seja Ruma relação de A em B, S uma relação de B em C e T uma relação de C em D. Então
T ˝ pS ˝Rq “ pT ˝ Sq ˝R .
Definição 15. Dados A e B conjuntos, uma função f de A em B é uma relação univalente e total
a direita entre A e B. Em outras palavras, o grafico Γf da relação f é o grafico de uma função se e
somente se
@a P A D!b P B | pa, bq P Γf .
Fixado a P A, temos um único b tal que pa, bq P Γf . Em outras palavras, qualquer "reta vertical"tauˆBcruza o grafico Γf em um único ponto. Por sua unicidade, o b depende unicamente de a, e serà indicadocom fpaq. Então a escritura
b “ fpaq
é equivalente apa, bq P Γf
quando f é uma função.
23
Definição 16. Uma função f : A - B se diz injetiva, se é injetiva como relação;sobrejetiva, se é sobrejejtiva como relaçãobijetiva se é injetiva e sobrejetiva.
Observação 26. Se A é conjunto a função idA : A - A é a função cujo grafico é ∆A “ tpa, aq |a P Au,ou seja, a função tal que idApaq “ a por cada a P A.
Exercício 3. Sejam A,B conjuntos. Seja R uma relação de A em B. Provar que R ˝ idA “ R,idB ˝R “ R.
Observação 27. É facil ver que uma função f : A - B é bijetiva se e somente se
@b P B D!a P A | pa, bq P Γf
Observação 28. Seja f : A - B uma função. A condição de bijetividade para f , ou seja
@b P B D!a P A | pa, bq P Γf
é equivalente a dizer que@b P B D!a P A | pb, aq P Γf˚
ou seja que a relação f˚ é uma função.
Exercício 4. Composição de funções é uma função.
Definição 17. Uma função f : A - B se diz inversível se existe uma função g : B - A tal que#
g ˝ f “ idA
f ˝ g “ idB
Uma tal função se diz inversa de f .
Exercício 5. Seja f : A - B uma função inversível e sejam g1, g2 duas inversas de f . Entãog1 “ g2.
Teorema 30. Seja f : A - B uma função. Então f é bijetiva se e somente se f é inversível.Neste caso a única inversa é a função f˚. Neste caso indicaremos com a mais comum notação f´1 afunção inversa f˚.
20. 09/10: Aula 19. Sejam, A,B conjuntos e R uma relação entre A e B. Se C Ď B, definimos com
R´1pCq “ ta P A | aRb, Db P Cu
Em outras palavras R´1pCq “ R˚pCq.
Sejam A,B conjuntos e f : A - B uma função. Se C “ tcu Ď B é um subconjunto de B que contémum único elemento, denotamos com f´1pcq o subconjunto f´1ptcuq, mesmo que f não seja inversívelcomo função.
Motivação para as relações de equivalencia. Uma relação de equivalencia formaliza um conceito de"igualdade"menos rigido do que a igualdade formal, de forma a enfatizar, a concentrar-se sobre aspropriedades que consideramos importantes a cada vez. Por exemplo, na geometria euclidiana plana,consideramos iguais dois triangulos quando um deles pode ser transportado em cima do outro via um
24
movimento rigido (movimento que conserva as distancias). Mas dois triangulos considerados iguais,não são necessariamente o mesmo triangulo. No caso da geometria euclidiana a propriedade queconsideramos importante é a conservação da distancia, e então consideramos iguais dois triangulosquando os lados são, a dois a dois, do mesmo tamanho.
Seja R uma relação do conjunto A em si. Definição de relação reflexiva, simétrica, antisimétrica,transitiva. Uma relação de equivalencia é uma relação reflexiva, simétrica e transitiva. Uma relação depre-ordem é uma relação reflexiva e transitiva. Uma relação de pre-ordem antisimétrico é uma relaçãode ordem.
Definição 18. Seja R uma relação de A em si mesmo. Seja a P A. Definimos com
ras “ tb P A | bRau
ou seja, é o subconjunto de A de todos os elementos em relação com A. Quando R é de equivalencia,chamamos ras a classe de equivalencia de a para a relação R.
Definição 19. Seja R uma relação de equivalencia definida em A. Chamamos conjunto quociente oconjunto A{R “ tras | a P Au de todas as classes de equivalencia de A.
Observação 29. O conjunto quociente é naturalmente um subconjunto de PpAq.
Definição 20. Seja R uma relação de equivalencia definida em A e seja A{R o conjunto quociente. Aprojeção quociente é a função (naturalmente sobrejetiva)
πR : A -- A{R
a - ras
Exemplo de relações de pre-ordem, ordem e de equivalencia como a divisibilidade em Z (pre-ordem),divisibilidade em N (ordem), ď em Z (ordem total), várias relações de equivalencia geometrica em R2,identificação das classes de equivalencia e do conjunto quociente. Reparamos o seguinte fenomeno: asclasses de equivalencia distintas são sempre disgiunta e nunca vazias, e cobrem todo o conjunto A ondea relação é definida.
Definição 21 (Relação de congruencia módulo k). Seja k P Z. Definimos a relação de congruenciamódulo k em Z como
x ”k y ðñ y ´ x P kZ ðñ y ´ x “ kq, Dq P Z .
Proposição 13. A relação de congruencia módulo k é de equivalencia. Denotamos o conjunto quoci-ente Z{ ”k com Z{kZ, o, as vezes, com Zk.
Observação 30. É facil reparar que ”0 é exactamente a identidade idZ, que Γ”1 “ Zˆ Z, ou seja que@y P Z, @x P Z, x ”1 y.
Exemplo 3. Escrevemos todas as classes de equivalencia r0s6, r1s6, r2s6, r3s6, r4s6, r5s6 em Z{6Z.
21. 11/10 Aula 20. Vamos provar agora que as classes de equivalencias formam uma partição do conjuntoonde a relação é definida.
Observação 31. Vamos reformular as propriedades reflexiva, simétrica, transitiva, para uma relaçõa Rdefinida no conjunto A.
25
• R é reflexiva ðñ aRa @a P A ðñ a P ras @a P A.
• R é simétrica se e somente se @a, b P A aRb ðñ bRa, ou seja @a, b P A a P rbs ðñ b P ras
• R é transitiva se e somente se @a, b, c P A,
#
aRb
bRcùñ aRc, ou seja
@a, b, c P A
#
a P ras
b P rcsùñ a P rcs .
Proposição 14. Seja R uma relação de equivalencia definida em A. São equivalentes
i) aRb;
ii) ras X rbs ‰ H;
iii) ras “ rbs.
Demonstração. i) ùñ ii). Se aRb então a P rbs, mas a P ras, porque R é reflexiva, então a P ras X rbs.Então ras X rbs ‰ H.
ii) ùñ iii). Supomos que ras X rbs ‰ H. Então existe x P A, tal que x P ras X rbs. Mas então x P ras,e x P rbs. Pela propriedade simétrica, se x P ras implica que a P rxs, e dado que x P rbs, temos quea P rbs, ou seja que aRb, e que então bRa, por simétria.
Provamos agora que ras Ď rbs. Seja y P ras. Dado que a P rbs, temos por transitividade que y P rbs, oque implica que ras Ď rbs. Seja agora y P rbs. Dado que b P ras, temos y P ras por transitividade; entãorbs Ď ras. Então ras “ rbs.
iii) ùñ i) Se ras “ rbs, temos que a P ras “ rbs, então a P rbs, ou seja aRb.
Corolário 7. Seja R uma relação de equivalencia definida em A. Se ras ‰ rbs, então ras X rbs “ H.Ou seja, duas classes de equivalencia distintas são disjuntas.
Observação Importante. A proposição precedente diz o fato seguinte. Se A é conjunto e R é deequivalencia em A, então temos
xRy ðñ rxs “ rys .
Observação Importante, II Em particular, se k P Z, k ‰ 0, temos que se x, y P Z, temos
x ”k y ðñ rxsk “ rysk .
Definição 22. Seja A um conjunto. Uma partição de A é uma familia tSλuλPΛ de subconjuntos de Atais que
• por cada λ P Λ, Sλ ‰ H;
• Se λ1 ‰ λ2, temos Sλ1X Sλ2
“ H
• YλPΛSλ “ A.
26
Teorema 31. Seja A um conjunto. Cada relação de equivalencia R em A define uma única partiçãode A cuja família de subconjuntos tSλuλPΛ é dada pelas classes de equivalencia trasurasPA{R. Recipro-camente, dada uma partição tSλuλPΛ de A, existe uma única relação de equivalencia R em A tal queas classes de equivalencias sejam exactamente os subconjuntos da partição (ou seja, se por cada a P A,indicamos com Sλa
o único subconjunto da partição que contem a, então a função A{R - tSλu queassocia a ras o conjunto Sλa
é bem definida e bijetiva: não só, temos que ras “ Sλa).
Funções a partir de um conjunto quociente.
Dada uma relação de equivalencia R no conjunto A e um segundo conjunto B, se põe o problema dedefinir funções
f : A{R - B .
O problema se põe quando queremos definir fprxsq, ou seja f aplicada à classe de equivalencia de umelemento x, em termos de x. Surge o problema da boa definição: A classe rxs, mesmo dependendo doelemento x, pode provavelmente se escrever como rxs “ rys, com y diferente de x. Então, para ter umafunção bem definida de A{R até B, é preciso que cada vez que rxs “ rys, tenhamos que a definição defprxsq coincida com a definição de fprysq.
Exemplo 4. A função f : Z{6Z - N dada por fprnsq “ |n| não é bem definida. De fato fpr2sq teriaque ser igual a fpr8sq porque r2s “ r8s, mas na nossa definição fpr2sq “ |2| ‰ |8| “ fpr8sq. Ou seja, adefinição de f tem que depender só da classe e não do elemento representante da classe, mesmo que adefinição use aquele elemento.
Exemplo 5. Seja R2 “ A e seja R a relação de equivalencia px, yqRpx1, y1q se x2 ` y2 “ px1q2 ` py1q2.Consideramos a função f : R2{R - R "definida"por
fprpx, yqs “ x4 ` y4 ` 2x2y2 ` 3x2 ` 3y2
Então ela é bem definida, no sentido que se rpx, yqs “ rpx1, y1qs, então x4 ` y4 ` 2x2y2 ` 3x2 ` 3y2 “
px1q4 ` py1q4 ` 2px1q2py1q2 ` 3px1q2 ` 3py1q2.
Tentamos agora de ver o problema de forma um pouco mais teorica. Seja A um conjunto e seja R umarelação de equivalencia sobre A. Se g : A{R - B é uma função bem definida entre o quociente A{Re o conjunto B, então, por composição com a projeção quociente πR : A - A{R, fica definida umafunção f : g ˝ πR : A - A{R - B. Por definição temos que
fpxq “ gpπRpxqq “ gprxsq
Ou seja, cada vez que temos uma função bem definida g : A{R - B, conseguimos sempre exprimirg como uma função do representante. É claro também que se
πRpxq “ πRpyq ùñ fpxq “ gpπRpxqq “ gpπRpyqq “ fpyq
ou seja a função f : A - B tem a propriedade
πRpxq “ πRpyq ùñ fpxq “ fpyq .
Esta condição se pode re-escrever como
rxs “ rys ùñ fpxq “ fpyq
ou entãoxRy ùñ fpxq “ fpyq .
27
Observação 32. A condição que acabamos de escrever se pode interpretar como R Ď„f , en termos derelações, ou ainda como o fato que f é constante longo das classes de equivalencia de R.
Vamos ver agora o reciproco. Se trata de saber quando, dada uma função f : A - B, e uma relaçãode equivalencia R sobre A, a função f "desce"a uma função g : A{R - B. É claro que a condiçãoque encontramos é necessaria, mas serà suficiente?
Vamos colocar o problema de forma ainda mais geral.
Lema 9. Seja f : A - B uma função e seja π : A -- Q uma função sobrejetiva. Então existe(uma única) g : Q - B tal que g ˝ π “ f se e somente se πpxq “ πpyq ùñ fpxq “ fpyq, ou seja,se e somente se f é constante longo as fibras de π.
Demonstração. A necessidade da condição é evidente porque se existe g, e se πpxq “ πpyq, entãofpxq “ gpπpxqq “ gpπpyqq “ fpyq. Do outro lado, supomos que por cada x, y P A, πpxq “ πpyq ùñ
fpxq “ fpyq. Sabemos que g é sobrejetiva. Queremos definir gpqq, com q P Q. Mas certamente existea P A tal que πpaq “ q. Definimos então
gpqq :“ fpaq .
Aqui surge o problema da boa definição, porque para definir g fizemos uma escolha. Temos queconseguir provar que o valor de gpqq não depende da escolha feita, mas só de q. Supomos então que a1
seja outro elemento em A tal que πpa1q “ πpaq “ q. Ou seja a, a1 P π´1pqq. Mas f é constante sobre asfibras de π, então
πpaq “ πpa1q ùñ fpa1q “ fpaq
ou seja, se tivessemos definido gpqq usando o levantamento a1, teriamos tido o mesmo resultado. Entãog esta bem definida e é claro que gpπpaqq “ fpaq porque a é um levantamento de πpaq. É tambémclaro que se existe uma tal g tem que ser única.
Temos o reciproco:
Teorema 32. Seja f : A - B uma função entre conjuntos. Seja R uma relação de equivalenciadefinida em A e seja πR : A - A{R a projeção quociente. Então existe g : A{R - B tal quef “ g ˝ πR se e somente se
@x, y P A, xRy ùñ fpxq “ fpyq
Demonstração. A necessidade da condição foi feita antes da observação. Para a suficiencia, usamos olema acima, com Q “ A{R, e obtemos que g existe (unica) se temos a condição
πRpxq “ πRpyq ùñ fpxq “ fpyq
mas esta é a condição do teorema.
Observação 33. No teorema acima, temos que a função induzida g é sobrejetiva se e somente se f ésobrejetiva, e é injetiva se e somente se fpxq “ fpyq ùñ πpxq “ πpyq ðñ xRy, ou seja, se e somentese R “„f .
As vezes é preciso definir uma função g : A1{R1ˆA2{R2- B a partir do produto cartesiano de dois
conjuntos quocientes. Certamente temos a função sobrejetiva πR1ˆπR2 : A1ˆA2- A1{R1ˆA2{R2.
Então podemos aplicar o lema acima, para obter
28
Proposição 15. Sejam A1, A2, B conjuntos. Seja f : A1 ˆ A2- B uma função. Sejam R1, R2
relações de equivalencias, respeitivamente, nos conjuntos A1 e A2. Então existe uma função g : A1{R1ˆ
A2{R2- B tal que g ˝ pπR1
ˆπR2q se e somente se px1R1y1q^px2R2y2q ùñ fpx1, y1q “ fpx2, y2q.
Proposição 16. Seja k P Z, k ‰ 0. Temos que x ”k y ou seja, que rxsk “ rysk se e somente se x e ytem o mesmo resto na divisão por k.
Demonstração. Se x “ kq ` r, y “ kq1 ` r, então x ”k r, y ”k r, e então rxs “ rrs “ rys.
Do outro lado, supomos que x ”k y, e dividimos os dois por k: x “ kq`r, y “ kq1`r1, com 0 ď r ă |k|,0 ď r1 ă |k|. Então rrs “ rxs “ rys “ rr1s. Mas então r ” r1 mod k, e então r “ kq` r1. Mas então asduas r “ k0` r e r “ kq ` r1 são duas divisões euclidianas e r “ r1.
Proposição 17. Seja k P Z, k ‰ 0. O conjunto quociente Z{kZ contém exactamente |k| elementos(ou seja, é em bijeção com t1, . . . , |k|u).
Demonstração. Consideramos a composição
j : t0, . . . , |k| ´ 1u Ă - Z - Z{kZ .
É composição de funções, e então é uma função. Ela é definida como jpxq “ rxs. É sobrejetiva, porquê,dado rxs P Z{kZ, e dividindo x por k temos x “ kq ` r, com 0 ď r ă |k|, então 0 ď r ď |k| ´ 1. Alémdisso, rxs “ rrs, porquê x ”k r, porquê x´ r P kZ. Então rxs “ rrs “ jprq. Então é sobrejetiva.
Mostramos que é injetiva. Supomos que x, y P t0, . . . , |k| ´ 1u e que jpxq “ jpyq. Mas então x e y temo mesmo resto na divisão por k. Mas temos as divisões euclidianas x “ k0 ` x, y “ k0 ` y. Entãox “ y. É claro agora que t0, . . . , |k| ´ 1u é em bijeção com t1, . . . , |k|u, via função x - x ` 1, quetem inversa x - x ´ 1. Mas então a composição t1, . . . , |k|u - t0, . . . , |k| ´ 1u - Z{kZ, queobservamos dada por x - rx´ 1sk, é bijetiva, porquê composição de bijeções.
22. (16/10: aula 21)Funções a partir de um conjunto quociente.
23. (18/10: aula 22)
Definição 23. Seja A um conjunto. Uma operação interna em A é uma função µ : AˆA - A.
Provamos, em duas maneiras, a mão e usando a teoria da aula passada, que as seguintes (propostasde) definições são BEM DEFINIDAS fornecem duas operações ` e ¨ sobre Z{nZ:
rasn ` rbsn :“ ra` bsn
rasn ¨ rbsn :“ rabsn
Observação 34. As definições acima não são fruto do caso. Queremos que Z{nZ tenha operações soma` e produto ¨ tais que a projeção quociente π : Z - ZZ respeite ou seja compativel com as operaçõesem Z (estandard) e em Z{nZ, ou seja, queremos que
πpa` bq “ πpaq`πpbq
πpa ¨ bq “ πpaq¨πpbq
29
Mas, dado que πpaq :“ rasn, segue que para ter operações ` e ¨ da forma que π as respeite, é necessarioque
rasn`rbsn :“ πpaq`πpbq :“ πpa` bq “ ra` bsn
rasn¨rbsn :“ πpaq¨πpbq :“ πpa` bq “ ra ¨ bsn
Ou seja, existe uma única definição possível para operações de soma e produto em Z{nZ tais que π asrespeite.
Definição 24. Seja A um conjunto e seja µ : AˆA - A uma operação interna.
• Dizemos que µ é associativa se
@a, b, c P A µpµpa, bq, cq “ µpa, µpb, cqq .
• Dizemos que um elemento e P A é neutro para a operação µ se
@a P A µpa, eq “ a “ µpe, aq .
Neste caso dizemos que a operação µ admite elemento neutro e.
Observação 35. Seja A um conjunto e µ uma operação em A. Existe ao máximo um únicoelemento neutro e para µ.
Demonstração. Supomos que e1, e2 sejam elementos neutros para µ. Então
e1 “ µpe1, e2q “ e2
onde na primeira igualdade usamos que e2 é neutro para µ e na segunda usamos que e1 é neutro.
• Seja µ uma operação interna com elemento neutro definida em A. Seja a P A. Dizemos que a éinversível (ou admite inverso) para a operação µ se existe b P A tal que
µpa, bq “ e “ µpb, aq .
Observação 36. Seja A um conjunto e seja µ uma operação interna associativa com elementoneutro definida em A. Seja a P A. Então existe ao máximo um inverso b de a para a operação µ.
Demonstração. Se b1, b2 são dois inversos de a para a operação µ, então
b1 “ µpb1, eq “ µpb1, µpa, b2qq “ µpµpb1, aq, b2q “ µpe, b2q “ b2 .
• Dizemos que µ é comutativa se
@a, b P A µpa, bq “ µpb, aq .
Definição 25. Seja A um conjunto com uma operação interna µ.
• Dizemos que o par pA,µq é um semigrupo se µ é associativa.
Exemplo 6. pNě5,`q, pNě3, ¨q são semigrupos.
30
• Dizemos que o par pA,µq é um monoide se pA,µq é um semigrupo e µ admite elemento neutro e.
Exemplo 7. pN,`q é um monoide, assim como pN˚, ¨q, com elementos neutros 0 e 1, respeitiva-mente.
• Dizemos que pA,µq, é um grupo se pA,µq é um monoide onde todos os elementos são inversíveispara µ.
Exemplo 8. O par pSpXq, ˝q, onde X é um conjunto, SpXq é o conjunto das bijeções de X emX, e ˝ é a composição é um grupo, chamado o grupo simétrico de X.
• Dizemos que pA,µq é um grupo comutativo se pA,µq é grupo e µ é comutativo.
Exemplo 9. pZ,`q é um grupo comutativo. O grupo simétrico pSpXq, ˝q não é comutativo se|X| ě 3.
Definição 26. Um anel é uma tripla pA,µ, νq onde A é um conjunto e µ e ν são operações internasdefinidas em A tais que
• pA,µq é um grupo (comutativo) com elemento neutro 0;
• pA, νq é um monoide com elemento neutro 1;
• 1 ‰ 0;
• As duas estruturas pA,µq (estrutura aditiva) e pA, νq (estrutura multiplicativa) são relacionadaspor a propriedade distributiva
@a, b, c P A νpa, µpb, cqq “ µpνpa, bq, νpa, cqq
νpµpa, bq, cq “ µpνpa, cq, νpb, cqq
• Um anel pA,µ, νq se diz comutativo se ν é comutativa.
Teorema 33. O conjunto quociente Z{nZ, com as operações soma ` e produto ¨ é um anel comutativo.
(23/10: aula 23). Lei de anulação do produto em Z{nZ é valida se e somente se n é primo. Inversosmultiplicativos modulo n.
Proposição 18. Sejam a, b P Z, n P N, n ě 1. A congruencia ax ” b mod n tem solução se e somente sepa, nq � b. Em tal caso a solução é única modulo n1, onde n1 é definido como n “ n1|pa, nq|. Isto significa quea solução geral pode ser exprimida como x ” c mod n1, onde c é uma solução particular. Modulo n existemexactamente as d soluções distintas c, c` n1, . . . , c` pd´ 1qn1.
(30/10: aula 24).
Teorema 34. O sistema de congruencias#
x ” a mod n
x ” b mod m
admite solução se e somente se a ” b mod pm,nq.
31
Teorema 35. O sistema de congruências:$
’
&
’
%
x ” a1 mod m1
. . .
x ” ak mod mk
O sistema tem solução se e soamente se por cada i, j temos ai ” aj mod pmi,mjq. Em tal caso a solução éúnica módulo rm1, . . . ,mks, ou seja, a solução geral se pode escrever como x ” c mod rm1, . . . ,mks, onde cé uma solução particular.
Demonstração. Por indução sobre o número de congruências k. Por k “ 2 o enunciado é o conteudo doteorema 34. Supomos o resultado seja valido por k congruências e tentámos mostra-lo por k ` 1. Supomoster k ` 1 congruências
$
’
’
’
&
’
’
’
%
x ” a1 mod m1
. . .
x ” ak mod mk
x ” ak`1 mod mk`1
com a hipótese@i, j P t1, . . . , k ` 1u ai ” aj mod pmi,mjq .
Mas então temos a condição
@i, j P t1, . . . , ku ai ” aj mod pmi,mjq
Por hipótese indutiva existe então uma solução e às primeiras k congruências e todas as outras soluções sãoda forma x ” e mod rm1, . . . ,mks: esta última congruência é equivalente às primeiras k. Então só temosque encontrar uma solução ao sistema de duas congruências:
#
x ” e mod rm1, . . . ,mks
x ” ak`1 mod mk`1
.
Podemos usar o teorema 34: temos que provar antes de tudo que as hipóteses são verificadas, ou seja que
e ” ak`1 mod prm1, . . . ,mks,mk`1q .
Reparamos antes de tudo que
prm1, . . . ,mks,mk`1q “ rpm1,mk`1q, . . . pmk,mk`1qs .
Reparamos tambem que e ” ak`1 mod rpm1,mk`1q, . . . pmk,mk`1qs é equivalente ao fato
rpm1,mk`1q, . . . pmk,mk`1qs � e´ ak`1 ðñ
$
’
’
’
&
’
’
’
%
pm1,mk`1q � e´ ak`1
. . .
. . .
pmk,mk`1q � e´ ak`1
o que é equivalente ao sistema de congruências:$
’
’
’
&
’
’
’
%
e ” ak`1 mod pm1,mk`1q
. . .
. . .
e ” ak`1 mod pmk,mk`1q
32
Provamos que estas k congruências são verdadeiras. Por cada i “ 1, . . . , k, temos e ” ai mod mi o queé equivalente a mi � pe ´ aiq. Mas agora pmi,mk`1q � mi � e ´ ai e então e ” ai mod pmi,mk`1.Temos por hipótese ai ” ak`1 mod pmi,mk`1q. Mas então a propriedade transitiva diz e ” ak`1
mod pmi,mk`1q. Então as congruências aqui em cima são todas verdadeiras, ou seja é verdade que e ” ak`1
mod rpm1, ak`1q, . . . pmk, ak`1qqs. Mas se esta condição é verificada, então podemos aplicar o teorema 34 ededuzir a existência de uma solução ao sistema de congruências
#
x ” e mod rm1, . . . ,mks
x ” ak`1 mod mk`1
.
Mas este sistema de congruências é equivalente ao sistema original. Agora a solução geral do sistema#
x ” e mod rm1, . . . ,mks
x ” ak`1 mod mk`1
se escreve comox ” c mod rrm1, . . . ,mks,mk`1s
que, sendo rrm1, . . . ,mks,mk`1s “ rm1, . . . ,mk`1s, é o que queriamos.
Corolário 8. Se m1, . . . ,mk são a dois a dois coprimos (ou seja pmi,mjq “ 1 por cada i ‰ j), o sistemade congruências
$
’
&
’
%
x ” a1 mod m1
. . .
x ” ak mod mk
tem sempre solução. Essa solução é única módulo m1 ¨ ¨ ¨mk.
(01/11: aula 25). Estrutura de anel produto cartesiano de aneis.
Proposição 19. Sejam pA,µA, νAq, pB,µB , νBq dois aneis. Então as operações µAˆµB, νAˆ νB definidascomo as composições
µA ˆ µB : pAˆBq ˆ pAˆBq„- pAˆAq ˆ pB ˆBq - AˆB
ppa1, b1q, pa2, b2qq - ppa1, a2q, pb1, b2qq - pµApa1, a2q, µBpb1, b2qq
νA ˆ νB : pAˆBq ˆ pAˆBq„- pAˆAq ˆ pB ˆBq - AˆB
ppa1, b1q, pa2, b2qq - ppa1, a2q, pb1, b2qq - pνApa1, a2q, νBpb1, b2qq
definem sobre o produto cartesiano AˆB uma estrutura de anel, com elemento neutro para a soma µAˆµBo elemento p0A, 0Bq e elemento neutro para o produto µA ˆ νB o elemento p1A, 1Bq.
Exemplo 10. O produto cartesiano Z{12Zˆ Z{15Z tem estrutura de anel com as operações
pra1s12, rb1s15q ` pra2s12, rb2s15q “ pra1s12 ` ra2s12, rb1s15 ` rb2s15q
pra1s12, rb1s15q ¨ pra2s12, rb2s15q “ pra1s12 ¨ ra2s12, rb1s15 ¨ rb2s15q
O elemento neutro para a soma é pr0s12, r0s15q e o do produto é pr1s12, r1s15q. O elemento oposto depras12, rbs15q é pr´as12, r´bs15q.
Homomorfismo de aneis. Isomorfismo de Aneis.
33
Definição 27. Sejam pM,µM q, pN,µN q dois monoides, com elementos neutros eM , eN , respeitivamente.Uma função f : M - N é homomorfismo de monoides se
fpµM px, yqq “ µN pfpxq, fpyqq
fpeM q “ fpeN q
Definição 28. Sejam pG,µGq, pH,µHq dois grupos, com elementos neutros eG, eH , respeitivamente. Umafunção f : G - H é homomorfismo de grupos se é homomorfismo de monoides.
Observação 37. Sejam pG,µGq, pH,µHq dois grupos, com elementos neutros eG, eH . Então uma funçãof : G - H é homomorfismo de grupos se e somente se fpµM px, yqq “ µN pfpxq, fpyqq, ou seja, destacondição, com a hipótese que G e H são grupos, podemos deduzir fpeGq “ eH .
Definição 29. Sejam pA,µA, νAq, pB,µB , νBq dois aneis. Uma função f : A - B se diz homomorfismode aneis se
fpµApx, yqq “ µBpfpxq, fpyqq @x, y P A
fpνApx, yqq “ νBpfpxq, fpyqq @x, y P A
fp1Aq “ fp1Bq
Exercício 6. Provar que se f : A - B é homomorfismo de aneis (como aqui em cima), então necessari-amente fp0Aq “ 0B . Usar que 0A “ 0A ` 0A.
Definição 30. Uma função f : A - B entre dois aneis é isomorfismo de aneis se é homomorfismo deaneis e se existe g : B - A, homomorfismo de aneis, tal que f ˝ g “ idB , g ˝ f “ idA.
Exercício 7. Uma função f : A - B entre dois aneis é isomorfismo de aneis se e somente se é homomor-fismo bijetivo.
Teorema 36 (Teorema Chinês do Resto, versão II). Se pmi,mjq “ 1, por i ‰ j, então a função
pf : Z{m1 ¨ ¨ ¨mkZ - Z{m1Zˆ ¨ ¨ ¨ ˆ Z{mkZ
rxsm1¨¨¨mk- prxsm1
, . . . , rxsmkq
é um isomorfismo de aneis.
(06/11: aula 26).
Teorema 37. Se pmi,mjq “ 1, por i ‰ j, então o isomorfismo de aneis
pf : Z{m1 ¨ ¨ ¨mkZ - Z{m1Zˆ ¨ ¨ ¨ ˆ Z{mkZ
rxsm1¨¨¨mk- prxsm1 , . . . , rxsmk
q
induz um isomorfismo de grupos dos inversíveis multiplicativos
pfˇ
ˇ
U: UpZ{m1 ¨ ¨ ¨mkZ, ¨q - UpZ{m1Z, ¨q ˆ ¨ ¨ ¨ ˆ UpZ{mkZ, ¨q .
Definição 31. Seja n P N, n ě 2. Definimos a função totiente de Euler ϕpnq como
ϕpnq :“ˇ
ˇUpZ{nZ, ¨qˇ
ˇ “ˇ
ˇ tm P N | 0 ď mleqn | pm,nq “ 1uˇ
ˇ .
Proposição 20. A função ϕ é multiplicativa, ou seja, se m,n P N, m,n ě 2,
ϕpmnq “ ϕpmqϕpnq .
34
Demonstração. Dado que pm,nq “ 1, pelo teorema 37 temos o isomorfismo de grupos
UpZ{mnZq » UpZ{mZq ˆ UZ{nZq
e então
ϕpnmq “ˇ
ˇUpZ{mnZqˇ
ˇ “ |UpZ{mZq ˆ UpZ{nZqˇ
ˇ “ |UpZ{mZq| ¨ |UZ{nZqˇ
ˇ “ ϕpmqϕpnq .
Proposição 21. Se p é um primo, então
ϕppkq “ pk ´ pk´1 “ pk´1pp´ 1q .
Demonstração. É suficiente contar quantos são os inteiros não negativos menores de pk que não são primoscom pk, ou com p, que é a mesma coisa, ou seja: vamos contar os naturais até pk que são divisiveis por p.São todos da forma mp, com 0 ď m ă pk´1. Então são pk´1. Então
ϕppkq “ pk ´ pk´1 .
Teorema 38 (Formula do Produto de Eulero). Seja n P N, n ě 2. Então:
ϕpnq :“ nź
pn
´
1´1
p
¯
.
Demonstração. Decompomos n em fatores primos: escrevaremos n como n “ pα11 . . . pαk
k , com pi primosdistintos. Então:
ϕpnq “kź
j“1
ϕppαj
j q “
kź
j“1
pαj´1j ppj ´ 1q
“
kź
j“1
pαj
j
´
1´1
pj
¯
“ nkź
j“1
´
1´1
pj
¯
“ nź
p�n
´
1´1
p
¯
(08/11: aula 27).
Proposição 22. Se p P N é primo, então por cada 1 ď k ď p´ 1,
p �
ˆ
p
k
˙
Demonstração. Por definiçãoˆ
p
k
˙
“p!
k!pp´ kq!“ppp´ 1q . . . pp´ k ` 1q
k!.
Entãok!
ˆ
p
k
˙
“ ppp´ 1q . . . pp´ k ` 1q .
Agora o termo de direita tem como p como fator primo. Então o termo de esquerda tambem. Mas todosos fatores primos de k!, dado que k ă p, são necessariamente menores do que p. Então p é fator primo deˆ
p
k
˙
.
35
Proposição 23. Sejam a, b inteiros, p P N, p primo. Então
pa` bqp ” ap ` bp mod p .
Demonstração. Da fórmula do binómio de Newton temos:
pa` bqp “ ap ` bp `n´1ÿ
i“1
ˆ
p
i
˙
ap´ibi .
Então
pa` bqp ” ap ` bp `n´1ÿ
i“1
ˆ
p
i
˙
ap´ibi mod p .
É suficiente mostrar quen´1ÿ
i“1
ˆ
p
i
˙
ap´ibi ” 0 mod p ,
mas, pela proposição precedente, p �ˆ
p
i
˙
por cada i “ 1, . . . , p´ 1. Ou seja, podemos escreverˆ
p
i
˙
“ pci,
ci P N˚, se i “ 1, . . . , p´ 1. Então
n´1ÿ
i“1
ˆ
p
i
˙
ap´ibi “ pn´1ÿ
i“1
ciap´ibi ” 0 mod p
e então obtemos o que queremos.
Teorema 39 (Pequeno Teorema de Fermat). Seja p P N, p primo. Se a P Z então
ap ” a mod p
Se p ffl a, esta equação é equivalente aap´1 ” 1 mod p .
Demonstração. Demostramos a primeira. A afirmação é modulo p, e então é suficiente demostra-la paraa “ 0, . . . , p ´ 1. De fato, se val para a “ 0, . . . , p ´ 1, então por qualquer outro a, dividendo por p, temosa ” r mod p, onde r é o resto da divisão euclidiana de a por p e então 0 ď r ď p ´ 1. Mas então ap ” rp
mod p ” r mod p ” a mod p.É suficiente então mostrar a identidade para a P N, por indução sobre a. É claro que o caso base a “ 0 é
obvio dado que 0p “ 0 e então 0p ” 0 mod p. Supomos agora o teorema válido por a ě 0, ou seja supomosap ” a mod p, e provamo-no por a` 1. Temos
pa` 1qp ” ap ` 1p mod p
por a proposição precedente. Mas agora ap ” a mod p por hipótese indutiva, então
pa` 1qp ” ap ` 1p mod p ” a` 1 mod p
e o passo indutivo esta mostrado.Para demostrar a segunda, se p não divide a, então pa, pq “ 1 e a tem inverso multiplicativo módulo p.
Seja b o inverso múltiplicativo de a módulo p. Lembramos que ab ” 1 mod p. Então
ap´1 ” apb mod p ” ab mod p ” 1 mod p .
36
Teorema 40 (Euler-Fermat). Sejam n P N, n ě 2, a P Z, com pa, nq “ 1. Então
aϕpnq ” 1 mod n .
Demonstração. A hipótese pa, nq “ 1 é equivalente ao fato que rasn P UpZ{nZ, ¨q. Em particular existerbsn “ ras
´1n o inverso multiplicativo de rasn. Consideramos agora a função g : UpZ{nZ, ¨q - UpZ{nZq
definida como
g : UpZ{nZ, ¨q - UpZ{nZq
rxsn - rasn ¨ rxsn “ raxsn
Mostramos agora que g é uma bijeção. Temos que gprxsnq “ gprysnq implica que rasn ¨ rxsn “ rasn ¨ rysn emultiplicando a esquerda por rbsn obtemos
rasn ¨ rxsn “ rasn ¨ rysn
rbsn ¨ prasn ¨ rxsnq “ prbsn ¨ rasnq ¨ rysn
prbsn ¨ rasnq ¨ rxsnq “ prbsn ¨ rasnq ¨ rysn
r1sn ¨ rxsn “ r1sn ¨ rysn
rxsn “ rysn
Então g é injetiva. Sabemos que uma função injetiva entre conjuntos finitos tem que ser sobrejetiva; então gé bijeção. Mostramos a mão que g é sobrejetiva. Seja rysn P UpZ{nZ, ¨q. É facil ver que gprbsn ¨ rysnq “ rysn.
O fato que g é bijetiva diz que g é uma permutação do conjunto UpZ{nZ, ¨q. Em outras palavras,denotamos o conjunto UpZ{nZ, ¨q “ trα1sn, . . . , rαϕpnqsnu. O fato que g é uma permutação deste conjuntosignifica que podemos re-escrever este conjunto como
UpZ{nZ, ¨q “ trα1sn, . . . , rαϕpnqsnu “ tgprα1snq, . . . , gprαϕpnqsnqu ,
ou seja os elementos gprα1sn, . . . , gprαϕpnqsnq coincidem (a menos da ordem, que pode ter estado alteradapor g) com os elementos rα1sn, . . . , rαϕpnqsn.
Seja agora z :“śϕpnqi“1 rαisn P UpZ{nZq. Temos que
z “
ϕpnqź
i“1
rαisn “
ϕpnqź
i“1
gprαisnq “
ϕpnqź
i“1
rasn ¨ rαisn “ rasϕpnqn
ϕpnqź
i“1
rαis “ rasϕpnqn z
Multiplicando agora por o inverso multiplicativo w de z temos
r1sn “ zw “ rasϕpnqn zw “ rasϕpnqn
o que é equivalente ao fatoaϕpnq ” 1 mod n .
Teorema 41 (Wilson). Seja p P N. Então p é primo se e somente se
pp´ 1q! ” ´1 mod p .
37
Demonstração. A necessidade da condição de primalide para ter pp´1q! ” ´1 mod p é facilmente verificada:de fato, se p não é primo, então p se fatora p “ ab, com 1 ă a ă p, 1 ă b ă p. Mas então a � pp ´ 1q!,b � pp´ 1q! e a � ppp´ 1q!, pq, b � ppp´ 1q!, pq, que implicamo ppp´ 1q!, pq ‰ 1. Então pp´ 1q! não pode sercongruente a ´1 mod p, porque se o fosse teriamos ppp´ 1q!, pq “ 1.
Mostramos a suficiencia da condição de primalidade para ter pp´ 1q! ” 1 mod p. A suficiencia é obviase p “ 2. Tomamos então p ‰ 2. Seja agora R a relação definida em UpZ{pZq “ tr1sp, . . . , rp´1spu da formaseguinte:
xRy ðñ px “ yq _ pxy “ r1spq
ou seja, dois elementos em UpZ{pZq são em relação se e somente se ou são iguais ou são um inverso dooutro. Esta relação é de equivalencia, porque é trivialmente reflexiva e simétrica, e facilmente transitiva(deixamos ao estudante provar a transitividade). Então as classes de equivalencia Ci, i “ 1, . . . , k, formamuma partição de UpZ{pZq. Em particular Yki“1Ci “ UpZ{pZq e Ci X Cj “ H se i ‰ j e cada Ci ‰ H.
Provamos agora o fato seguinte: |Ci| “ 1 se e somente se Ci contem r1sp ou rp´1sp “ r´1sp. Obsevamosque r1sp {R r´1sp, se p primo diferente de 2, então r´1sp e r1sp pertencem a classes distintas. Observamostambém que |Ci| “ 1 se e somente se Ci contém um único elemento x, que tem que ser inverso de si mesmo.Provamos então que em UpZ{pZq os únicos inversos de si mesmos são r1sp e r´1sp. De fato x “ rksp é inversode si mesmo se e somente se k2 ” 1 mod p, o que é equivalente ao fato de p � k2 ´ 1 “ pk ´ 1qpk ` 1q. Masentão p � k ´ 1 ou p � k ` 1. No primeiro caso k ” 1 mod p, no segundo k ” ´1 mod p (e os dois nãose realizam ao mesmo tempo se p ą 2). Mas então as únicas possibilidades são x “ r˘1sp como querido.Então as classes de equivalencia de r1sp e r´1sp contém só um elemento, enquanto todas as outras contemexactamente dois elementos. Então k “ pp ´ 1 ´ 2q{2 ` 2 “ pp ´ 3q{2 ` 2 “ pp ` 1q{2. Seja C1 a classe der1sp e Ck a classe de r´1sp. Temos
rpp´ 1q!sp “ź
xPUpZ{pZqx “
kź
i“1
ź
xPCi
x “ r1sp
˜
k´1ź
i“2
ź
xPCi
x
¸
r´1sp “ r´1sp
k´1ź
i“2
ź
xPCi
x
mas agora, por i “ 2, . . . , k´ 1, temos que Ci “ txi, x´1i u com xi ‰ x´1
i , e entãoś
xPCix “ 1. Então temos
que
rpp´ 1q!sp “ r´1sp
k´1ź
i“2
ź
xPCi
x “ r´1sp
k´1ź
i“2
r1sp “ r´1sp
o que significapp´ 1q! ” ´1 mod p .
Exercício 8. Calcular pn´ 1q! mod n quando n não é primo.
(13/11: aula 28). Subgrupos, classes laterais esquerdas e direitas, conjunto quociente G{H.Subgrupos. Um subgrupo H de um grupo pG, ¨q é um subconjunto que "herda"a operação de G, e, com
ela, fica um grupo. Mais precisamente
Definição 32. Seja pG, ¨q um grupo, com elemento neutro e. Um subconjunto H Ď G é um subgrupo de Gse
i) @x, y P H, x ¨ y P H (ou seja H é fechado pela operação ¨ de G).
ii) e P H (o elemento neutro de G) esta em H.
iii) @x P H, x´1 P H ou seja, o inverso x´1 (em G) pertence a H. (ou seja, H é fechado por inversão).
38
Observação 38. Sejam pG, ¨q e H Ď G um subgrupo, como na definição precedente. Então a operação ¨ˇ
ˇ
HˆH,
restringida a H ˆH, define uma operação
¨ˇ
ˇ
HˆH: H ˆH - H
por o ponto i) da definição acima. Esta operação é automaticamente associativa, porque é a mesma operaçãode G e ela é associativa em G. Além disso, se x P H, temos x ¨ e “ e ¨ x “ x, em H, porque agora e P H:então o elemento neutro e de G fica agora o elemento neutro de H. Finalmente, todo elemento de x de Htem um inverso x´1 que pertence a H. De fato temos a equação xx´1 “ x´1x “ e em G, mas agora ela valem H (todos os elementos estão em H). Então H é grupo com a estrutura induzida por G.
Exemplo 11. Se vê facilmente que nZ é subgrupo de Z.
Exemplo 12. Seja G um grupo e seja g P G. O conjunto xgy “ tgm | m P Zu é um subgrupo de G. Aqui sem é negativo, gm é definido como gm “ pg´1q´m. Dizemos que xgy é o subgrupo gerado por g.
Definição 33. Seja pG, ¨q um grupo e H um seu subgrupo. Seja g P G. Definimos as classes lateraisesquerdas e direitas gH e Hg como os conjuntos
gH “ tgh | h P Hu
Hg “ thg | h P Hu
Lema 10. Seja pG, ¨q um grupo e H um seu subgrupo. Temos as seguintes equivalencias:
xH “ yH ðñ y´1x P H ðñ x´1y P H
Hx “ Hy ðñ xy´1 P H ðñ yx´1 P H
Proposição 24. Seja pG, ¨q um grupo e H um seu subgrupo. As relações L „H e R„H definidas respecti-vamente em G como
x L„H y ðñ xH “ yH
xR„H y ðñ Hx “ Hy
são de equivalencias com classes de equivalencias
rxsL„H
“ xH
rxsR„H
“ Hx .
Proposição 25. A involução5 ω : G - G dada por a inversão ωpgq “ g´1 induz uma bijeção pω entre osconjuntos quocientes
pω : G{ L„Hbij- G{R„H .
Demonstração. A função ω verifica ω2 “ id, então é uma involução, ou seja, é inversível e coincide com asua inversa. Então ω é bijetiva. Consideramos agora a composição
πR ˝ ω : Gω- G
πR- G{R„H
5Dizemos involução uma função f : X - X tal que f2 “ id
39
onde πR é a projeção quociente de G sobre G{R„H . Temos o diagrama
Gω - G
G{ L„H
πL
?G{R„H
πR
?
πR˝ω
-
onde πL é a projeção quociente de G sobre G{ L„H . Mostramos que πR ˝ ω desce a uma função
pω : G{ L„H - G{R„H ,
ou seja, que πR ˝ω fatora como πR ˝ω “ pω ˝πL por uma aplicação pω : G{ L„H - G{R„H . Por a teoriageral, isto acontece se e somente se
x L„H y ùñ πR ˝ ωpxq “ πR ˝ ωpyq .
Agora temos que
πR ˝ ωpxq “ πR ˝ ωpyq ðñ Hx´1 “ Hy´1 ðñ y´1px´1q´1 P H ðñ y´1x P H ðñ xH “ yH
ou seja mostramos quexH “ yH ðñ πR ˝ ωpxq “ πR ˝ ωpyq .
Isto implica que não só πR ˝ ω desce, mas desce a uma função injetiva pω : G{ L „H - G{R „H talque πR ˝ ω “ pω ˝ πL. Dado que πL é sobrejetiva e ω é sobrejetiva, temos que πR ˝ ω é sobrejetiva, e queentão pω ˝ πL é sobrejetiva; mas se uma composição é sobrejetiva, a segunda função (neste caso pω tem queser sobrejetiva. Então pω é bijetiva. Ela manda xH em Hx´1.
Observação 39. A proposição precedente afirma que os conjuntos quocientes, pelo menos do ponto de vistaconjuntistico, são muito parecidos. Em particular, tem o mesmo cardinal.
Definição 34. Seja pG, ¨q um grupo e H um seu subgrupo. Denotamos com G{H um dos conjuntosquocientes G{ L „H ou G{R „H , fixado uma vez por todas, dependentemente do gosto do autor e daconveniencia do uso do objeto matemático. Para nos, neste curso, denotaremos com
G{H :“ G{ L„H“ tgH | g P Gu .
O cardinal de G{H serà indicado com rG : Hs e serà chamado o indice de H em G.
Observação 40. Denotamos com π : G - G{H a projeção quociente. Como em qualquer relação deequivalencia, temos
π´1pgHq “ gH
onde o gH de esquerda é um ponto de G{H, e o gH de direita é um subconjunto de G. A π não é bijetiva,então neste caso π´1pgHq “ tx P G | πpxq “ gHu denota o subconjunto pre-imagem de gH por π.
Observação 41. Em geral, o cojunto quociente G{H não tem estrutura de grupo, a menos que H não tenhaalguma outra hipótese adicional (ser subgrupo normal, ou que não definiremos). Em particular, em geral,não ha uma estrutura de grupo tal que a projeção quociente π : G - G{H seja um homomorfismo. Temosuma tal estrutura se e somente se a operação em G{H é definida como
pg1Hqpg2Hq :“ g1g2H .
Mas esta, em geral, não é bem definida. Por exemplo se tomamos G “ σ3, e H “ σ12 “ tτ P σ3 | τp3q “ 3u,a operação acima não é bem definida.
40
Observação 42. Se G (e então H) é comutativo, então a posição
pg1Hqpg2Hq :“ g1g2H
bem define uma operação em G{H, que torna G{H um grupo, como elemento neutro H, e com inversopgHq´1 “ g´1H. De fato, se g1H “ k1H e se g2H “ k2H, temos k´1
1 g1 P H, k´12 g2 P H, e então
k´11 g1k
´12 g2 P H, mas dado que tudo é comutativo, temos
k´11 k´1
2 g1g2 P H
o que é equivalente a (porque G é comutativo)
k´12 k´1
1 g1g2 P H ðñ pk1k2q´1g1g2 P H ðñ k1k2H “ g1g2H
o que implica que a operaçãopg1Hqpg2Hq :“ g1g2H
é bem definida. Deixamos ao estudantes provar que ela é associativa e que tem como elemento neutro H ecomo inveso do elemento gH o elemento g´1H. Com esta operação a projeção quociente π : G - G{H éum homomorfismo sobrejetivo de grupos.
Exercício 9. Provar que tomando G “ Z e H “ nZ, com n P N, n ě 2, e fazendo a construção G{H descritaacima, se obtem exactamente o grupo aditivo Z{nZ das classes de resto.
Lema 11. Seja pG, ¨q um grupo e seja H um seu subgrupo. Seja g P G e consideramos a classe lateral gH.Então a multiplicação a esquerda por g´1 induz uma bijeção
gHbij - H
gh - h
com o subgrupo H.
Observação 43. Analogamente se demonstra que qualquer classe lateral direita Hg é em bijeção com osubgrupo H (bijeção induzida pela multiplicação a direita por g´1. ).
Lema 12. Seja f : X -- Y uma sobrejeção entre dois conjuntos. Supomos que exista um terceiro conjuntoZ tal que, por cada y P Y temos uma bijeção
ψy : f´1pyqbij- Z .
Então existe uma bijeçãoΨ : X
bij- Y ˆ Z .
Demonstração. Seja x P X. Observamos que x P f´1pfpxqq, ou seja, x pertence necessariamente à fibra def sobre fpxq. Definimos uma função Ψ : X - Y ˆ Z da seguinte forma
Ψ : X - Y ˆ Z
x - pfpxq, ψfpxqpxqq
Tentamos de definir uma função inversa Φ : Y ˆ Z - X, da seguente forma
Φ : Y ˆ Z - X
py, zq - ψ´1y pzq
41
Provamos agora que são uma inversa da outra: neste caso seram inversíveis e então bijetivas ambas. Temosque provar que
ΨΦ “ idYˆZ
ΦΨ “ idX .
Provamos a primeira: reparamos que ψ´1y pzq P f´1pyq, ou seja, pertence à fibra de f sobre y. Então
fpψ´1y pzqq “ y.
ΨΦpy, zq “ Ψpψ´1y pzqq “ pfpψ
´1y pzqq, ψfpψ´1
y pzqqpψ´1y pzqqq “ py, ψypψ
´1y pzqqq “ py, zq .
Provamos a segunda:ΦΨpxq “ Φpfpxq, ψfpxqpxqq “ ψ´1
fpxqpψfpxqpxqq “ x .
Observação 44. Seja f : X -- Y uma sobrejeção entre dois conjuntos. Supomos adicionalmente que X éfinito (então Y é finito, necessariamente) e que existe k P N˚ tal que todas as fibras f´1pyq tenham o mesmocardinal k. Então, sem usar o lema precedente, temos que
|X| “ k|Y | .
Demonstração. Temos que a familia tf´1pyquyPY é uma partição finita do conjunto X. Então
|X| “ÿ
yPY
|f´1pyq| “ÿ
yPY
k “ kÿ
yPY
1 “ k|Y | .
Definição 35. Seja G um grupo e H um seu subgrupo. Chamamos indice rG : Hs do subgrupo H em G ocardinal
rG : Hs :“ |G{H| .
Teorema 42 (Lagrange). Seja pG, ¨q um grupo e seja H Ă G um seu subgrupo. Então existe uma bijeção6
Gbij- G{H ˆH .
Em particular, em termos de cardinais|G| “ rG : Hs|H| .
Consequentemente, se G é um grupo finito, a ordem do subgrupo H divide a ordem do grupo G.
Demonstração I: caso geral. Consideramos a projeção quociente π : G - G{H. Dado que G{H “
G{L „H e que L „H é uma relação de equivalencia. temos que π´1pgHq “ gH. Mas então, pelo lema11, temos que existe uma bijeção, induzida pela multiplicação a esquerda por g´1:
ψgH : π´1pgHq “ gH - H .
Mas então, pelo lema 12 existe uma bijeção
Gbij- G{H ˆH .
As outras afirmações seguem diretamente dessa.6esta bijeção é longe de ser um isomorfismo em geral
42
Demonstração II: caso G finito. . No caso em que G é um grupo finito, não é preciso usar o lema ??.Consideramos a sobrejeção π : G - G{H. Todas as fibras de π tem cardinal |gH| “ |H|, pelo lema 11.Mas então, aplicando a observação 44, temos
|G| “ |G{H||H| “ rG : Hs|H| .
(22/11: aula 29).
Definição 36. Seja pG, ¨, eq um grupo e seja g P G um seu elemento. Supomos que exista m P N˚ tal quegm “ e. Então definimos7 a ordem de g em G o inteiro positivo
ordGpgq :“ mintm P N˚ | gm “ eu .
Se não existe m P N˚ tal que gm “ e dizemos que ordGpgq é infinito.
Proposição 26. Seja G um grupo e seja g um elemento de ordem finita, dizemos ordGpgq “ m0 P N˚.Então
• Todos os elementos e, g, . . . , gm0´1 são distintos,
• xgy “ te, g, . . . , gm0´1u ;
• em particular |xgy| “ ordGpgq .
Demonstração. Provamos o primeiro ponto. Sejam 0 ď i ă j ď m0 ´ 1. Provamos que gi ‰ gj . Sefosse gi “ gj , multiplicando por g´i “ pg´1qi, teriamos gj´i “ e, mas então j ´ i P N˚, e gj´i “ e, masj ´ i ă m0 “ mintn P N˚ | gn “ eu. Absurdo. Então gi ‰ gj .
Provamos o segundo ponto. É claro que temos te, g, . . . , gm0´1u Ď xgy, por definição de xgy. Provamosque val a inclusão oposta. Seja gs P xgy. Dividimos s por m0: temos s “ m0q ` r, com 0 ď r ď m0 ´ 1.Então
gs “ gm0q`r “ pgm0qqgr “ eqgr “ egr “ gr P te, g, g2, . . . , gm0´1u .
O terceiro ponto é consequencia imediata do segundo, por que |xgy| “ |te, g, g2, . . . , gm0´1u| “ m0 “
ordGpgq.
Corolário 9. Seja G um grupo finito. Seja g P G. Então ordGpgq � |G|.
Demonstração. O conjunto |xgy| é subgrupo de G. Então ordGpgq “ |xgy| � |G|.
Corolário 10. Seja G um grupo. Seja g P G. Então
gm “ e Dm ‰ 0 ðñ a ordem de g é finita e ordGpgq � m .
Demonstração. Provamos a implicação ùñ . Provamos antes de tudo que existe n P N˚ tal que gn “ e.O que sabemos é que existe m P Z˚ tal que gm “ e. Se m P N˚, então não ha nada a demonstrar. Sem ă 0, então multiplicando a gm “ e por g´m “ pg´1qm, temos g´m “ e, e ´m P N˚. Então existe m P N˚
tal que gm “ e. Então g é de ordem finita, o que implica que |G| “ |xgy| é finito, porque ordGpgq “ |xgy|.Provamos que ordGpgq � m. Denotamos com m0 :“ ordGpgq. Dividimos m por m0: temos m “ m0q ` r,com 0 ď r ď m0 ´ 1. Com a mesma conta feita na proposição precedente, temos
e “ gm “ gm0q`r “ pgm0qqgr “ gr .
7aqui usamos implicitamente o PBO para dizer que o conjunto tm P N˚ | gm “ eu tem minimo
43
Agora, se r ą 0, teriamos que gr “ e, e r ă m0 “ mintn P N˚ | gn “ eu. Absurdo. Então r “ 0. Entãom “ m0q, ou seja ordGpgq � m.
A implicação ðù é imediata, porque, chamado m0 “ ordGpgq, se temos m “ m0q, temos também quegm “ gm0q “ pgm0qq “ eq “ e.
Exercício 10. Seja G um grupo. Seja g P G. Então
gm “ gncom m ‰ n ðñ a ordem de g é finita e m ” n mod ordGpgq .
Corolário 11 (Euler-Fermat). Seja n P N, n ě 2. Seja a P Z, pa, nq “ 1. Então
aϕpnq ” 1 mod n .
Demonstração. O fato que pa, nq “ 1 é equivalente a dizer que rasn P UpZ{nZ, ¨q. Mas então
ordUpZ{nZqprasnq � |UpZ{nZ, ¨q| “ ϕpnq .
Mas pelo corolário 10 temos então querasϕpnqn “ r1sn
o que é equivalente aaϕpnq ” 1 mod n .
Exercício 11. Encontrar todos os x P Z tais que
r4s7x´565 “ r´1s65 .
Solução. Temos p4, 65q “ 1 e então r4s65 é multiplicativamente inversivel em Z{65Z. A equação só temsolução se r´1s65 P xr4s65y. Agora, por Euler-Fermat, temos
r4sϕp65q65 ” r1s65
e então ordpr4s65q � ϕp65q “ ϕp5qϕp13q “ 4 ¨ 12 “ 48. Mas é facil ver que r4s265 “ r16s65, r4s365 “ r´1s65 eque então ordpr4sq “ 6. Então a equação fica:
r4s7x´565 “ r4s365
Mas isto acontece se e somente se7x´ 5 ” 3 mod 6
o que é equivalente a x ” 2 mod 6.
Definição 37. Seja G um grupo. Dizemos que G é cíclico se existe g P G (chamado gerador) tal queG “ xgy.
Proposição 27. Seja G um grupo cíclico, gerado por g P G, ou seja G “ xgy. Então
• G é infinito se e somente se Em P N˚ tal que gm “ e.
• G é finito se e somente se Dm P N˚ tal que gm “ e.
Demonstração. A segunda segue diretamente do corolário 10. A primeira é equivalente à segunda (ou seja asegunda é da forma A ðñ B e a primeira é equivalente a A ðñ B).
44
Teorema 43 (Classificação dos grupos cíclicos). Seja G um grupo cíclico, gerado por g P G, ou seja G “ xgy.
• Se G é infinito, a função
ϕ : Z - G
m - gm
é isomorfismo.
• Se G é finito e |G| “ m, então a função ϕ, definida acima, é sobrejetiva, mas não injetiva, e induz umisomorfismo
pϕ : Z{mZ - G
rksm - gk
Demonstração. 1. Consideramos a função ϕ : Z - G que manda m - gm. É claramente sobrejetiva.Provamos que é injetiva. Se fosse ϕpm1q “ ϕpm2q, com m1 ‰ m2 — podemos assumir sem falta degeneralidade que m2 ą m1 — então gm1 “ gm2 , então, multiplicando os dois lados por g´m1 “ pg´1qm1 ,temos
gm2´m1 “ e
e então existe s “ m2´m1 P N˚ tal que gs “ e. Mas então pelo corolário 10 G é finito. Absurdo. Mas entãoϕ é injetiva.
Só falta provar que ϕ é homomorfismo de grupos, ou seja, que
ϕpm1 `m2q “ ϕpm1qϕpm2q .
Mas
ϕpm1 `m2q “ gm1`m2 “ gm1 ¨ gm2 “ ϕpm1q ¨ ϕpm2q
pelas propriedades das potencias em grupos quaisquer. Então ϕ é homomorfismo bijetivo, ou seja, isomor-fismo.
2. Temos que |G| “ |xgy| “ ordGpgq “ m “ mintn P N˚ | gn “ eu. Consideramos mais uma vez a funçãoϕ : Z - G que manda m - gm. É claramente sobrejetiva. Ela não é injetiva. De fato temos, peloexercicio precedente:
ϕpm1q “ ϕpm2q ðñ gm1 “ gm2 ðñ m1 ” m2 mod m
Mas isto implica que ϕ desce a uma função bem definida e injetiva
pϕ : Z{mZ - G
que manda rksm - gk. Dado que ϕpkq “ pϕprksmq “ gk por cada k P Z, resulta que pϕ é necessariamentesobrejetiva, e então bijetiva. Mas pϕ é também homomorfismo de grupos dado que
pϕprk1sm ` rk2smq “ pϕprk1 ` k2smq “ gk1`k2 “ gk1 ¨ gk2 “ pϕprk1smq ¨ pϕprk2smq .
Então pϕ é isomorfismo de grupos.
(27/11: aula 30). Revisão.
45
