Álgebra para alunos de Ciências de Computadores
Full text
´
Algeb a
Ch is ian Lomp
2004
2
Sum´a io
1 P elimina es 5
1.1 L´ogica ............................... 5
1.2 Conjun os ............................. 8
1.3 O p inc´ıpio da Indu¸c˜ao . . . . . . . . . . . . . . . . . . . . . . 10
1.4 Rela¸c˜oes.............................. 11
2 A i m´e ica 19
2.1 Di iso es e m´ul iplos . . . . . . . . . . . . . . . . . . . . . . . 19
2.2 M´aximo di iso comum . . . . . . . . . . . . . . . . . . . . . . 21
2.3 N´ume os p imos e ac o iza¸c˜ao . . . . . . . . . . . . . . . . . . 27
3 A i m´e ica modulo n33
3.1 Cong uˆencias ........................... 33
3.2 Resolu¸c˜ao da cong uˆencia linea ax ≡b(modn)......... 36
3.3 O pequeno Teo ema de Fe ma . . . . . . . . . . . . . . . . . 40
3.4 Sis ema c ip og ´a ico RSA . . . . . . . . . . . . . . . . . . . . 42
3.5 Rep esen a¸c˜ao na base n . . . . . . . . . . . . . . . . . . . . . 45
4 Pe mu a¸c˜oes 49
4.1 Og uposim´e ico......................... 49
4.2 Ciclos e T ansposi¸c˜oes . . . . . . . . . . . . . . . . . . . . . . 54
4.3 Pe mu a¸c˜oes pa es e ´ımpa es . . . . . . . . . . . . . . . . . . . 59
5 Mon´oides e G upos 63
5.1 Ope a¸c˜oes Bin´a ias . . . . . . . . . . . . . . . . . . . . . . . . 63
5.2 Mon´oides ............................. 64
5.3 In e ibilidade em mon´oides . . . . . . . . . . . . . . . . . . . 66
5.4 G upos............................... 67
5.5 G uposc´ıclicos .......................... 72
5.6 Classes la e ais e o Teo ema de Lag ange . . . . . . . . . . . . 74
3
4SUM ´
ARIO
6 An´eis e co pos 81
6.1 An´eis................................ 81
6.2 Ideais e Teo ema Fundamen al do Homomo ismo . . . . . . . 84
6.3 Dom´ınios de In eg idade e Co pos . . . . . . . . . . . . . . . . 87
Cap´ı ulo 1
P elimina es
1.1 L´ogica
Nes e cu so s´o conside amos a i ma¸c˜oes(p oposi¸c˜oes) ela i amen e as quais
podemos decidi se s˜ao e dadei as ou alsos. Po exemplo a a i ma¸c˜ao ”Es e
ase ´e alsa.” ´e uma a i ma¸c˜ao inadmiss´ı el.
Sejam AeBa i ma¸c˜oes. Temos as seguin es ope a¸c˜oes:
conjuga¸c˜ao A∧B´e e dadei a se e s´o se A´e Bs˜ao e dadei as.
disjun¸c˜ao A∨B´e e dadei a se e s´o se Aou B´e e dadei a.
implica¸c˜ao A⇒B´e e dadei a se e s´o se B´e e dadei a ou A´e alsa.
equi alˆencia A⇔B´e e dadei a se e s´o se AeBs˜ao ambos e dadei as
ou ambas alsas.
nega¸c˜ao ¬A´e e dadei a se e s´o se A´e alsa.
Podemos ep esen a es es ope a¸c˜oes po uma abela de e dade (em
ela¸c˜ao com os alo es de AeB). A le a F ep esen a o alo ” alsa”e
a le a V ep esen a o alo ” e dadei a”.
A B A ∧B A ∨B A ⇒B A ⇔B¬A
F F F F V V V
F V F V V F V
V F F V F F F
V V V V V V F
Es es abelas dizem-se amb´em abelas de e dade. Seja A(X1, . . . , Xn)
uma a i ma¸c˜ao que depende das a i´a eis X1, . . . , Xncujos alo es ´e Fou V.
A abela de e dade de A´e uma abela onda pa a oda a combina¸c˜ao de F
eVpo X1, . . . , Xno alo de A(X1, . . . , Xn) ´e egis ado.
5
6CAP´
ITULO 1. PRELIMINARES
Po exemplo: Seja A(X, Y ) a a i ma¸c˜ao que ´e e dade se e s´o se X´e
e dade e Y´e also. En ˜ao a abela de e dade de A´e:
X Y A(X, Y )
F F A(F, F) = F
F V A(F, V ) = F
V F A(V, F) = V
V V A(V, V ) = F
Duas a i ma¸c˜oes A(X1, . . . , Xn) e B(X1, . . . , Xn) que dependem da al-
gumas a i´a eis X1, . . . , Xns˜ao equi alen es se ˆem a mesma abela de
e dade.
Seja A(X, Y ) a a i ma¸c˜ao do exemplo an e io e seja B(X, Y ) := ¬(X⇒
Y). En ˜ao emos que as a i ma¸c˜oes AeBs˜ao equi alen es. Esc e emos
A≡B.
Exe c´ıcio 1.1.1 Ve i ique que as duas a i ma¸c˜oes (X∧(¬Y)) ∨((¬X)∧Y)
e¬(X⇔Y)s˜ao equi alen es.
Obse a¸c˜ao 1.1.2 As seguin es a i ma¸c˜oes s˜ao e dadei as pa a a i ma¸c˜oes
A, B eC:
(1) [A⇒B]≡[B∨(¬A)]
(2) ¬(A∧B)≡(¬A)∨(¬B)
(3) ¬(A∨B)≡(¬A)∧(¬B)
(4) A∧(B∨C)≡(A∧B)∨(A∧C)
(5) A∨(B∧C)≡(A∨B)∧(A∨C)
(6) ¬(¬A)≡A
(7) A∧B=B∧A
(8) A∨B=B∨A.
Demons a¸c˜ao: Exe c´ıcio.
As equi alˆencias (2) e (3) dizem-se as leis de DeMo gan.
Quan i icado es
Suponhamos que que emos aze a i ma¸c˜oes sob e alguns objec os/en idades.
Po exemplo sob e ”os alunos da FCUP”. H´a duas manei as de o mula es as
a i ma¸c˜oes:
1.1. L ´
OGICA 7
•A i ma¸c˜oes que s˜ao alidas pa a odos os objec os; po exemplo a
a i ma¸c˜ao ”Todos os alunos da FCUP ˆem um n´ume o mecanog ´a ico”.
•A i ma¸c˜oes que s˜ao alidas pa a (pelo menos) um objec o; po exemplo
a a i ma¸c˜ao ”Exis e um aluno da FCUP que em cabelo lou o.”
Na linguagem de ma em´a ica esc e emos
∀x:P(x)
pa a dize que odo o objec o x em a p op iedade P(x). E esc e emos
∃x:P(x)
pa a dize que exis e (pelo menos) um objec o xque em a p op iedade
P(x). Temos semp e de indica a qual objec os nos e e imos. Po exemplo;
seja Ao conjun o das alunos da FCUP e seja P(x)= ” x em um n´ume o
mecanog ´a ico ”. Podemos cons ui a a i ma¸c˜ao ∀x∈A:P(x).
Obse a¸c˜ao 1.1.3 A nega¸c˜ao das a i ma¸c˜oes que con ˆem quan i icado es ´e
impo an e. Seja P(x)uma p op iedade.
(1) A nega¸c˜ao da a i ma¸c˜ao ” odos objec os x ˆem a p op iedade P” ´e equi -
alen e da a i ma¸c˜ao ”exis e (pelo menos um) objec o xque n˜ao em a
p op iedade P”. Em linguagem simb´olica, esc e emos: ¬(∀x:P(x)) ≡
∃x:¬P(x)
(2) A nega¸c˜ao da a i ma¸c˜ao ”exis e um objec o x que em a p op iedade P”
´e equi alen e da a i ma¸c˜ao ” odos os objec os x n˜ao ˆem a p op iedade
P”. Em linguagem simb´olica, esc e emos: ¬(∃x:P(x)) ≡ ∀x:¬P(x)
Em ez de ¬(∃x:P(x)) esc e emos amb´em @x:P(x).
Exemplo 1.1.4 Seja Ro conjun o dos n´ume os eais. Conside amos as
seguin es a i ma¸c˜oes:
(1) ∀x∈R:x2>0.
(2) ∃x∈R:x2>0.
(3) @x∈R:x2>0.
S´o a a i ma¸c˜ao em (2) ´e e dadei a; as ou as s˜ao alsas.
8CAP´
ITULO 1. PRELIMINARES
Seja P(x, y) uma p op iedade que depende de dois objec os. Po exemplo
a p op iedade ”x+y= 0” pa a x, y ∈R´e uma p op iedade P(x, y) que
depende de dois objec os xey. Temos:
[∃x∃y:P(x, y)] ≡[∃y∃x:P(x, y)]
[∀x∀y:P(x, y)] ≡[∀y∀x:P(x, y)].
En ˜ao a o dem das quan i icado es do mesmo ipo n˜ao in e esse.
Mas cuidado ! Ge almen e a o dem das quan i icado es de dois ipos
di e en es ´e impo an e:
[∀x∃y:P(x, y)] 6≡ [∃y∀x:P(x, y)]
Po exemplo: seja P(x, y) = ”x+y= 0” pa a x, y ∈Ren ˜ao a a i ma¸c˜ao
(∀x∈R)(∃y∈R) : x+y= 0
´e e dadei a (pa a um x∈Rescolhemos y=−x). Mas a a i ma¸c˜ao
(∃y∈R)(∀x∈R) : x+y= 0
´e alsa; se exis e um y∈R al que pa a odo x∈R:x+y= 0 emos em
pa icula 0+y= 0 que implica y= 0. Mas 1 = 1+0 = 1 +y= 0 ´e absu do.
O p oblema ´e que na ase ”pa a odos x exis e um y al que ...” o y
pode depende de x. Ou seja pa a qualque xexis e um ycom uma ce a
p op iedade mas es e ypode se di e en e pa a di e en es x. No en an o na
ase ”exis e um y al que pa a odos o x ...” o y´e ixo pa a odos os x.
1.2 Conjun os
Um conjun o ´e uma colec¸c˜ao de alguns objec os. Os objec os de um con-
jun o chamam-se elemen os. Esc e emos a∈Ase a´e um elemen o do
conjun o Aou a6∈ Ase an˜ao ´e um elemen o de A. Dois conjun os s˜ao
iguais se ˆem os mesmos elemen os. Po exemplo os conjun os A={0,1,2}
eB={0,0,0,1,1,2}s˜ao iguais; A=B. Esc e emos |A|pa a o n´ume o de
elemen os do conjun o de A. Se A em um n´ume o in ini o de elemen os
esc e emos |A|=∞. No a-se | {0,0,0,1,1,2} |= 3.
Exemplo 1.2.1 Temos as seguin es conjun os conhecidos:
1.2. CONJUNTOS 9
N={0,1,2,3,···} os n´ume os na u ais
Z={0,±1,±2,±3,···} os in ei os
Q={a
b|a, b ∈Z∧b6= 0}os n´ume os acionais
Ros n´ume os eais
C={a+ıb |a, b ∈R}os n´ume os complexos
Axioma do conjun o azio: Exis e um conjun o sem elemen os. Es e
conjun o chama-se o conjun o azio.
Esc e emos ∅pa a o conjun o azio. Sejam A e B conjun os. Se odo o
elemen o de A ´e amb´em um elemen o de B digamos que A ´e um subconjun o
de B e esc e emos A⊆B.
Obse a¸c˜ao 1.2.2 (i) Sejam AeBdois conjun os. Temos A=Bse e s´o
se A⊆BeB⊆A.
(ii) O conjun o azio ´e um subconjun o de odo o conjun o.
Seja Bum conjun o e seja Puma p op iedade que os elemen os xde B
ˆem ou n˜ao ˆem. En ˜ao
A:= {x∈B|x em a p op iedade P}
´e um subconjun o de B.
Seja B=R+po exemplo igual ao conjun o dos n´ume os eais posi i os
e seja P(x) =00 1
x>100 a p op iedade que um n´ume o eal x em se 1
x>1
A:= {x∈R+|x em a p op iedade P(x)}=x∈R+|1
x>1=]0,1[.
No e-se que: se B´e um conjun o e Puma p op iedade al que nenhum
elemen o de B em es a p op iedade, en ˜ao
A:= {x∈B|x em a p op iedade P}=∅.
Axioma dos conjun o das pa es: Pa a odo o conjun o B exis e um
conjun o P(B) cujo elemen os s˜ao os subconjun os de B.
Po exemplo pa a B:= {0,1,2}o conjun o das pa es P(B) de B´e igual
P(B) = {∅,{0},{1},{2},{0,1},{0,2},{1,2}, B}.
Axioma da euni˜ao: Pa a quaisque dois conjun os A e B exis e um
conjun o que consis e p ecisamen e dos elemen os de A e de B. Chama-se a
euni˜ao de A e B. Esc e emos A∪Bpa a es e conjun o.
Dado dois conjun os A e B de inimos os seguin es conjun os:
16 CAP´
ITULO 1. PRELIMINARES
Obse a¸c˜ao 1.4.23 Seja {Ai}i∈Iuma pa i¸c˜ao de um conjun o n˜ao azio
Aindexada po I. De inimos a ela¸c˜ao
R:= {(a, b)∈A×A| ∃i∈I:a∈Aieb∈Ai}.
En ˜ao R´e uma ela¸c˜ao da equi alˆencia.
Exe c´ıcio 1.4.24
Sejam A, B eCa i ma¸c˜oes. Mos e que:
1. [A⇒B]≡[(¬B)⇒(¬A)]
2. [A⇔B]≡[A⇒B∧B⇒A]
3. A∧(B∨C)≡(A∧B)∨(A∧C)
4. A∨(B∧C)≡(A∨B)∧(A∨C)
5. ¬(A∧B)≡(¬A)∨(¬B)
6. ¬(A∨B) = (¬A)∧(¬B)
Sejam A, B eCconjun os. Mos e que as seguin es igualdades s˜ao alidas:
(a) A∩(B∪C) = (A∩B)∪(A∩C)
(b) A∪(B∩C) = (A∪B)∩(A∪C)
(c) A (B∩C) = (A B)∪(A C)
(d) A (B∪C) = (A B)∩(A C)
Sejam XeYconjun os e seja :X→Yuma un¸c˜ao. Sejam AeB
subconjun os de Xe sejam DeEsubconjun os de Y. Mos e que se e i ica:
(a) (A∪B) = (A)∪ (B);
(b) (A∩B)⊆ (A)∩ (B);
(c) −1(D∩E) = −1(D)∩ −1(E);
(d) −1(D∪E) = −1(D)∪ −1(E);
(e) A⊆ −1( (A)) e ( −1( (A))) = (A);
( ) D⊇ ( −1(D)) e −1( ( −1(D))) = −1(D).
1. Desc e a os subconjun os Sn∈N[1
n+1 ,1] eTn∈N[1
n+1 ,1] de R.
1.4. RELAC¸ ˜
OES 17
2. Seja A:= Ze seja An:= {3a+n|a∈Z}pa a qualque n∈N.
A am´ılia {An}n∈N´e uma pa i¸c˜ao de Z? Quan os subconjun os An
di e en es exis em ?
3. Seja A:= R2e seja A := {(x, 3x+ )∈R2|x∈R}pa a qualque ∈
R. A am´ılia {A } ∈R´e uma pa i¸c˜ao de R2? Como pode desc e e A
geome icamen e ? A am´ılia {A } ∈N´e uma pa i¸c˜ao de R2 amb´em?
18 CAP´
ITULO 1. PRELIMINARES
Cap´ı ulo 2
A i m´e ica
Nes e cap´ı ulo es udamos as p op iedade a i m´e icas dos in ei os Z.
2.1 Di iso es e m´ul iplos
De ini¸c˜ao 2.1.1 Um in ei o adi ide um in ei o bse exis e um in ei o q al
que b=qa. Esc e emos a|bse adi ide b. O in ei o qdiz-se o quocien e,
o in ei o bdiz-se um m´ul iplo de aeadiz-se um di iso de b.bdiz-se
di is´ı el po a.
Obse a¸c˜ao 2.1.2 Sejam a,becin ei os.
(1) Se a|beb|cen ˜ao a|c.
(2) Se a|ben ˜ao −a|bea|bc pa a qualque in ei o c.
(3) Se a|bea|cen ˜ao a|b+c.
(4) Se 0|ben ˜ao b= 0.
(5) pa a qualque in ei o a emos a|0
Demons a¸c˜ao: Exe c´ıcio.
Relemb e a o dem dos in ei os: a≤bse e s´o se b−a≥0.
Obse a¸c˜ao 2.1.3 Seja bum in ei o posi i o. En ˜ao odo o di iso posi i o
de bes ´a en e 1eb.
Demons a¸c˜ao: Se a > 0 e a|b. Logo exis e um in ei o q al que b=aq.
Como aebs˜ao posi i o, q´e posi i o. En ˜ao b−a=a(q−1) >0 ou
equi alen emen e b > a.
19
20 CAP´
ITULO 2. ARITM´
ETICA
Co ol´a io 2.1.4 Seja aum in ei o. Se a|1en ˜ao a= 1 ou a=−1.
Demons a¸c˜ao: Suponhamos que a´e posi i o. En ˜ao po 2.1.3 emos a= 1.
Se a´e nega i o en ˜ao −a´e posi i o e pelo 2.1.3 −a= 1 ⇔a=−1.
Co ol´a io 2.1.5 Sejam aebin ei os. Se a|beb|aen ˜ao a=bou
a=−b.
Demons a¸c˜ao: a|bimplica que exis e um c∈Z al que b=ac eb|a
implica que exis e um d∈Zcom a=bd. Logo emos b=ac =bdc ou seja
b(1 −dc) = 0. Se b= 0 en ˜ao a= 0 po 2.1.2(4). Se b6= 0 emos 1 = dc ou
seja d|1. Po Co ol´a io 2.1.4 emos d=±1 e po an o a=±b.
Teo ema 2.1.6 (Algo i mo da di is˜ao) Seja aum in ei o e bum n´ume o
posi i o. En ˜ao exis e um in ei o qe um n´ume o ais que a=bq + e
0≤ < b.
Em ez de uma demons a¸c˜ao conside amos o seguin e algo i mo:
Algo ´ı mo da di is˜ao
INPUT:dois n´ume os posi i os aeb
OUTPUT:dois n´ume os posi i os qe al que a=bq + e 0 ≤ < b
(1) q:= 0; := 0;
(2) while(a−qb > b)q:= q+ 1;
(3) := a−qb;
Pa a um in ei o anega i o podemos aplica o algo i mo com −aebe
ob emos q0e 0 al que −a=bq0+ 0. Se 0= 0 podemos escolhe = 0 e
q=−q0. Se 06= 0 podemos escolhe := b− 0eq=−(q0+ 1). Temos
a=−(bq0+ 0) = −bq0−b+b− 0=qb + .
O n´ume o diz-se o es o eqdiz-se o quocien e da di is˜ao de bpo a.
Em qualque linguagem de p og ama¸c˜ao exis em un¸c˜oes pa a calcula eq.
Po exemplo em C em-se := b%aeq:= b/a.
Exe c´ıcio 2.1.7 Calcule o es o e o quocien e pa a os seguin es in ei os:
(i) a= 2047, b = 128; (ii) a= 5251, b = 89; (iii) a=−34, b = 13 (i )
a= 4, b = 12;
2.2. M ´
AXIMO DIVISOR COMUM 21
2.2 M´aximo di iso comum
De ini¸c˜ao 2.2.1 Sejam aebin ei os n˜ao simul aneamen e nulos. Um in-
ei o cque di ide aebdiz-se um di iso comum en e aeb. O maio
di iso comum de aebdiz-se o m´aximo di iso comum en e aeb.
Esc e emos mdc(a, b)pa a es e in ei o posi i o.
No e que s´o exis e um m´aximo di iso comum en e dois in ei os.
Obse a¸c˜ao 2.2.2 Sejam aebin ei os n˜ao simul aneamen e nulos.
(1) mdc(a, b) = mdc(b, a)
(2) mdc(a, b) = mdc(−a, b)
(3) mdc(a, 0) = |a|
(4) mdc(a, b) = mdc(a, b +na)pa a qualque n∈Z.
Demons a¸c˜ao: (1-3) Exe c´ıcios.
(4) Todo o di iso comum en e aeb´e amb´em um di iso comum en e ae
b+na (pa a qualque n∈Z) e odo o di iso comum en e aeb+na ´e um
di iso comum en e e aeb. De ac o, se d|aed|ben ˜ao d|b+an (po
2.1.2(2+3) ) e se d|aed|b+na en ˜ao d|b+na −na, is o ´e d|b. Po an o
mdc(a, b) = mdc(a, b +na).
Co ol´a io 2.2.3 Sejam aebin ei os n˜ao simul aneamen e nulos. Seja a=
qb + com q, ∈Ze0≤ < b. En ˜ao mdc(a, b) = mdc(b, ).
Demons a¸c˜ao: Po 2.2.2(1) emos mdc(a, b) = mdc(b, a). Como =a+
(−q)b emos po 2.2.2(4) mdc(b, a) = mdc(b, ). Logo mdc(a, b) = mdc(b, ).
O ´ul imo co ol´a io ajuda calcula o m´aximo di iso comum. Po exem-
plo seja a= 45 e b= 18. O es o 45 po 18 ´e 9. Po o co ol´a io emos
mdc(45,18) = mdc(18,9). O es o de 18 po 9 ´e 0. Aplicamos o co ol´a io
de no o emos mdc(18,9) = mdc(9,0). Po 2.2.2(3) emos mdc(9,0) = 9.
Po an o:
mdc(45,18) = mdc(18,9) = mdc(9,0) = 9.
O seguin e algo i mo de Euclides (325 - 265 A.D.) usa o ´ul imo co ol´a io
pa a de e mina o mdc:
22 CAP´
ITULO 2. ARITM´
ETICA
Algo ´ı mo de Euclides
INPUT: a, b ∈N>0
OUTPUT: mdc(a, b)
while (b6= 0) do
{subs i ue ao mesmo empo apo bebpelo es o da di is~ao de a
po b.}
e u n a
Podemos implemen a acilmen e es e algo i mo na linguagem C:
in mdc(in a, in b)
{in aux;
while(b!=0) {aux=b; b=a%b; a=aux }
e u n a
}
Exemplo 2.2.4 Sejam a= 144 eb= 81. O algo i mo abalha da seguin e
o ma:
a b a%b
144 81 63 144 = 1*81 + 63 (1)
81 63 18 81 = 1*63 + 18 (2)
63 18 9 63 = 3*18 + 9 (3)
18 9 0 18 = 2*9 + 0 (4)
9 0 algo i mo e mina
Logo mdc(144,81) = 9. No e que as equa¸c˜oes (3),(2) e (1) implicam:
mdc(144,81) = 63 −3∗18 po (3)
= 63 −3∗(81 −1∗63) po (2)
= 4 ∗63 + (−3) ∗81
= 4 ∗(144 −1∗81) + (−3) ∗81 po (1)
= 4 ∗144 + (−7) ∗81
Encon ´amos in ei os es( = 4, s=−7) al que
mdc(144,81) = ∗144 + s∗81
Teo ema 2.2.5 Sejam aebin ei os n˜ao simul aneamen e nulos. En ˜ao
exis em in ei os es ais que mdc(a, b) = ∗a+s∗b.
2.2. M ´
AXIMO DIVISOR COMUM 23
Se aebs˜ao in ei os posi i os e a=qb + pa a alguns in ei os q, com
0≤ < b en ˜ao sabemos mdc(a, b) = mdc(b, ). Suponha que exis em
in ei os x, y ∈Z al que mdc(b, ) = xb +y en ˜ao emos:
mdc(a, b) = mdc(b, ) = xb +y =xb +y(a−qb) = ya + (x−qy)b.
Is o su giu o seguin e algo i mo ecu si o: Algo ´ı mo mdc
INPUT:a, b ∈Z+ex, y ∈Z
OUTPUT:mdc(a, b) = xa +yb
i (b! = 0){
de e mine qe al que a=qb + ;
aux:=mdc(b, ,x,y);
subs i ue x po y e y po x-qy;
e u n aux;
}
else
{x=1;
y=0;
e u n a;
}
Temos amb´em a seguin e e s˜ao ala gada do Algo i mo de Euclides que
n˜ao usa ecu s˜ao:
Algo ´ı mo de Euclides(ala gada)
INPUT: a, b ∈N>0
OUTPUT: x, y ∈Z al que mdc(a, b) = xa +yb
Va i´a eis auxilia : q, , u, , x, y ∈Z
Inicializa¸c~ao: x= 1; = 1; y= 0; u= 0;
while (bn~ao nulo) do
{encon e qe al que a=qb + e0≤ < b
subs i ue simul aneamen e:
apo bebpo
xpo ueupo x−qu
ypo e po y−q
}
e u n xey
24 CAP´
ITULO 2. ARITM´
ETICA
Po exemplo sejam a= 144 e b= 81. O algo i mo abalha assim:
a b x u y u
144 81 1 0 0 1 144 = 1*81 + 63
81 63 0 1 1 -1 81 = 1*63 + 18
63 18 -1 1 -1 2 63 = 3*18 + 9
18 9 -1 4 2 -7 18 = 2*9 + 0
9 0 4 -9 -7 16 algo i mo e mina
Podemos ago a mos a algumas p op iedades impo an es do m´aximo
di iso comum.
Teo ema 2.2.6 Sejam a, b edin ei os posi i os. As seguin es a i ma¸c˜oes
s˜ao equi alen es:
(a) d= mdc(a, b).
(b) d´e um di iso comum en e aeb al que odo o di iso comum posi i o
de aeb amb´em ´e um di iso de d.
(c) d´e o meno in ei o posi i o al que exis em in ei os xey al que
d=x∗a+y∗b.
A ca ac e iza¸c˜ao (c) do mdc diz:
mdc(a, b) = min{d∈Z>0| ∃x, y ∈Z:d=x∗a+y∗b}
Demons a¸c˜ao: (a)⇒(c) Seja e:= min{z∈Z>0| ∃x, y ∈Z:z=
xa +yb}. Pelo Algo i mo de Euclides exis em x, y ∈Z ais que d=xa +yb.
Como e´e o meno in ei o com es a p op iedade em-se e≤d. Po ou o lado
d´e um di iso comum en e aeb. Logo emos d| a +sb pa a quaisque
in ei os esed|eou seja d≤e. Po an o d=e.
(c)⇒(b) Seja d:= min{z∈Z>0| ∃x, y ∈Z:z=xa +yb}e sejam xey
in ei os ais que d=xa +yb. Seja cum di iso comum posi i o de aeb.
Logo exis em es al que a= c eb=sc. Po an o d=xa+(yb =x +ys)c
mos a que cdi ide d.
(b)⇒(a) Como mdc(a, b) ´e um di iso comum posi i o de aeb emos
po hip´o ese mdc(a, b)|dou seja mdc(a, b)≤d(2.1.3). Mas mdc(a, b) ´e o
m´aximo di iso comum en e aeb. Po an o em-se mdc(a, b) = d.
Em pa icula emos o seguin e co ol´a io:
Co ol´a io 2.2.7 Sejam aebin ei os posi i os e exis em in ei os xey ais
que 1 = x∗a+y∗ben ˜ao mdc(a, b) = 1.
2.2. M ´
AXIMO DIVISOR COMUM 25
Dois in ei os aebcom mdc(a, b) = 1 dizem-se ela i amen e p imos.
Obse a¸c˜ao 2.2.8 Pa a qualque in ei os a, b ∈Z {0} emos a
mdc(a,b)e
b
mdc(a,b)s˜ao ela i amen e p imos.
Demons a¸c˜ao: De ac o se um d≥1 ´e um di iso comum de a
mdc(a,b)e
b
mdc(a,b)en ˜ao exis em x, y ∈Z al que a
mdc(a,b)=xd eb
mdc(a,b)=yd. Logo
dmdc(a, b) ´e um di iso comum de aeb. Po an o dmdc(a, b)≤mdc(a, b)
po que mdc(a, b) ´e o m´aximo di iso comum. Mas is o implica d≤1 ou seja
d= 1. En ˜ao mdc( a
mdc(a,b),b
mdc(a,b)) = 1.
Co ol´a io 2.2.9 Sejam aebdois in ei os posi i os e suponha que aebs˜ao
ela i amen e p imos. Pa a qualque in ei o c emos: se a|bc en ˜ao a|c.
Demons a¸c˜ao: Pelo algo i mo de Euclides exis em in ei os xey ais que
1 = xa +yb. Logo c=xac +ybc. Se a|bc en ˜ao a|xac +ybc ⇒a|c.
Dados in ei os a, b, c ∈Zque emos encon a odos os in ei os XeY ais
que
aX +bY =c.
Uma equa¸c˜ao des e ipo diz-se uma equa¸c˜ao de Dio an o linea .
( Dio an o de Alexand ia, ma em´a ico g ego, i ia (ce ca) en e 200-284 A.D.)
Obse a¸c˜ao 2.2.10 Sejam aebin ei os n˜ao simul aneamen e nulos e ela i a-
men e p imos (mdc(a, b) = 1). Suponha que exis em in ei os XeY ais que
aX +bY = 0 en ˜ao exis e um in ei o n al que
X=−nb eY=na.
Demons a¸c˜ao: aX +bY = 0 ⇒aX =−bY . Se a= 0 emos b= 1 po que
mdc(0, b) = 1 ⇒b= 1. Logo Y= 0 = n0 e X=−npa a qualque n∈Z.
Suponha que a6= 0. Como a| −bY e mdc(a, b) = 1 emos po 2.2.9 a| −Y.
Po an o exis e n∈Z al que Y=na eaX =−bY =−nab implica X=−nb.
Teo ema 2.2.11 Sejam aebin ei os n˜ao simul aneamen e nulos. As solu¸c˜oes
in ei os XeYda equa¸c˜ao aX +bY = 0 s˜ao da o ma
X=−nb
mdc(a, b)eY=na
mdc(a, b)
pa a algum n∈Z.
32 CAP´
ITULO 2. ARITM´
ETICA
Cap´ı ulo 3
A i m´e ica modulo n
3.1 Cong uˆencias
De ini¸c˜ao 3.1.1 Seja n∈N. De inimos a seguin e ela¸c˜ao de equi alˆencia em Z:
Rn:= {(a, b)∈Z×Z|n|b−a}
Se (a, b)∈Rnen ˜ao dizemos que a´e cong uen e com bmodulo n. Esc e emos
amb´em a≡b(mod n).
Dado um in ei o a∈Z. O subconjun o de Zque consis e de odos os in ei os b
ais que a´e cong uen e com bm´odulo ndiz-se a classe de am´odulo n.
[a]n:= {b∈Z|b≡a(mod n)}
Exemplo 3.1.2 Seja n= 2 ea, b ∈Z. Suponha que a´e cong uen e com bm´odulo
2ou seja a≡b(mod 2). Po de ini¸c˜ao 2|b−a. Se a´e um n´ume o pa en ˜ao
exis e um in ei o k al que a= 2k. Tem-se 2|b−2k⇒2|b. Logo b´e um
n´ume o pa . Se a´e ´ımpa en ˜ao exis e um in ei o k al que a= 2k+ 1. Logo
2|b−2k−1⇒2|b−1ou seja b= 2l+1 pa a um l∈Z. Logo b´e ´ımpa amb´em.
Po an o se a´e cong uen e com bm´odulo 2en ˜ao aebs˜ao ambos pa ou ambos
´ımpa .
No ou o caso suponha que aebs˜ao dois n´ume os pa es en ˜ao b−a´e pa
amb´em e logo 2|b−a. Logo a´e cong uen e com bm´odulo 2. Se aebs˜ao ambos
´ımpa en ˜ao b−a´e pa e amb´em emos a´e cong uen e com bm´odulo 2.
Vimos que dois in ei os a´e bs˜ao cong uen e m´odulo 2se e s´o se ambos s˜ao
n´ume os pa es ou n´ume os ´ımpa es.
A cong uˆencia m´odulo 2di ide os in ei os em duas pa es : os n´ume os pa es
e os n´ume os ´ımpa es. A classe [a]2m´odulo 2de um elemen o aou ´e igual os
n´ume os pa es ou ´e igual os n´ume os ´ımpa es.
[a]2={os n´ume os pa es }= [0]2[a]2={os n´ume os ´ımpa es}= [1]2
33
34 CAP´
ITULO 3. ARITM´
ETICA MODULO N
Obse a¸c˜ao 3.1.3 Seja n∈N:
1. ∀a∈Z:a∈[a]npo que a≡a(mod n).
2. ∀a, b ∈Z:b≡a(mod n)⇔a≡b(mod n).
3. ∀a, b, c ∈Z:se a≡b(mod n)eb≡c(mod n)en ˜ao a≡c(mod n). Is o
implica amb´em: b≡c(mod n)⇔[b]n⊆[c]n.
4. Temos em pa icula :
[a]n= [b]n⇔[a]n∩[b]n6=∅ ⇔ a≡b(mod n)
(suponha que exis e c∈[a]n∩[b]n. En ˜ao [c]n⊆[a]n∩[b]n. Po (2) emos
amb´em a, b ∈[c]ne logo
[a]n∪[b]n⊆[c]n⊆[a]n∩[b]n,
que implica [a]n= [c]n= [b]n. Po an o [a]n∩[b]n6=∅ ⇒ [a]n= [b]n. A
ou a implica¸c˜ao ´e ob ia.)
5. As classes {[a]n}a∈Zm´odulo n o mam uma pa i¸c˜ao de Z. (Pois, como
odo o in ei o a∈Zpe ence a [a]n emos Sa∈Z[a]n=Z. Vimos na al´ınea
an e io que [a]n= [b]nou [a]n∩[b]n=∅pa a qualque a, b ∈Z.)
6. Seja a∈Z. Pelo Algo i mo da Di is˜ao exis em q, ∈Z ais que
a=qn + e0≤ < n.
Temos a− =qn ou seja a≡ (mod n). Po (4) emos [a]n= [ ]nou seja
a classe de um in ei o am´odulo n´e igual a classe do es o da sua di is˜ao
po n.
7. Pa a o conjun o das classes m´odulo nesc e emos:
Zn:= {[a]n|a∈Z}
Se n6= 0 es e conjun o em p ecisamen e nelemen os (dis in os) ou seja
|Zn|=n. Vimos na al´ınea an e io que, pa a qualque a∈Z, exis e um
n´ume o 0≤ < 0(o es o da di is˜ao de apo n) al que [a]n= [ ]n. Logo
Zn:= {[0]n,[1]n,[2]n, . . . , [n−1]n}
Exemplo 3.1.4 Seja n= 5. Qual ´e a classe de 73 m´odulo 5? Temos pa a um
in ei o b
b≡73(mod n)⇔ ∃n∈Z:b−73 = 5n
⇔ ∃n∈Z:b−14 ∗5−3 = 5n
⇔ ∃n∈Z:b−3 = 5(n+ 14)
⇔b≡3(mod5).
3.1. CONGRUˆ
ENCIAS 35
Po an o as classes [73]5e[3]5s˜ao iguais e emos:
[73]5= [3]5={b∈Z|o es o da di is˜ao de bpo 5´e 3}={5n+ 3 |n∈Z}.
Obse a¸c˜ao 3.1.5 Seja n∈Ne sejam a, a0, b, b0∈Z ais que a≡a0(mod n)e
b≡b0(mod n). Temos
(i) a±b≡a0±b0(mod n);
(ii) a∗b≡a0∗b0(mod n);
(iii) pa a qualque k∈N em-se ak≡(a0)k(mod n).
Em ge al n˜ao emos a/b ≡a0/b0(mod n) se b|aeb0|a0. Po exemplo
seja n= 4, a = 10, a0= 6, b = 10, b0= 2. Tem-se a= 10 ≡6 = a0(mod 4) e
b= 10 ≡2 = b0(mod 4) mas n˜ao emos a/b = 1 ≡a0/b0= 3(mod 4).
De ini¸c˜ao 3.1.6 Seja n∈N. Temos as seguin es ope a¸c˜oes no conjun o Zn. Pa a
qualque [a]n,[b]n∈Znde inimos:
[a]n+ [b]n:= [a+b]ne[a]n∗[b]n= [a∗b]n
Obse a¸c˜ao 3.1.7 1. As ope a¸c˜oes +e∗s˜ao independen e das escolha do
ep esen an e dos elemen os [a]n.
2. As ope a¸c˜oes +e∗s˜ao comu a i as
[a]n+ [b]n= [b]n+ [a]ne[a]n∗[b]n= [b]n∗[a]n
e dis ibu i a ela i amen e +
[a]n∗([b]n+ [c]n) = ([a]n∗[b]n) + ([a]n∗[c]n).
A a i m´e ica modula em alguns aplica¸c˜oes ´u eis:
Obse a¸c˜ao 3.1.8 A a i m´e ica modula pode se usado pa a e i ica que um
n´ume o ´e di is´ı el po 9. Seja a∈Z+. Podemos ep esen a ana o ma:
a=an10n+an−110n−1+···+a2102+a110 + a0
pa a a0, a1, . . . , an∈ {0,1, . . . , 9}ean6= 0.
Tem-se 10 ≡1(mod 9) e logo 10k≡(1)k(mod 9) = 1(mod 9). Po an o
9|a
⇔a≡0(mod 9)
⇔an10n+ +an−110n−1+···+a2102+a110 + a0≡0(mod 9)
⇔an+an−1+···+a2+a1+a0≡0(mod 9)
36 CAP´
ITULO 3. ARITM´
ETICA MODULO N
Po exemplo os n´ume os a= 1233 ea= 123456789 s˜ao di is´ı eis po 9.
Obse a¸c˜ao 3.1.9 A a i m´e ica modula ajuda amb´em a eduzi po ˆencias. Supon-
hamos que que emos decidi se o n´ume o 109+ 1 ´e di is´ı el po 19. Temos:
10 ≡(−9)(mod 19)
e logo
102≡(−9)2(mod 19) = 81(mod 19) = 5(mod 19).
Con inuando assim ob emos:
104≡(102)2(mod 19) = 52(mod 19) = 6(mod 19)
108≡(104)2(mod 19) = 62(mod 19) = (−2)(mod 19)
109≡10 ∗(10)8(mod 19) = (−20)(mod 19) = (−1)(mod 19)
109+ 1 ≡(−1) + 1(mod 19) = 0(mod 19)
Po an o 19 |109+ 1.
3.2 Resolu¸c˜ao da cong uˆencia linea ax ≡b(modn)
Em ez da equa¸c˜ao linea aX =bcom in ei os aebpodemos amb´em es uda
solu¸c˜oes da cong uˆencia linea aX ≡b(mod n).
Obse a¸c˜ao 3.2.1 As ope a¸c˜oes +e∗ ˆem um elemen o neu o. Temos
[a]n+ [0]n= [a+ 0]n= [a]n= [0 + a]n= [0]n+ [a]n
[a]n∗[1]n= [a∗1]n= [a]n= [1 ∗a]n= [1]n∗[a]n
De ini¸c˜ao 3.2.2 Um elemen o [a]n∈Zn {[0]n}diz-se in e ´ı el se exis e um
elemen o [b]n∈Zn al que
[a]n∗[b]n= [1]n
O elemen o [b]ndiz-se o in e so mul iplica i o de [a]n. No a¸c˜ao [a]−1
n:= [b]n. Um
in ei o a∈Zdiz-se in e ´ı el m´odulo nse [a]n´e in e ´ı el em Zn.
Exemplo 3.2.3 Seja n= 10 emos [3]10 ∗[7]10 = [21]10 = [1]10. Po an o [3]10 ´e
in e ´ı el e 3´e in e ´ı el m´odulo 10.
Uma solu¸c˜ao da cong uˆencia linea aX ≡b(mod n) ´e equi alen e a equa¸c˜ao
[a]n[X]n= [b]n. Se [a]n´e in e ´ı el podemos mul iplica com [a]−1
ne ob emos
[X]n= [b]n[a]−1
n.
Teo ema 3.2.4 Seja n > 1ea∈Z. As seguin es a i ma¸c˜oes s˜ao equi alen es:
3.2. RESOLUC¸ ˜
AO DA CONGRU ˆ
ENCIA LINEAR AX ≡B(MODN) 37
(a) a classe [a]n´e in e ´ı el;
(b) mdc(a, n) = 1 (ou seja aens˜ao ela i amen e p imos);
(c) a cong uˆencia aX ≡1(mod n) em uma solu¸c˜ao.
Demons a¸c˜ao: (a)⇒(b).Suponha que [a]n´e in e ´ı el. En ˜ao exis e um x∈Z
al que [1]n= [a]n∗[x]n= [ax]n. En ˜ao exis e um y∈Z al que 1 −ax =yn ⇔
1 = ax +ny. Po 2.2.7 mdc(a, n) = 1.
(b)⇒(c) Suponha que mdc(a, n) = 1 en ˜ao po 2.2.9 exis em in ei os X, Y ais
que 1 = aX +nY ou seja n|1−aX. En ˜ao aX ≡1(mod n) em uma solu¸c˜ao.
(c)⇒(a) Seja Xa solu¸c˜ao de aX ≡1(mod n) en ˜ao [a]n∗[X]n[aX]n= [1]n
implica [a]nin e ´ı el.
Co ol´a io 3.2.5 Seja pum n´ume o p imo. Todo o elemen o [a]p∈Zp {[0]p}´e
in e ´ı el.
Teo ema 3.2.6 Seja num in ei o posi i o. A cong uˆencia linea aX ≡b(mod n)
em uma solu¸c˜ao se e s´o se mdc(a, n)|b. Nes e caso as solu¸c˜oes s˜ao da o ma:
X≡ b +nk
mdc(a, n)(mod n)onde k∈ {0,1, . . . , mdc(a, n)−1}
e ∈Z al que mdc(a, n) = a +sn pa a algum s∈Z.
Demons a¸c˜ao: Sejam aeb∈Ze seja n≥1. Temos
aX ≡b(mod n)⇔n|b−aX ⇔ ∃Y∈Z:aX +nY =b.
A ul ima equa¸c˜ao ´e uma equa¸c˜ao de Dio an o linea . Po 2.2.12 es a equa¸c˜ao em
uma solu¸c˜ao se e s´o se mdc(a, n)|b. Po an o aX ≡b(mod n) em uma solu¸c˜ao
se e s´o se mdc(a, n)|n. Teo ema 2.2.12 diz amb´em que nes e caso as solu¸c˜oes
s˜ao da o ma:
X= b +nk
mdc(a, n)pa a k∈Ze , s ∈Z al que mdc(a, n) = a +sn.
Dois solu¸c˜oes b+nk
mdc(a,n)e b+nk0
mdc(a,n)s˜ao cong uen e m´odulo nse e s´o se
n| b +nk
mdc(a, n)− b +nk0
mdc(a, n)=n(k0−k)
mdc(a, n)⇔mdc(a, n)|(k0−k).
Po an o as solu¸c˜oes m´odulo ns˜ao da o ma
X≡ b +nk
mdc(a, n)(mod n) onde k∈ {0,1, . . . , mdc(a, n)−1}.
38 CAP´
ITULO 3. ARITM´
ETICA MODULO N
Exemplo 3.2.7 Que emos encon a odos as solu¸c˜oes da cong uˆencia linea 15X≡
66(mod 9). O m´aximo di iso comum en e 15 e9´e 3 = mdc(15,9) = 2 ∗15 +
(−3) ∗9. Logo = 2 e as solu¸c˜oes s˜ao da o ma:
X≡2∗66 −9k
3(mod 9)
= 44 −3k(mod 9)
= 8 −3k(mod 9)
pa a k∈ {0,1,2}. Po an o X≡8(mod 9) ou X≡5(mod 9) ou X≡2(mod 9)
s˜ao odos as solu¸c˜oes.
Obse a¸c˜ao 3.2.8 (i) Se a cong uˆencia aX ≡b(mod n) em uma solu¸c˜ao
en ˜ao qualque in ei o
X= b
mdc(a, n)+n
mdc(a, n)kpa a k∈Z
´e uma solu¸c˜ao.
(ii) Se mdc(a, n) = 1 en ˜ao s´o h´a uma solu¸c˜ao X≡ b(mod n)m´odulo n.
(iii) As solu¸c˜oes da cong uˆencia aX ≡0(mod n)s˜ao da o ma
X≡n
mdc(a, n)k(mod n)pa a k∈ {0,1, . . . , mdc(a, n)−1}
(i ) Seja c∈Zec6= 0. En ˜ao as cong uˆencias
acX ≡bc(mod nc)eaX ≡b(mod n)
ˆem as mesmas solu¸c˜oes. Tem-se:
acX ≡bc(mod nc)⇔nc |(b−aX)c⇔n|b−aX ⇔aX ≡b(mod n).
Po exemplo: 15X≡12(mod 21) ⇔5X≡4(mod 7) ⇔X≡5(mod 7).
( ) Suponha que mdc(a, n)|ben ˜ao
aX ≡b(mod n)⇔a
mdc(a, n)X≡b
mdc(a, n)mod n
mdc(a, n).
Como mdc a
mdc(a,n),n
mdc(a,n)= 1,a
mdc(a,n)´e in e ´ı el m´odulo n
mdc(a,n).
Logo exis e um ∈Z al que a
mdc(a,n)≡1(mod n
mdc(a,n)). Po an o
aX ≡b(mod n)⇔X≡ b
mdc(a, n)mod n
mdc(a, n).
3.2. RESOLUC¸ ˜
AO DA CONGRU ˆ
ENCIA LINEAR AX ≡B(MODN) 39
Teo ema 3.2.9 (Teo ema chinˆes do es o) Dados in ei os posi i os n1, . . . , nk
e in ei os a1, . . . , ak. Se mdc(ni, nj) = 1 pa a i6=jen ˜ao o sis ema das con-
g uˆencias linea es
X≡ai(mod ni)pa a i= 1, . . . , k
em uma ´unica solu¸c˜ao m´odulo n1n2···nk
Demons a¸c˜ao: Suponha que mdc(ni, nj) = 1 pa a i6=j. Pa a qualque i∈
{1,2, . . . , k}seja
ˆni:= Y
j6=i
nj:= n1···ni−1ni+1 ···nk.
Temos mdc(ni,ˆni) = 1. Logo pelo Algo i mo de Euclides exis em in ei os i, si∈Z
al que
1 = ini+siˆni
Tem-se ai=aisiˆni+ai iniou seja
aisiˆni≡ai(mod ni).
Temos amb´em
aisiˆni≡0(mod nj) pa a qualque j6=i
Seja X:= Pk
i=1 aisiˆni:= a1s1ˆn1+···akskˆnk.En ˜ao
X≡aisiˆni(mod ni)≡ai(mod ni) pa a qualque i∈ {1, . . . , k}.
Logo X´e uma solu¸c˜ao.
Suponha que X´e Ys˜ao solu¸c˜oes. En ˜ao X−Y≡0(mod ni) pa a qualque
iou seja ni|X−Y. Como mdc(ni, nj) = 1 emos n1···nk|X−YeX≡
Y(mod n1···nk).
Exemplo 3.2.10 Seja k= 3. Conside amos o sis ema:
(1) X≡3(mod 5)
(2) X≡6(mod 7)
(3) X≡4(mod 6)
Pela equa¸c˜ao (1) uma solu¸c˜ao Xdes e sis ema em se igual X= 3 + 5Ypa a um
in ei o Y. Subs i u´ımos Xpo 3+5Yna equa¸c˜ao (2) ob emos:
X≡6(mod 7)
⇔3+5Y≡6(mod 7)
⇔5Y≡3(mod 7).
40 CAP´
ITULO 3. ARITM´
ETICA MODULO N
Como mdc(5,7) = 1 |3pelo Teo ema 3.2.6 a solu¸c˜ao pa a Y´e
Y≡3 (mod 7)
onde ´e um in ei o al que exis e um s∈Ze1 = mdc(5,7) = 5 + 7s. Nes e caso
podemos escolhe = (−4) (e s= 3). Po an o
Y= (−4) ∗3+7Z=−12 + 7Z
pa a um Z∈Ze
X= 3 + 5Y= 3 + 5(−12 + 7Z) = −57 + 35Z.
Subs i u´ımos Xpo −57 + 35Zna equa¸c˜ao (3) emos
X≡4(mod 6)
⇔ −57 + 35Z≡4(mod 6)
⇔35Z≡61(mod 6)
⇔5Z≡1(mod 6)
Como mdc(5,6) = 1 |1pelo Teo ema 3.2.6 a solu¸c˜ao pa a Z´e
Z≡ (mod 6)
onde ´e um in ei o al que exis e um u∈Ze1 = mdc(5,6) = 5 + 6u. Nes e caso
podemos escolhe =−1(e u= 1). Po an o
Z=−1+6W
pa a um W∈Z. Logo
X=−57 + 35Z=−57 + 35(−1+6W) = −92 + 210W.
Como 118 ≡ −92(mod 210)
X≡118(mod 210)
´e a (´unica) solu¸c˜ao do sis ema.
3.3 O pequeno Teo ema de Fe ma
O seguin e eo ema ´e mui o impo an e e a unda¸c˜ao do sis ema c ip og ´a ico RSA.
Teo ema 3.3.1 (Pequeno Teo ema de Fe ma ) Seja pum n´ume o p imo. Pa a
qualque in ei o a∈Zse mdc(a, p) = 1 en ˜ao ap−1≡1(mod p).
Em pa icula em-se ap≡a(mod p)pa a qualque a∈Z.
3.3. O PEQUENO TEOREMA DE FERMAT 41
Demons a¸c˜ao: Seja Zp:= {[0]p,[1]p, . . . , [p−1]p}o conjun o das classes m´odulo
p. Se a∈Z´e um in ei o al que mdc(a, p) = 1 emos em pa icula p-aou seja
[a]p6= [0]p. Pelo Co ol´a io 3.2.5 sabemos que [a]p´e in e ´ı el em Zp. En ˜ao exis e
um b∈Z al que [a]p∗[b]p= [1]P. Esc e emos [a]−1
p:= [b]p. Conside amos a
un¸c˜ao
:Zp−→ Zp al que [x]p7→ [x]p∗[a]p
Como [a]p´e in e ´ı el a un¸c˜ao em um in e so
−1:Zp−→ Zp al que [x]p7→ [x]p∗[a]−1
p
Pois emos
−1( ([x]p)) = −1([x]p∗[a]p) = [x]p∗[a]p∗[a]−1
p= [x]p∗[1]p= [x]p
e emos amb´em −1([x]p)= [x]p. Po an o a imagem de ´e igual Zp(pa a
qualque [x]p emos ([x]p[a]−1
p) = [x]p).
Im( ) = {[x]p∗[a]p|x∈ {0,1, . . . , p −1}}
={[0]p,[a]p,[2a]p, . . . , [(p−1)a]p}
=Zp
={[0]p,[1]p,[2]p, . . . , [p−1]p}
Po an o o p odu o de odos os elemen os em Im( ) {[0]p}´e igual ao p odu o de
odos os elemen os em Zp {[0]p}.
[a]p∗[2a]p∗···∗[(p−1) ∗a]p= [1]p∗[2]p∗···∗[p−1]p
No e-se que o p odu o em p−1 ac o es. En ˜ao emos
(?) [ap−1(p−1)!]p= [(p−1)!]p
No e-se que p-(p−1)! (pois, se p|(p−1)! en ˜ao p|xcom 1 ≤x≤p−1 que
´e imposs´ı el.) En ˜ao pelo 3.2.5 [(p−1)!]p´e in e ´ı el e logo exis e um elemen o
[(p−1)!]−1
p∈Zp al que [(p−1)!]p∗[(p−1)]−1
p= [1]p. Mul iplicamos a equa¸c˜ao
(?) com [(p−1)!]−1
pob emos
[ap−1]p= [1]p
ou seja ap−1≡1(mod p).
Se mdc(a, p) = 1 emos ap−1≡1(mod p). Mul iplicamos com aob emos
ap≡a(mod p). Se mdc(a, p)6= 1 en ˜ao p|a⇒a≡0(mod p)⇒ap≡a(mod p).
P ecisamos a seguin e obse a¸c˜ao:
Obse a¸c˜ao 3.3.2 Sejam aebdois in ei os e seja cum m´ul iplo comum de a
eb. En ˜ao mmc(a, b)|c. Em pa icula se aebs˜ao ela i amen e p imo, i.e.
mdc(a, b) = 1 en ˜ao ab |c.
48 CAP´
ITULO 3. ARITM´
ETICA MODULO N
Cap´ı ulo 4
Pe mu a¸c˜oes
4.1 O g upo sim´e ico
Sejam XeYconjun os n˜ao azios.
De ini¸c˜ao 4.1.1 Uma un¸c˜ao :X→Ydiz-se
•injec i a se x16=x2implica (x1)6= (x2)pa a odo x1, x2∈X;
•sob ejec i a se, pa a odo y∈Yexis e um x∈X al que (x) = y;
•bijec i a se ´e injec i a e sob ejec i a.
A un¸c˜ao idX:X→Xcom idX(x) = xpa a odo x∈X´e uma un¸c˜ao
bijec i a e diz-se a iden idade em X.
Obse a¸c˜ao 4.1.2 Uma un¸c˜ao :X→Y´e bijec i a se e s´o se exis e uma
un¸c˜ao in e sa g:Y→Xou seja uma un¸c˜ao g al que g( (x)) = xe (g(y)) = y
pa a odo x∈Xey∈Y. No a¸c˜ao: −1:= g.
Se em um in e so en ˜ao pa a qualque y∈Yexis e um x∈X(x:= g(y))
al que (x) = y. Logo ´e sob ejec i a. Se x1ex2s˜ao elemen os de Xen ˜ao
(x1) = (x2)implica x1=g( (x1)) = g( (x2)) = x2. Po an o ´e injec i a e
logo bijec i a.
Recip ocamen e, se ´e bijec i a en ˜ao a co espondˆencia g:Y→Xda o ma
g(y) := xse e s´o se (x) = y´e uma un¸c˜ao. Uma ez que pa a odo o yexis e
um x∈X al que (x) = y(pois ´e sob ejec i a) e exis e um s´o x∈Xcom es a
p op iedade (pois ´e injec i a). Po de ini¸c˜ao g´e o in e so de .
Seja :X→Yuma un¸c˜ao bijec i a. Tem-se ◦ −1=idYe −1◦ =idX.
49
50 CAP´
ITULO 4. PERMUTAC¸ ˜
OES
De ini¸c˜ao 4.1.3 Uma un¸c˜ao :X→Ybijec i a diz-se amb´em bijec¸c˜ao. Se
exis e uma bijec¸c˜ao en e dois conjun os XeYesc e emos X≃Y. Se X=Y
uma bijec¸c˜ao :X→Xdiz-se pe mu a¸c˜ao. Deno e-se po SXo conjun o de
odas as pe mu a¸c˜oes de X, is o ´e
SX:= { :X→X| ´e bijec i a }.
SXdiz-se o g upo sim´e ico de X.
Obse a¸c˜ao 4.1.4 A composi¸c˜ao de duas pe mu a¸c˜oes ´e uma pe mu a¸c˜ao. Pois,
se , g ∈SXen ˜ao
◦g:X→Xcom ◦g(x) := (g(x))
´e uma un¸c˜ao. ◦g´e bijec i a po que em um in e so que ´e a un¸c˜ao g−1◦ −1.
Tem-se
( ◦g)((g−1◦ −1)(x)) = (g(g−1( −1(x)))) = ( −1(x)) = xe
(g−1◦ −1)(( ◦g)(x)) = g−1( −1( (g(x)))) = g(g−1(x)) = x∀x∈X.
Suponha que exis e uma bijec¸c˜ao ϕ:X→Yen e dois conjun os XeY.
En ˜ao exis e amb´em uma bijec¸c˜ao en e os g upos sim´e icos SXeSY.
Obse a¸c˜ao 4.1.5 Sejam XeYdois conjun os n˜ao azios. Suponha que exis e
uma bijec¸c˜ao ϕ:X→Y. En ˜ao a un¸c˜ao
ϕ:SX→SY 7→ ϕ◦ ◦ϕ−1
´e uma bijec¸c˜ao en e SXeSY. (No e-se ϕ( )(y) := ϕ( (ϕ−1(y))))
Demons a¸c˜ao: A un¸c˜ao ϕ em um in e so. Temos:
Y−→ X−→ X−→ Y
y7→ ϕ−1(y)7→ (ϕ−1(y)) 7→ ϕ( (ϕ−1(y))) = ϕ( )(y)
Seja ψ:SY→SXde inido po ψ(g):=ϕ−1◦g◦ϕpa a qualque g∈SY. Logo:
ψϕ( ) = ψϕ◦ ◦ϕ−1=ϕ−1◦ϕ◦ ◦ϕ−1◦ϕ=
e
ϕψ(g) = ϕϕ−1◦g◦ϕ=ϕ◦ϕ−1◦g◦ϕ◦ϕ−1=g.
Po an o ψ=: ϕ−1´e o in e so de ϕ.
Que emos es uda o g upo sim´e ico de um conjun o ini o X.
4.1. O GRUPO SIM´
ETRICO 51
Obse a¸c˜ao 4.1.6 Seja Xum conjun o com nelemen os (n≥1). En ˜ao exis e
uma bijec¸c˜ao en e Xe o subconjun o {1,2, . . . , n}de N. Em pa icula SX≃
S{1,2,...,n}.
Demons a¸c˜ao: Exe c´ıcio.
Es amos pa icula men e in e essados no caso de Xse um conjun o ini o de
o dem n(n≥1). Pela obse a¸c˜ao an e io podemos supo que X:= {1,2, . . . , n}.
Deno amos SXpo Sn.
Sn:= { :{1,2, . . . , n} −→ {1,2, . . . , n} | ´e bijec i a }.
Sndiz-se o g upo sim´e ico de g au n. A composi¸c˜ao ◦´e uma ope a¸c˜ao
bin´a ia em Sne a iden idade id em {1,2, . . . , n}´e o elemen o neu o, i.e. ◦id =
=id ◦ pa a odo ∈Sn.
Seja ∈SX, deno a-se
0:= id
k:= ◦ ◦···◦
| {z }
k ezes
pa a k≥1
Deno a-se ainda −k:= ( −1)kpa a k≥1.
Obse a¸c˜ao 4.1.7 Seja ∈SX. Pa a odos m, n ∈Z:
m◦ n= m+ne( m)n= m·n.
Sendo ∈Sn´e usual ep esen a a a ´es de uma ma iz 2 ×n, da seguin e
manei a:
=1 2 ··· n
(1) (2) ··· (n)
Tem-se na p imei a linha os elemen os de {1,2, . . . , n}e abaixo de cada 1 ≤
i≤n em-se a sua imagem (i).
Exemplo 4.1.8 S´o exis e uma un¸c˜ao {1} → {1}, a iden idade. Logo S1={id}.
Podemos esc e e em ez de id :1
1.
Exis em qua o un¸c˜oes :{1,2}→{1,2}mas s´o dois bijec¸c˜oes: a iden idade
e a un¸c˜ao que oca 1e2, i.e. (1) = 2 e (2) = 1. Logo S2={id, }. Podemos
ep esen a na o ma: =1 2
2 1 .
52 CAP´
ITULO 4. PERMUTAC¸ ˜
OES
Exis em 27 un¸c˜oes :{1,2,3}→{1,2,3}mas exis em s´o seis bijec¸c˜oes:
id =123
123 1=1 2 3
1 3 2 2=1 2 3
2 1 3
3=123
321 4=1 2 3
3 1 2 5=1 2 3
2 3 1
Logo S3={id, 1, 2, 3, 4, 5}. A composi¸c˜ao de dois pe mu a¸c˜oes em Sn´e
amb´em uma pe mu a¸c˜ao. Po exemplo a composi¸c˜ao de 3e 5: Tem-se
3◦ 5(1) = 3( 5(1)) = 3(2) = 2
3◦ 5(2) = 3( 5(2)) = 3(3) = 1
3◦ 5(3) = 3( 5(3)) = 3(1) = 3
Logo 3◦ 5=123
3211 2 3
2 3 1 =123
213= 2. Pa a a composi¸c˜ao
5◦ 3 em-se:
5◦ 3(1) = 5( 3(1)) = 3(3) = 1
5◦ 3(2) = 5( 3(2)) = 3(2) = 3
5◦ 3(3) = 5( 3(3)) = 3(1) = 2
Logo 5◦ 3=123
231123
321=1 2 3
1 3 2 = 1. No e-se que
3◦ 5= 26= 1= 5◦ 3
Pa a calcula o in e so de uma pe mu a¸c˜ao emos oca as linhas. Po exem-
plo 5=123
231e
−1
5=231
123=1 2 3
3 1 2 = 4.
Teo ema 4.1.9 Seja n≥1. O g upo sim´e ico Snde g au n em n!elemen os.
Demons a¸c˜ao: Seja ∈Sn. Temos npossibilidades pa a a imagem (1), n−1
possibilidades pa a (2), n−2 possibilidades pa a (3), . . ., 2 possibilidades pa a
(n−1) e uma possibilidades pa a (n). Logo ´e uma das n(n−1)(n−2)·····2·1 =
n! bijec¸c˜oes poss´ı eis. Po an o |Sn|=n!.
Teo ema 4.1.10 Seja n≥1. Pa a oda a pe mu a¸c˜ao ∈Snexis e um k∈N
al que k=id.
4.1. O GRUPO SIM´
ETRICO 53
Demons a¸c˜ao: Conside amos o subconjun o P:= { k|k≥1} ⊆ Sn. Como Sn
´e um conjun o ini o (s´o em n! elemen os) o subconjun o P´e um conjun o ini o
amb´em. Po an o nem odas as po ˆencias ks˜ao dis in as. Po an o exis em
n´ume os n>m al que n= me
n= m⇔ n◦ −m= m◦ −m⇔ n−m=id.
Logo exis e um k≥1 (aqui k=n−m) al que k=id.
De ini¸c˜ao 4.1.11 A o dem de ∈Sn´e o meno in ei o posi i o k≥1 al que
k=id.
A o dem da iden idade ´e igual 1.
Exemplo 4.1.12 Seja n= 3 e := 1 2 3
1 3 2 ∈S3.
6=id
2=123
1321 2 3
1 3 2 =123
123=id.
Logo em o dem 2. Seja := 123
312∈S3.
6=id
2=123
3121 2 3
3 1 2 =123
2316=id
3=123
3121 2 3
2 3 1 =123
123=id
Logo em o dem 3.
Obse a¸c˜ao 4.1.13 Seja n≥1e ∈Sn. Seja ka o dem de .
1. Tem-se −1= k−1, pois k=id implica k−1= k◦ −1= −1.
2. Suponha que l=id pa a um in ei o l≥1. En ˜ao k|l, pois l=id implica
l≥kcomo ke o meno in ei o posi i o al que k=id. Pelo algo i mo da
di is˜ao exis em in ei os qe ais que
l=qk + e0≥ < k.
Tem-se
id = l= qk ◦ = kq◦ = (id)q◦ = .
Como k´e o meno in ei o posi i o com a p op iedade k=id e como < k
em-se = 0. Po an o l=qk ou seja k|l.
54 CAP´
ITULO 4. PERMUTAC¸ ˜
OES
4.2 Ciclos e T ansposi¸c˜oes
De ini¸c˜ao 4.2.1 Seja ∈Sn. De inimos os elemen os ixos
ix( ):={i∈ {1,2, . . . , n} | (i) = i}
eo supo e de
sup( ):={i∈ {1,2, . . . , n} | (i)6=i}
Ob iamen e emos ix ={1,2, . . . , n} sup .
No e-se que sup =∅se e s´o se =id.
Exemplo 4.2.2 Seja =1 2 3 4
2 3 1 4 en ˜ao sup( ) = {1,2,3}e ix( ) =
{4}. No e-se que −1=1 2 3 4
3 1 2 4 esup( −1) = sup( )e ix( −1) = ix( ).
Obse a¸c˜ao 4.2.3 Seja ∈Sn. Tem-se sup( −1) = sup( ). Tamb´em em-se
i∈sup( )se e s´o se (i)∈sup( )pa a odo 1≤i≤n.
Demons a¸c˜ao: Seja i∈ ix( ). En ˜ao (i) = i⇒ ( (i)) = (i). Logo (i)∈
ix( ). Se (i)∈ ix( ) en ˜ao ( (i)) = (i)⇒ −1( ( (i))) = −1( (i)) ⇔
(i) = i. Po an o i∈sup( )⇔i6∈ ix( )⇔ (i)6∈ ix( )⇔ (i)∈sup( ).
Seja i∈ ix( ), i.e i= (i) en ˜ao −1(i) = −1( (i)) = iimplica i∈ ix( −1).
Seja i∈ ix( −1) , i.e. −1(i) = i. En ˜ao i= ( −1(i)) = (i) implica i∈ ix( ).
Logo sup( ) = sup( −1).
De ini¸c˜ao 4.2.4 Seja m≥2. Uma pe mu a¸c˜ao ∈Sndiz-se m-ciclo se se pude
o dena o supo e de sup( ) = {a1, a2, . . . , am}com ai6=aj∀i6=j, de o ma que
(ai) = ai+1 (∀i∈ {1, . . . , m −1})e (am) = a1
Esc e emos = (a1a2···am)pa a um m-ciclo .
Um 2-ciclo diz-se uma ansposi¸c˜ao. iden idade um 1-ciclo.
No e-se que a no a¸c˜ao = (a1···am) ´e amb´ıgua. Pa a se p ecisa, ´e necess´a io
indica o g upo Snao qual pe ence.
Exemplo 4.2.5 Seja =1 2 3 4
3 1 2 4 ∈S4en ˜ao sup( ) = {1,2,3}. Pode-
mos o dena o supo e da o ma sup( ) = {1,3,2}ou seja sup( ) = {a1, a2, a3}
com a1= 1,a2= 3 ea3= 2, pois emos (a1) = a2, (a2) = a3e (a3) = a1.
Logo ´e um 3-ciclo
= (132).
4.2. CICLOS E TRANSPOSIC¸ ˜
OES 55
No e-se que −1=1 2 3 4
2 3 1 4 ´e amb´em um 3-ciclo. O supo e sup( −1) =
sup( ) = {1,3,2}pode se o denado da o ma sup( −1) = {1,2,3}. Temos
−1(1) = 2, −1(2) = 3, −1(3) = 1. Logo −1= (123).
Seja g=1 2 3 4
2 1 4 3 . O supo e sup(g) = {1,2,3,4}n˜ao pode se o -
denado da o ma sup(g) = {a1, a2, a3, a4} al que g(ai) = ai+1 pa a i= 1,2,3e
g(a4) = a1. Po exemplo come¸camos com a1= 1 em-se g(1) = 2 eg(2) = 1.
Po an o emos um 2-ciclo (12) ”den o” g. N˜ao ´e di ´ıcil de e que g= (12)(34).
Como ciclos s˜ao pe mu a¸c˜oes, a composi¸c˜ao de ciclos ´e de inido. Mas em ge al
o p odu o de dois ciclos n˜ao ´e um ciclo. Po exemplo
(12)(34) = 1 2 3 4
2 1 3 4 1 2 3 4
1 2 4 3 =1 2 3 4
2 1 4 3 =g.
O p odu o dos ciclos (23)(543) ´e igual
(23)(543) = 12345
1324512345
12534=12345
13524= (2354).
Obse a¸c˜ao 4.2.6 Seja = (a1···am)∈Snum m-ciclo. En ˜ao −1´e um m-
ciclo amb´em e em-se
−1= (amam−1···a2a1)
Demons a¸c˜ao: Tem-se (ai) = ai+1 pa a 1 ≤i < m e (am) = a1. Logo
−1(ai+1) = −1( (ai)) = aipa a 1 ≤i<me −1(a)= −1( (am)) mos a que
o supo e sup( −1) = sup( ) = {am, am−1, . . . , a1}pode se o denado na o ma
que ida. Logo =(amam−1···a1) ´e um m-ciclo.
No e-se que os m-ciclos (a1a2···am) e (ama1···am−1) s˜ao iguais. Logo o
in e so (231) do ciclo (132) ´e igual o ciclo (123).
Teo ema 4.2.7 A o dem de um m-ciclo ´e m.
Demons a¸c˜ao: Seja = (a1···am) um m-ciclo. Seja 1 ≤k < m. Tem-se
k(a1) = k−1(a2) = k−2(a3) = ··· = 2(ak−1) = (ak) = ak+1.
En ˜ao k(a1) = ak+1 6=a1mos a que a o dem de ´e ≥m.
Temos
m(a1) = ( m−1(a1)) = (am−1+1) = (am) = a1.
Pa a qualque 1 < i ≤m em-se
m(ai) = m( i−1(a1)) = i−1( m(a1)) = i−1(a1) = ai.
Po an o m´e a o dem de .
56 CAP´
ITULO 4. PERMUTAC¸ ˜
OES
Exemplo 4.2.8 Seja =123456
352641∈S6. Podemos o dena o su-
po e sup( ) = {1,2,3,4,5,6}={1,3,2,5,4,6} al que
(1) = 3, (3) = 2, (2) = 5, (5) = 4, (4) = 6 e (6) = 1.
Logo = (132546) ´e um 6-ciclo. Po an o a o dem de ´e 6.
De ini¸c˜ao 4.2.9 Dois pe mu a¸c˜oes egde Sndizem-se disjun as se sup( )∩
sup(g) = ∅.
Obse a¸c˜ao 4.2.10 Sejam , g ∈Snpe mu a¸c˜oes disjun as en ˜ao ◦g=g◦ .
Demons a¸c˜ao: Tem-se {1,2, . . . , n}= sup( )∪sup(g)∪( ix( )∩ ix(g)) como
conjun os disjun os. Pa a odo i∈ ix( )∩ ix(g) emos (g(i)) = (i) = i=g(i) =
g( (i)). Pa a odo i∈sup( ) emos i∈ ix(g) e logo (g(i)) = (i) = g( (i)) ( e
4.2.3). Analogamen e emos pa a odo i∈sup(g) amb´em (g(i)) = g(i) = g( (i)).
Po an o ◦g=g◦ .
Digamos amb´em que as pe mu a¸c˜oes egcomu am se ◦g=g◦ .
Teo ema 4.2.11 Seja egdois pe mu a¸c˜oes disjun as de Sn. A o dem da com-
posi¸c˜ao ◦g´e o m´ınimo m´ul iplo comum das o dens de e de g:
o d( ◦g) = mmc(o d( ),o d(g)).
Demons a¸c˜ao: Seja k= mmc(o d( ),o d(g)). Como egs˜ao disjun as emos
◦g=g◦ e
( ◦g)k= ( ◦g)◦···◦( ◦g)
| {z }
k− ezes
= k◦gk= o d( )q◦go d(g)p=id
onde q=k/o d( ) e p=k/o d(g). Logo m:= o d( ◦g)≤k.
Tem-se id = ( ◦g)m= m◦gmimplica m=g−me sup( m) = sup(g−m) =
sup(gm). Como ix(g)⊆ ix(gm) emos sup(g)⊇sup(gm). Logo
sup( m) = sup(gm)⊆sup( )∩sup(g) = ∅
implica sup( m) = ∅= sup(gm) ou seja m=id =gm. Po an o o d( )|me
o d(g)|mimplica k= mmc(o d( ),o d(g)) ≤m. Logo m=k.
Teo ema 4.2.12 Toda a pe mu a¸c˜ao de Sn´e um p odu o de ciclos disjun os.
Al´em disso, o p odu o ´e ´unico a menos da pe mu a¸c˜ao iden idade e da o dem dos
ac o es.
4.2. CICLOS E TRANSPOSIC¸ ˜
OES 57
Demons a¸c˜ao: Seja ∈Sn. De inimos uma ela¸c˜ao de equi alˆencia no conjun o
{1,2, . . . , n}po i∼jse e s´o se j= k(i) pa a algum k≥0. Seja [i]∼:= {j∈
{1,2, . . . , n} | i∼j}a classe de i. Tem-se
[i]∼={i} ⇔ i∈ ix( ).
Como o conjun o {1,2, . . . , n}´e ini o emos s´o um n´ume o ini o de classes dis-
in as. Sejam [a1]∼,[a2]∼, . . . , [ak]∼as classes com mais do que 1 elemen o. En ˜ao
{1,2, . . . , n}= ix( )∪[a1]∼∪[a2]∼∪···∪[ak]∼.
Pa a cada 1 ≤i≤kseja mi≥1 o meno in ei o posi i o al que mi+1(ai) = ai.
Tem-se
[ai]∼={ai, (ai), 2(ai), . . . , mi(ai)}
Seja gi:= (ai (ai) 2(ai)··· mi(ai)) o mi-ciclo. En ˜ao emos
=g1◦g2◦···◦gk.
Pa a odo x∈ ix( ) em-se gi(x) = x, ∀1≤i≤k. Po an o
g1◦g2◦···◦gk(x) = x= (x).
Seja x∈[ai]∼en ˜ao x= (ai) pa a 0 ≤ ≤mi. Po an o
gi(x) = gi( (ai)) = +1(ai) = ( (ai)) = (x).
Como x, (x)6∈ [aj]∼pa a j6=i. Tem-se gj(x) = xegj( (x)) = (x) pa a j6=i.
Logo
g1◦g2◦···◦gk(x) = ··· =g1◦g2◦···◦gi−1◦gi(x) = g1◦g2◦···◦gi−1( (x)) = ··· = (x).
Po an o pa a odo x∈ {1,2, . . . n}, (x) = g1◦···◦gk(x).
Suponhamos =g1···gk=h1···hl´e p odu o de ciclos disjun os giehj. Seja
x∈sup( ) en ˜ao exis em i, j ais que x∈sup(gi) e x∈sup(hj). Sem pe da da
gene alidade podemos supo i=j= 1. Tem-se g
1(x) = (x) = h
1(x) pa a odo
∈N. Po an o exis e um ≥1 al que g
1(x) = x=h
1(x). Tem-se
g1= (xg1(x)g2
1(x)···g
1(x)) = h1.
Logo g1=h1ou seja g−1
1 =h−1
1 =: ˜
. Repe indo o p ocesso conclui-se que
k=le, a menos da o dem dos ac o es i=gi.
Exemplo 4.2.13 Seja =123456
312465. En ˜ao sup( ) = {1,2,3,5,6}.
Escolhemos um n´ume o i∈sup( ); po exemplo i= 1. Tem-se 1, (1) = 3, 2(1) =
(3) = 2, 3(1) = 2(3) = (2) = 1. Logo emos um 3-ciclo
g1:= (132)
64 CAP´
ITULO 5. MON ´
OIDES E GRUPOS
3. (Zn,+,[0]n)e(Zn {[0]n},·,[1]n)s˜ao mon´oides pa a n≥1.
4. (M2(A),+,0 0
0 0 )´e um mon´oide onde M2(A) = {a b
c d |a, b, c, d ∈
A}pa a A=N,Z,Q,R,C.
5. O conjun o dos polin´omios (A[X],+,0) com coe icien es em A=N,Z,Q,R,C
´e um mon´oide.
5.2 Mon´oides
Obse a¸c˜ao 5.2.1 Sejam (M, , e)e(N, ~, )mon´oides. No p odu o ca esiano
M×Npodemos de ini uma ope a¸c˜ao bin´a ia : (M×N)×(M×N)→(M×N)
po
(m, n)(m0, n0) := (mm0, n ~n0)
pa a odos os elemen os (m, n),(m0, n0)∈M×N. En ˜ao (M×N, ,(e, )) ´e um
mon´oide e diz-se o p odu o di ec o de MeN.
Demons a¸c˜ao: Po de ini¸c˜ao ´e uma un¸c˜ao. En ˜ao (M×N, ) ´e um g up´oide.
O elemen o (e, ) ´e o elemen o neu o de (M×N, ), pois pa a odo (m, n)∈M×N
em-se
(m, n)(e, ) = (me, n ~ ) = (m, n) = (em, ~n) = (e, )(m, n).
A ope a¸c˜ao ´e associa i a, po que pa a (m, n),(m0, n0),(m00, n00)∈M×N em-se
(m, n)((m0, n0)(m00, n00)) = (m(m0m00), n ~(n0~n00))
= ((mm0)m00),(n~n0)~n00)
= ((m, n)(m0, n0)) (m00, n00)
Po an o (M×N, ,(e, )) ´e um mon´oide.
De ini¸c˜ao 5.2.2 Seja (M, , e)um mon´oide. Um subconjun o N⊆Mdiz-se
submon´oide de Mse
(i) e∈N
(ii) N´e echado pa a , i.e. ∀x, y ∈N⇒xy∈N.
Obse a¸c˜ao 5.2.3 Sejam (M, , e)um mon´oide e Cum conjun o de submon´oides
de M. En ˜ao
N∈C
N
´e um submon´oide de M.
5.2. MON ´
OIDES 65
Demons a¸c˜ao: Como e∈Npa a odo N∈ C,e∈TN∈C N. Sejam x, y ∈
TN∈C Nen ˜ao x, y ∈Npa a odo N∈ C. Logo
xy∈N∀N∈ C ⇒ xy∈
N∈C
N.
Seja Aum conjun o n˜ao azio que designamos po al abe o (os elemen os de A
s˜ao as le as). Seja A+o conjun o das pala as no al abe o A, i.e. as sequˆencias
a1a2···ancom ai∈A. Seja A∗=A+∪{∅}, onde ∅´e a pala a azia. De ine-se a
ope a¸c˜ao ·de conca ena¸c˜ao da seguin e manei a:
(a1···an)·(b1···bm) = a1···anb1···bm
∅·∅=∅
(a1···an)·∅ =a1···an=∅·(a1···an)
pa a ai, bj∈A. En ˜ao (A+,·) ´e um semig upo e (A∗,·,∅) ´e um mon´oide, que se
diz o mon´oide li e em A.
Suponha A={x}en ˜ao h:N→A∗com h(0) := ∅eh(k) := xx ···x
| {z }
k− ezes
´e uma
un¸c˜ao bijec i a. Temos amb´em h(k+l) = h(k)·h(l).
De ini¸c˜ao 5.2.4 Sejam (M, , e)e(N, ~, )dois mon´oides. Uma un¸c˜ao h:
M→Ndiz-se homomo ismo de mon´oides se
(i) h(e) =
(ii) h(mm0) = h(m)~h(m0)pa a odo m, n ∈M.
Se h´e uma un¸c˜ao bijec i a hdiz-se um isomo ismo de mon´oides. Se exis e um
isomo ismo en e dois mon´oides MeNdizemos que MeNs˜ao isomo os e
esc e emos M≃N.
Vimos que os mon´oides (N,+,0) e ({x}∗,·,∅) s˜ao isomo os.
Obse a¸c˜ao 5.2.5 Seja :M→Num isomo ismo en e mon´oides. En ˜ao
|M|=|N|e −1:N→M´e amb´em um isomo ismo de mon´oides.
De ini¸c˜ao 5.2.6 Sejam (M, , e)um mon´oide e Dum subconjun o de M. O
submon´oide ge ado po D´e
hDi:= {x1x2···xn|n≥1, xi∈D}∪{e}.
Obse a¸c˜ao 5.2.7 Sejam (M, , e)um mon´oide e Dum subconjun o de M.
1. hDi´e o meno submon´oide de Mque con ´em D.
2. hDi=TN∈C Nonde C´e o conjun o dos submon´oides Nde Mque con ˆem
D.
66 CAP´
ITULO 5. MON ´
OIDES E GRUPOS
5.3 In e ibilidade em mon´oides
De ini¸c˜ao 5.3.1 Sejam (M, , e)ex, y ∈M. Diz-se que y´e o in e so de xse
xy=e=yx.
Se x em um in e so dizemos que x´e in e ´ı el. Nes e caso deno a-se o in e so
de xpo x−1.
Obse a¸c˜ao 5.3.2 Um elemen o de um mon´oide em apenas um in e so.
Demons a¸c˜ao: Seja xum elemen o de um mon´oide (M, , e) e suponhamos que
yezs˜ao in e sos de x. En ˜ao
y=ye=y(xz) = (yx)z=ez=z.
Seja U(M):={x∈M|x´e in e ´ı el }.
Obse a¸c˜ao 5.3.3 Sejam (M, , e)ex, y ∈M.
1. e´e in e ´ı el, i.e. e∈U(M).
2. se xeys˜ao in e ´ı eis en ˜ao xy´e in e ´ı el, i.e xy∈U(M). O in e so
de xy´e (xy)−1=y−1x−1.
3. U(M)´e um submon´oide de M.
Demons a¸c˜ao: 1) Como ee=e,e´e in e ´ı el. 2) Como
(xy)(y−1x−1) = x(yy−1)x−1=xex−1=xx−1=e
e
(y−1x−1)(xy) = y−1(x−1x)y=y−1ey=y−1y=e
Tem-se (xy)−1=y−1x−1.
Teo ema 5.3.4 Sejam (M, , e)um mon´oide e x∈Mum elemen o in e ´ı el.
En ˜ao pa a qualque a, b ∈M, se ax=bxou xa=xben ˜ao a=b.
Demons a¸c˜ao: Seja x−1o in e so de xen ˜ao
ax=bx⇒(ax)x−1= (bx)x−1
⇒a(xx−1) = b(xx−1)
⇒ae=be
⇒a=b.
Analogamen e mos a-se que xa=xb⇒a=b.
5.4. GRUPOS 67
5.4 G upos
De ini¸c˜ao 5.4.1 Um g upo ´e um mon´oide (G, ·, e) al que odo o elemen o de G
´e in e ´ı el.
En ˜ao (G, ·, e) ´e um g upo se
•G´e um conjun o
• · :G×G−→ G´e uma ope a¸c˜ao bin´a ia
•e∈G´e o elemen o neu o, i.e. a·e=a=e·a∀a∈G
• odo o elemen o de G em um in e so (em G), i.e. ∀g∈G:∃h∈G:h·g=
e=g·h.
Exemplo 5.4.2 1. (Z,+,0) ´e um g upo.
2. (Z,·,1) n˜ao ´e um g upo, mas ({1,−1},·,1) ´e um g upo.
3. (Q,+,0) e(Q {0},·,1) s˜ao g upos.
4. (Sn,◦, id)e(An,◦, id)s˜ao g upos.
5. (M2(Q),+,0 0
0 0 )e(GL2(Q),·,1 0
0 1 )s˜ao g upos onde
GL2(Q):={A∈M2(Q)|de A6= 0}.
Um g upo cuja ope a¸c˜ao bin´a ia ´e comu a i a diz-se amb´em g upo abeliano.
Obse a¸c˜ao 5.4.3 Sejam G1eG2g upos. O p odu o di ec o G1×G2´e um g upo.
Demons a¸c˜ao: Sejam (G1,, e1) e (G2,~, e2) g upos.
Sabemos que G1×G2´e um mon´oide com a ope a¸c˜ao bin´a ia:
(a1, a2)(b1, b2) := (a1b1, a2~b2)
e com o elemen o neu o (e1, e2). Como G1eG2s˜ao g upos odo o elemen o
a1∈G1ea2∈G2 em um in e so. Logo o in e so do elemen o (a1, a2)∈G1×G2
´e o elemen o (a−1
1, a−1
2), pois
(a1, a2)(a−1
1, a−1
2) = (a1a−1
1, a2~a−1
2) = (e1, e2).
De ini¸c˜ao 5.4.4 Seja Hum subconjun o de um g upo G.Hdiz-se um subg upo
de Gse H´e um submon´oide de G al pa a odo h∈H amb´em o in e so h−1
pe ence H.
68 CAP´
ITULO 5. MON ´
OIDES E GRUPOS
En ˜ao um subconjun o Hde um g upo G´e um subg upo de Gse
•e∈H
• ∀h∈H:h−1∈H
• ∀h, g ∈H:hg ∈H.
Exemplo 5.4.5 1. An´e um subg upo de Sn
2. (Z,+,0) ´e um subg upo de (Q,+,0).
3. (Z {0},·,1) n˜ao ´e um subg upo de (Q {0},·,1).
4. SL2(Q)´e um subg upo de GL2(Q).
5. (2Z4,+,[0]4´e um subg upo de (Z4,+,[0]4)onde
2Z4:= {[2a]4|a∈Z}={[0]4,[2]4}.
Obse a¸c˜ao 5.4.6 Seja Cum conjun o de subg upos de um g upo G. En ˜ao
TH∈C H´e um subg upo de G.
Demons a¸c˜ao: Seja K:= TH∈C H. J´a sabemos que K´e um submon´oide de
G. Seja k∈Ken ˜ao k∈Hpa a odo H∈ C. Como H´e um subg upo emos
k−1∈Hpa a odo H∈ C. Logo k−1∈K.
De ini¸c˜ao 5.4.7 Seja (G, , e)um g upo e D⊆Gum subconjun o. O subg upo
ge ado po Dem G´e
hDi:= {x1x2···xn|n≥0exi∈Dou x−1
i∈D}.
Po con en¸c˜ao o p odu o com 0 ac o es ´e igual a e(= o elemen o neu o de
G).
No e-se que hDi´e igual ao submon´oide ge ado po D∪D−1onde D−1:= {d−1|
d∈D}.
Obse a¸c˜ao 5.4.8 Seja Gum g upo e D⊆G.
1. hDi´e o meno subg upo de Gque con ´em D.
2. hDi=TH∈C Honde C´e o conjun o dos subg upos Hde Gque con ˆem D.
De ini¸c˜ao 5.4.9 Suponha G=hDipa a um subconjun o D⊆G. En ˜ao dizemos
que G´e ge ado po DeD´e um conjun o dos ge ado es de G. Se exis e um
conjun o ini o D={d1, d2, . . . , dm} al que G=hDien ˜ao Gdiz-se ini amen e
ge ado. Se exis e um elemen o d∈G al que G=h{d}i en ˜ao Gdiz-se c´ıclico.
5.4. GRUPOS 69
Usamos a seguin e no a¸c˜ao. Seja xum elemen o de um g upo (G, , e) e seja
k∈Z:
xk:= x···x
| {z }
k− ezes
pa a k > 0,
xk:= epa a k= 0,
xk:= x−1···x−1
| {z }
|k|− ezes
pa a k < 0.
No e-se que se G=Ze 0 6=x∈Zen ˜ao no g upo (Z,+,0) emos
xk=x+···+x
| {z }
k− ezes
=kx
pa a k > 0 e
xk= (−x) + ···+ (−x)
| {z }
|k|− ezes
= (−k)x
pa a k < 0. No g upo (Q {0},·,1) emos
xk=x·····x
| {z }
k− ezes
=xk
pa a k > 0 e
xk=1
x····· 1
x
| {z }
|k|− ezes
=1
xk
pa a k < 0.
Obse a¸c˜ao 5.4.10 1. Todo o g upo G´e ge ado pelos seus elemen os, i.e.
G=hGi. Logo se o conjun o G´e ini o, G´e ini amen e ge ado.
2. O g upo (Z,+,0) ´e c´ıclico, pois Z=h{1}i.
3. Seja (G, , e)um g upo abeliano e D⊆G. En ˜ao
hDi={xk1
1xk2
2···xkn
n|n≥0, ki∈Z, xi∈Dexi6=xj∀i6=j}.
4. O g upo (Q,+,0) n˜ao ´e ini amen e ge ado.
Demons a¸c˜ao: (1),(2) exe c´ıcio; (3) Po de ini¸c˜ao qualque elemen o x∈ hDi
´e igual x=x1x2··· xmpa a xi∈Dou x−1
i∈D. Como a ope a¸c˜ao
´e comu a i o podemos eo dena os ac o es e ob emos x=yk1
1···ykn
npa a
yi∈ {x1, . . . , xm}eyi6=yjeki∈Z. Po an o odo o elemen o de hDipode se
desc i o des a o ma.
(4) Seja D:= {a1
b1, . . . , am
bm} ⊂ Q. Po (3) odo o elemen o x∈ hDipode se esc i o
como
x=k1
a1
b1
+···km
am
bm
70 CAP´
ITULO 5. MON ´
OIDES E GRUPOS
onde ki∈Z. Calculando es a soma ob emos um elemen o de Qda o ma
x=c
b1b2···bm
pa a algum c∈Z( al ez seja poss´ı el simpli ica es e e mo, mas isso se ´a ig-
no ado aqui). Seja pum p imo al que p-bipa a odo 1 ≤i≤m. En ˜ao
1
p6∈ hDi, caso con ´a io suponhamos que 1
p∈ hDi. En ˜ao exis i a um c∈Z al
que 1
p=c
b1b2···bmou seja
b1b2···bm=cp.
Logo p|b1b2···bm. Assim, como p´e p imo, p|bipa a algum 1 ≤i≤m- absu do.
Po an o 1
p6∈ hDieQ6=hDipa a qualque subconjun o ini o Dde Q. Logo Q
n˜ao ´e ini amen e ge ado.
De ini¸c˜ao 5.4.11 Sejam (G1,, e1)e(G2,~, e2)g upos. Uma un¸c˜ao :G1−→
G2diz-se um homomo ismo de g upos se ´e um homomo ismo de mon´oides al
que (x−1) = (x)−1pa a odo x∈G1.
En ˜ao :G1−→ G2´e um homomo ismo de g upos se
• (e1) = e2;
• ∀x∈G1: (x−1) = (x)−1;
• ∀x, y ∈G1: (xy) = (x)~ (y).
Obse a¸c˜ao 5.4.12 Seja :G1→G2uma un¸c˜ao. En ˜ao ´e um homomo ismo
de g upos se e s´o se (xy) = (x)~ (y).
Demons a¸c˜ao: ⇒po de ini¸c˜ao.
⇐Temos
(e1) = (e1)~e2
= (e1)~( (e1)~ (e1)−1)
= (e1e1)~ (e1)−1
= (e1)~ (e1)−1
=e2
Pa a odo x∈G1 emos
(x)−1= (x)−1~e2
= (x)−1~ (e1)
= (x)−1~ (xx−1)
= (x)−1~ (x)~ (x−1) = (x−1).
5.4. GRUPOS 71
Seja :G1−→ G2um homomo ismo de g upos. O subconjun o de G1
Ke ( ):={x∈G1| (x) = e2}
diz-se o n´ucleo de . Pa a a imagem de esc e emos (G1).
Teo ema 5.4.13 Seja :G1−→ G2um homomo ismos de g upos.
1. A imagem (G1)´e um subg upo de G2.
2. O n´ucleo Ke ( )´e um subg upo de G1.
3. O homomo ismo ´e injec i o se e s´o se Ke ( ) = {e1}.
4. se ´e um isomo ismo en ˜ao −1:G2→G1´e um isomo ismo amb´em.
Demons a¸c˜ao: (3) Suponhamos que Ke ( ) = {e1}. Sejam x, y ∈G1 ais que
(x) = (y). En ˜ao e2= (y)~ (x)−1= (yx−1). Logo yx−1∈Ke ( ) =
{e1}. Consequen emen e yx−1=e1ou seja y=x. Po an o ´e injec i o.
Se ´e injec i o e (x) = e2logo x=e1.
Teo ema 5.4.14 (Teo ema de Cayley) Qualque g upo (G, , e)´e isomo o a
um subg upo de um g upo sim´e ico SX.
Demons a¸c˜ao: Seja X=GeSXo g upo sim´e ico do conjun o X. Pa a
qualque g∈Gseja Lg:X→Xa un¸c˜ao: Lg(x) = gx. Tem-se
Lg◦Lg−1(x) = gg−1x=x=id(x)
pa a qualque x∈X, po an o Lg´e bijec i a e Lg∈SX. No a que
Lgh(x) = ghx=Lg(Lh(x)) = (Lg◦Lh)(x)
pa a qualque x∈X. A aplica¸c˜ao L:G→SXcom (g) = Lg´e um homomo ismo
de g upos, po que
(gh) = Lgh=Lg◦Lh= (g)◦ (h).
Se (g) = Lg=id, en ˜ao
e=gg−1=Lg(g−1) = id(g−1) = g−1.
. Po an o Ke ( ) = {e}e ´e injec i o e G´e isomo o ao imagem de , que ´e um
subg upo de SX.
72 CAP´
ITULO 5. MON ´
OIDES E GRUPOS
5.5 G upos c´ıclicos
Teo ema 5.5.1 Seja (G, , e)um g upo c´ıclico, i.e. G=hxipa a algum x∈G.
En ˜ao ou G´e isomo o ao g upo (Z,+,0) ou G´e isomo o ao g upo (Zn,+,[0]n)
pa a algum n≥1.
Demons a¸c˜ao: Suponhamos que n˜ao exis e nenhum in ei o k6= 0 al que xk=e
onde e´e o elemen o neu o de G. En ˜ao a un¸c˜ao :Z→G al que (k) := xk´e
bijec i a, po que se (k) = (l) pa a k≥len ˜ao
xk=xl⇒xk−l=xl−l=e⇒k−l= 0 ⇒k=l.
A un¸c˜ao ´e um homomo ismo de g upos, pois (k+l) = xk+l=xkxl=
(k) (l) pa a k, l ∈Z. En ˜ao ´e um isomo ismo de g upos.
Suponhamos que exis e um in ei o k6= 0 al que xk=e. Sem pe da de
gene alidade podemos supo que exis e um in ei o posi i o, po que se k < 0 e
xk=een ˜ao x−k=e−1=ee−k > 0. Seja no meno in ei o posi i o al que
xn=e. Temos que
:Zn→Gcom ([k]n) := xk∀[k]n∈Zn
´e uma un¸c˜ao. Temos de e i ica se es ´a bem-de inida. En ˜ao sejam k≤ldois
in ei os ais que [k]n= [l]n. Logo n|l−k⇒ ∃q∈Z:l=k+qn. Po an o
([l]n) = xl=xk(xn)q=xke= ([k]n)
mos e que es ´a bem-de inida. Temos que ´e um homomo ismo de g upos, pois
([k]n+ [l]n) = ([k+l]n) = xk+l=xkxl= ([k]n) ([l]n)
pa a odo [k]n,[l]n∈Zn. Suponha que exis e um k∈Z al que ([k]n) = xk=e.
Pelo Algo i mo da di is˜ao exis em q∈Ze ∈ {0,1, . . . , n−1} ais que k=nq + .
Po an o
e=xk= (xn)qx =ex =x .
Como n´e o meno in ei o posi i o al que xn=ee 0 ≤ < n emos = 0. Logo
n|k⇒[k]n= [0]n. Po an o ´e injec i o. Como ´e amb´em sob ejec i o, ´e
bijec i a e um isomo ismo de g upos.
De ini¸c˜ao 5.5.2 Seja Gum g upo. De ine-se o dem de g∈Ge deno a-se po
o d(g), como sendo a o dem do subg upo hgige ado po g;o d(g) :=| hgi |.
Obse a¸c˜ao 5.5.3 Seja g∈G. Se o d(g)´e ini o en ˜ao o d(g)´e o meno in ei o
posi i o n al que gn=e. Al´em disso gk=e⇔o d(g)|kpa a k∈Z.
5.5. GRUPOS C´
ICLICOS 73
Demons a¸c˜ao: Suponhamos que o d(g) =| hgi |=n < ∞. En ˜ao :Zn→ hgi
com ([k]n) = gk´e um isomo ismo de g upos. Suponhamos que gk=epa a
algum k∈Z. En ˜ao ([k]n) = gk=e=g0= ([0]n) o que implica que [k]n= [0]n,
pois ´e injec i o. Logo n|k. Se k > 0 en ˜ao k≥n. Po an o n= o d(g)
´e o meno in ei o posi i o al que gn=e. Tamb´em emos que se gk=een ˜ao
n= o d(g)|k. A a i ma¸c˜ao con ´a ia ´e ob ia.
Lema 5.5.4 Todo o subg upo de um g upo c´ıclico ´e c´ıclico.
Demons a¸c˜ao: Seja (G, , e) um g upo c´ıclico. En ˜ao exis e um g∈G al que
G=hgi. Seja Hum subg upo de G. Se H={e}en ˜ao H´e c´ıclico, pois H=hei.
Suponha que H6={e}e seja h∈H al que h6=e. Como odo o elemen o de G´e
da o ma gkpa a k∈Zexis e k∈Z al que h=gk. Sem pe da de gene alidade
podemos supo que exis e um in ei o posi i o k > 0 al que gk∈H, pois se k < 0
en ˜ao g−k=h−1∈He−k > 0. Sejam ko meno in ei o posi i o al que gk∈He
gl∈Hcom l∈Zum elemen o de Hqualque . Pelo algo i mo da di is˜ao exis em
in ei os q∈Ze ∈ {0,1, . . . , k −1} ais que l=qk + . Po an o
gl=gkq q ⇒g =gl−qk ∈H.
Como k´e o meno in ei o posi i o al que gk∈He como 0 ≤ < k emos = 0
ek|l. Logo odo o elemen o de H´e da o ma (gk)qpa a um q∈Z. En ˜ao
H⊆ hgki ⊆ Himplica que H=hgki´e c´ıclico.
Co ol´a io 5.5.5 Os subg upos de (Z,+,0) s˜ao da o ma nZpa a n≥0.
Demons a¸c˜ao: O subg upo ge ado po um in ei o n∈Z´e igual
hni={n+. . . +n
| {z }
k− ezes |k > 0}∪{0}∪{(−n) + . . . + (−n)
|{z }
|k|− ezes |k < 0}
={kn |k∈Z}
=nZ.
Ob iamen e nZ= (−n)Z, en ˜ao odo o subg upo em a o ma nZpa a algum
n≥0.
Obse a¸c˜ao 5.5.6 Seja G=hgium g upo c´ıclico al que o d(g) = n. As
seguin es p op iedades s˜ao sa is ei as pa a odo o elemen o gk∈Gcom k∈Z:
(i) o d(gk) = n
mdc(n,k).
(ii) hgki=hgmdc(n,k)i.
80 CAP´
ITULO 5. MON ´
OIDES E GRUPOS
Cap´ı ulo 6
An´eis e co pos
6.1 An´eis
De ini¸c˜ao 6.1.1 Um conjun o Acom duas ope a¸c˜oes bin´a ias +e·´e um anel
se
(i) (A, +,0) ´e um g upo abeliano.
(ii) (A, ·,1) ´e um mon´oide.
(iii) ∀a, b, c ∈A:
a·(b+c) = a·b+a·c
(b+c)·a=b·a+c·a
A ope a¸c˜ao + diz-se a adi¸c˜ao do anel, a ope a¸c˜ao ·diz-se a mul iplica¸c˜ao do
anel; o elemen o neu o 0 da adi¸c˜ao diz-se o ze o do anel; o elemen o neu o 1
da mul iplica¸c˜ao diz-se o elemen o um do anel. Dado a∈Ao in e so de aem
(A, +,0) diz-se o sim´e ico de ae ep esen a-se po −a.
Se a mul iplica¸c˜ao do anel o comu a i a, o anel diz-se anel comu a i o.
Em ge al ep esen amos apenas po Ao anel (A, +,·,0,1).
Um elemen o ado anel Adiz-se in e ´ı el se a o in e ´ı el no mon´oide
(A, ·,1), i.e. se exis i b∈A al que
ab = 1 = ba.
Se a o in e ´ı el o in e so de aem (A, ·,1) ´e ´unico e deno a-se po a−1.
Um anel A al que odo o elemen o an˜ao nulo, i.e. a6= 0, ´e in e ´ı el diz-se
um co po.
O anel A={0}diz-se anel i ial. N˜ao ´e di ´ıcil mos a que A´e o anel i ial
se e s´o se |A|= 1.
Exemplo 6.1.2 •Z,Q,R,Cs˜ao an´eis. Nn˜ao ´e um anel po que (N,+,0) n˜ao
´e um g upo.
81
82 CAP´
ITULO 6. AN´
EIS E CORPOS
•(Zn,+,·,[0]n,[1]n)´e um anel pa a n≥0.
•(M2(R),+,·,0 0
0 0 ,1 0
0 1 )munido da soma e p odu o de ma izes
´e um anel.
•(R[X],+,·,0,1) munido da soma e p odu o de polin´omios ´e um anel.
Obse a¸c˜ao 6.1.3 Seja Aum anel e a, b ∈A. Tem-se que
(i) a·0=0=0·a.
(ii) (−a)·b=−(a·b) = a·(−b)
(iii) (−a)·(−b) = a·b
(i ) A´e o anel i ial se e s´o se 0 = 1.
Demons a¸c˜ao: (i) Seja a∈Aen ˜ao a·0 = a·(0 + 0) = a·0 + a·0⇒0 = a·0.
(ii) (−a)·b+a·b= (−a+a)·b= 0 ·b= 0. Logo (−a)·b=−(a·b).
(iii) 0 = (−a)·(−b)+(−(a·b) = (−a)·(−b)+(−a)·b= (−a)·(−b+b) = (−a)·0 = 0.
Logo (−a)·(−b) = −(−(a·b)) = a·b.
(i ) Ob iamen e se A´e i ial en ˜ao 0 = 1. Seja 0 = 1. Pa a odo a∈A emos
a=a·1 = a·0 = 0. Logo A={0}.
Teo ema 6.1.4 Sejam (A, +,·,0,1) e(A0,+0,·0,00,10)an´eis. O p odu o ca e-
siano A×A0´e um anel com as ope a¸c˜oes (a, a0)+(b, b0) := (a+b, a0+0b0)e
(a, a0)·(b, b0) := (a·b, a0·0b0), ze o (0,00)e elemen o um (1,10). O anel (A×
A0,+,·,(0,00),(1,10)) diz-se o p odu o di ec o de AeA0.
Demons a¸c˜ao: J´a sabemos que (A×A0,+,(0,00) ´e um g upo e (A×A0,·,(1,10))
´e um mon´oide. Como
(a, a0)+(b, b0) = (a+b, a0+0b0) = (b+a, b0+0a0) = (b, b0)+(a, a0)
pa a qualque (a, a0),(b, b0)∈A×A0o g upo (A×A0,+,(0,00)) ´e abeliano. Sejam
(a, a0),(b, b0),(c, c0)∈A×A0en ˜ao
(a, a0)·[(b, b0)+(c, c0)] = (a, a0)·(b+c, b0+0c0)
= (a·(b+c), a0·0(b0+0c0))
= (a·b+a·c), a0·0b0+0a0·0c0)
= (a·b, a0·b0)+(a·c, a0·0c0)
= (a, a0)·(b, b0)+(a, a0)·(c, c0).
Analogamen e em-se [(b, b0)+(c, c0)]·(a, a0) = (b, b0)·(a, a0)+(c, c0)·(a, a0). Po an o
A×A0´e um anel.
6.1. AN´
EIS 83
De ini¸c˜ao 6.1.5 Seja (A, +,·,0,1) um anel e B⊆A. Diz-se que B´e um subanel
de A se B´e um subg upo de (A, +,0) eB´e um submon´oide de (A, ·,1).
Assim B´e um subanel de Ase e s´o se
(i) 0 ∈B;
(ii) ∀b∈B:−b∈B;
(iii) ∀a, b ∈B:a+b∈B;
(i ) 1 ∈B;
( ) ∀a, b ∈B:a·b∈B.
De ini¸c˜ao 6.1.6 Seja Aum co po e B⊆A. Diz-se que B´e um subco po de A
se B´e um subanel de Ae∀b∈B {0}:b−1∈B.
Exemplo 6.1.7 •Z´e um subanel de Qmas n˜ao ´e um subco po de Q.
•Q´e um subco po de ReC.
Teo ema 6.1.8 Seja Aum anel e seja Cum conjun o de suban´eis de A. En ˜ao
a in e sec¸c˜ao
B∈C
B
´e um subanel de A.
Seja Dum subconjun o n˜ao azio de um anel A. Seja
C:= {B⊆A|B´e um subanel de Ae con ´em odos os elemen os de D}.
En ˜ao o subanel ge ado po D´e
hDi:=
B∈C
B.
Um anel Adiz-se ini amen e ge ado se exis e um subconjun o n˜ao azio
ini o {d1, . . . , dn} ⊆ A al que A=h{d1, . . . , dn}i. Po exemplo Z=h{1}i e
Z×Z=h{(1,0),(0,1)}i.Os n´ume os acionais Qn˜ao s˜ao ini amen e ge ado como
anel.
84 CAP´
ITULO 6. AN´
EIS E CORPOS
6.2 Ideais e Teo ema Fundamen al do Homo-
mo ismo
De ini¸c˜ao 6.2.1 Sejam (A, +,·,0,1) e(A0,+0,·0,00,10)dois an´eis. Uma un¸c˜ao
:A→A0diz-se homomo ismo de an´eis se ´e um homomo ismo en e os
g upos (A, +,0) e(A0,+0,00)e ´e um homomo ismo en e os mon´oides (A, ·,1) e
(A0,·0,10).
En ˜ao uma un¸c˜ao ´e um homomo ismo de an´eis se
(i) (a+b) = (a) +0 (b) pa a a, b ∈A
(ii) (a·b) = (a)·0 (b) pa a a, b ∈A
(iii) (1) = 10.
Um homomo ismo bijec i o diz-se um isomo ismo.
Obse a¸c˜ao 6.2.2 Seja :A→A0um homomo ismo de an´eis.
(i) (0) = 00;
(ii) (−a) = − (a)pa a odo a∈A;
(iii) se a∈A´e in e ´ı el en ˜ao (a)´e in e ´ı el e (a)−1= (a−1);
(i ) ´e injec i o se e s´o se Ke ( ) = {0};
( ) se ´e um isomo ismo, en ˜ao −1:A0→A´e amb´em um isomo ismo de
an´eis.
( i) Im( )´e um subanel de A0.
Demons a¸c˜ao: Como ´e um homomo ismo de g upos (A, +,0) e (A0,+0,00)
em-se (i),(ii) e (i ).
(iii) Seja a∈Ain e ´ı el. En ˜ao
(a)·0 (a−1) = (a·a−1) = (1) = 10= (1) = (a−1·a) = (a−1)·0 (a).
Logo (a−1) = (a)−1.
De ini¸c˜ao 6.2.3 Um subconjun o Ide um anel (A, +,·,0,1) diz-se ideal se I´e
um subg upo de (A, +,0) al que ax ∈Iexa ∈Ipa a odo a∈Aex∈I.
6.2. IDEAIS E TEOREMA FUNDAMENTAL DO HOMOMORFISMO 85
Exemplo 6.2.4 (1){0}eAs˜ao ideais de um anel A.
(2) Os ideais de Zs˜ao da o ma nZpa a n∈N.
Todo o ideal Ide Z´e amb´em um subg upo do g upo (Z,+,0). Logo I=nZpo
5.5.5. Po ou o lado odo o subconjun o nZ´e um subg upo de (Z,+,0). Como
pa a odo a∈Zenx ∈nZ:
a(nx) = (nx)a=n(xa)∈nZ
nZ´e um ideal.
Lema 6.2.5 Seja :A→A0um homomo ismo de an´eis en ˜ao Ke ( )´e um
ideal de A.
Demons a¸c˜ao: J´a sabemos que Ke ( ) ´e um subg upo de (A, +,0). Sejam a∈A
ek∈Ke ( ) en ˜ao
(a·k) = (a)·0 (k) = (a)·000= 00= 00·0 (a) = (k)·0 (a) = (k·a).
Logo a·k, k ·a∈Ke ( ).
Teo ema 6.2.6 Seja Ium ideal de um anel (A, +,·,0,1) en ˜ao o g upo quocien e
(A/I, +, I)´e um anel com a mul iplica¸c˜ao
(a+I)·(b+I) := (a·b) + I∀a, b ∈A
e o elemen o um 1 + I. O anel (A/I, +,·, I, 1 + I)diz-se o anel quocien e de A
po I.
Demons a¸c˜ao: O g upo quocien e (A/I, +, I) de Apo I´e um g upo. Como
(A, +,0) ´e um g upo abeliano:
(a+I)+(b+I) = (a+b) + I= (b+a) + I= (b+I)+(a+I)∀a, b ∈A,
i.e. (A/I, +, I) ´e um g upo abeliano.
Vamos e que a mul iplica¸c˜ao es eja bem-de inida: Seja a+I=a0+Ieb+I=b0+I
ou seja a−a0∈Ieb−b∈I. En ˜ao exis em x, y ∈I ais que a=a0+xeb=b0+y.
Po an o
(a+I)·(b+I)=(a·b) + I
= ((a0+x)·(b0+y))+I
= (a0·b0+a0·y+x·(b0+y))+I
= (a0·b0) + I
= (a0+I)·(b0+I)
86 CAP´
ITULO 6. AN´
EIS E CORPOS
po que a0·y∈Iex·(b0+y)∈Icomo I´e um ideal e x, y ∈I. (No e-se que
(a+z) + I=a+Ise z∈I). Po an o ·es ´a bem-de inida.
(A/I, ·,1+I) ´e um mon´oide, pois pa a odos os elemen os a+I, b+I, c+I∈A/I
em-se
[(a+I)·(b+I)]·(c+I) = [(a·b) + I]·(c+I)
= ((a·b)·c) + I
= (a·(b·c))+I
= (a+I)·[(b·c) + I]
= (a+I)·[(b+I)·(c+I)],
i.e. ·´e associa i a.
(a+I)·(1 + I) = (a·1) + I=a+I= (1 ·a) + I= (1 + I)·(a+I),
i.e. 1 + I´e o elemen o neu o de (A/I, ·).
Tamb´em em-se
(a+I)·[(b+I)+(c+I)] = (a+I)·((b+c) + I)
= (a·(b+c))+I
= (a·b+a·c)) + I
= [(a·b) + I]+[(a·c) + I]
= [(a+I)·(b+I)]+[(a+I)·(c+I)]
e analogamen e
[(b+I)+(c+I)]·(a+I) = [(b+I)·(a+I)]+[(c+I)·(a+I)].
Logo (A/I, +,·, I, 1 + I) ´e um anel.
Teo ema 6.2.7 (Teo ema undamen al de homomo ismos) Sejam AeA0
an´eis, :A→A0um homomo ismo de an´eis e I:= Ke ( ). A un¸c˜ao
:A/I →A0com (a+I):= (a)
pa a odo a+I∈A/I ´e um homomo ismo de an´eis injec i o.
Demons a¸c˜ao: J´a sabemos pelo 5.6.9 que :A/I →A0´e um homomo ismo
de g upos (A/I, +, I) e (A0,+0,00) onde I= Ke ( ) e (a+I) = (a). Tamb´em
sabemos que ´e injec i o. Bas a mos a que ´e um homomo ismo de an´eis ou
seja que ´e um homomo ismo de mon´oides (A/I, ·,1 + I) e (A0,·0,10). Tem-se
pa a odo a+I, b +I∈A/I :
((a+I)·(b+I)) = ((a·b) + I)
= (a·b)
= (a)·0 (b)
= (a+I)·0 (b+I).
6.3. DOM´
INIOS DE INTEGRIDADE E CORPOS 87
Ve i ique-se amb´em
(1 + I) = (1) = 10.
Po an o ´e um homomo ismo de mon´oides (A/I, ·,1 + I)e(A0,·0,10) e como j´a
sabemos que ´e um homomo ismo de g upos (A/I, +, I)e(A0,+0,00) em-se que
´e um homomo ismo de an´eis.
Co ol´a io 6.2.8 Seja :A→A0um homomo ismo de an´eis. En ˜ao os an´eis
A/Ke ( )eIm( )s˜ao isomo os: A/Ke ( )≃Im( ).
6.3 Dom´ınios de In eg idade e Co pos
De ini¸c˜ao 6.3.1 Seja Aum anel comu a i o. Um elemen o a∈A {0}diz-se um
di iso de ze o se exis i b∈A {0} al que ab = 0.
Exemplo 6.3.2 Seja A=Z6. O elemen o a= [2]6∈A´e um di iso de ze o,
po que pa a b= [3]6 em-se
ab = [2]6[3]6= [6]6= [0]6.
Po de ini¸c˜ao: Um elemen o a∈A´e um di iso de ze o se a a i ma¸c˜ao ∃b∈A:
b6= 0 ∧ab = 0 o e dade. Negamos es a a i ma¸c˜ao ob emos que um elemen o a
n˜ao ´e um di iso de ze o se 6 ∃b∈A:b6= 0∧ab = 0 ou seja se ∀b∈A:b= 0∨ab 6= 0.
Obse a¸c˜ao 6.3.3 Seja Aum anel comu a i o e a∈A. Suponha que a´e in-
e ´ı el en ˜ao an˜ao ´e um di iso de ze o.
Demons a¸c˜ao: Suponha que a∈A´e in e ´ı el. Seja a−1o in e so de a. Se
ab = 0 pa a algum b∈Aen ˜ao
b=a−1ab =a−10 = 0.
Po an o an˜ao pode se um di iso de ze o.
De ini¸c˜ao 6.3.4 Um anel comu a i o Adiz-se dom´ınio de in eg idade se A
n˜ao em di iso es de ze o.
Obse a¸c˜ao 6.3.5 Seja Aum anel comu a i o. A´e um dom´ınio de in eg idade
se e s´o se xa =xb ⇒x= 0 ∨a=bpa a odo a, b, x ∈A.
Demons a¸c˜ao: Seja Aum dom´ınio de in eg idade. Suponha que xa =xb pa a
x, a, b ∈A. Logo x(a−b) = 0. Como A´e um dom´ınio de in eg idade, An˜ao em
di iso es de ze o. Logo ou xou a−b´e igual 0. Po an o x= 0 ∨a=b.
Suponha que xa =xb ⇒x= 0 ∨a=bpa a odo a, b, x ∈A. Se ab = 0 pa a
alguns elemen os a, b ∈Aen ˜ao ab =0=a0⇒a= 0 ∨b= 0. Po an o An˜ao
em di iso es de ze o.
88 CAP´
ITULO 6. AN´
EIS E CORPOS
Exemplo 6.3.6 Z,Q,R,Cs˜ao dom´ınios de in eg idades.
Teo ema 6.3.7 Todo o co po ´e um dom´ınio de in eg idade.
Demons a¸c˜ao: Como odo o elemen o de um co po ou ´e igual 0 ou ´e um elemen o
in e ´ı el a obse a¸c˜ao 6.3.3 mos e que um co po n˜ao em di iso es de ze o.
O anel Z´e um dom´ınio de in eg idade mas n˜ao ´e um co po.
Digamos que um anel A´e ini o se |A|´e um n´ume o ini o.
Teo ema 6.3.8 Todo o dom´ınio de in eg idade ini o ´e um co po.
Demons a¸c˜ao: Seja Aum dom´ınio de in eg idade ini o com nelemen os. Pa a
qualque x∈A {0}conside amos a un¸c˜ao Ex:A→Acom Ex(a) = xa. Se
Ex(a) = Ex(b) en ˜ao xa =xb ⇒a=bpo 6.3.5. Logo Ex´e injec i o. Como A
em nelemen os e Ex´e injec i o, a imagem da un¸c˜ao Ex:
Im(Ex) = {xa |a∈A} ⊆ A
em amb´em nelemen os. Logo Ex´e sob ejec i o, i.e. Im(()Ex) = A. Po an o
exis e um a∈A al que xa =Ex(a) = 1, i.e x´e in e ´ı el. Mos ´amos que odo o
elemen o x6= 0 ´e in e ´ı el; logo A´e um co po.
De ini¸c˜ao 6.3.9 Seja Aum anel comu a i o. Um ideal Ide Adiz-se p imo se
∀a, b ∈A:ab ∈I⇒a∈I∨b∈I.
Um ideal Ide Adiz-se maximal se pa a odo ideal Jde A:
I⊆J⊆A⇒I=J∨J=A.
Exemplo 6.3.10 Os ideais maximais de Zs˜ao da o ma pZonde p´e um n´ume o
p imo.
Pa a e is o seja Ium ideal maximal de Z. Como odo o subg upo de Z´e da
o ma nZcom n≥0exis e um n∈N al que I=nZ. Seja dum di iso posi i o
de n, i.e. 1≤d≤ned|n. En ˜ao
I=nZ⊆dZ⊆Z
po que odo o elemen o na ∈nZ´e amb´em um m´ul iplo de d, po an o na ∈dZ.
Como I´e maximal, I=dZou dZ=Z. No p imei o caso em-se d∈I=nZou
seja d=nx mas como n=dy pa a algum y∈Z em-se
d=dyx ⇒1 = yx ⇒y=x= 1 ⇒d=n.
No segundo caso em-se 1∈dZou seja 1 = dx pa a algum x∈Z. Logo d= 1.
Po an o os ´unicos di iso es posi i os de ns˜ao 1en, i.e. n´e um n´ume o p imo.
Suponha que I=pZcom pum n´ume o p imo. Seja Jum ideal de Z al que
pZ⊆J⊆Z. Se pZ6=Jen ˜ao exis e um n∈J pZ. Logo p-nou seja
mdc(p, n) = 1. Pelo Algo i mo de Euclides exis em x, y ∈Z ais que 1 = px +ny.
Como px ∈pZ⊆Jeny ∈J em-se 1∈J. Po an o J=Z.
6.3. DOM´
INIOS DE INTEGRIDADE E CORPOS 89
Exemplo 6.3.11 Os ideais p imos de Zs˜ao os ideais maximais de Ze o ideal
{0}.
Seja Ium ideal p imo de Z. Exis e um n∈N al que I=nZ. Se n= 0 en ˜ao
I={0}. Suponha que n6= 0. Seja dum di iso posi i o de n al que n=dx pa a
algum x∈Z. Como dx =n∈nZ=IeI´e p imo, d∈Iou x∈I. Se d∈Ien ˜ao
d=ny pa a algum y∈Z. Logo
n=dx =nyx ⇒1 = yx ⇒x= 1 ⇒n=d.
Se x∈Ien ˜ao x=ny pa a algum y∈Z. Logo
n=dx =dny ⇒1 = dy ⇒d= 1.
Po an o os ´unicos di iso es posi i os de ns˜ao 1en, i.e. n´e um n´ume o p imo.
O ideal {0}´e um ideal p imo, pois se a, b ∈Z:
ab ∈ {0} ⇒ ab = 0 ⇒a= 0 ∨b= 0 ⇒a∈ {0}∨b∈ {0}.
Seja pum n´ume o p imo e a, b ∈Z
ab ∈pZ⇒p|ab ⇒p|a∨p|b⇒a∈pZ∨b∈pZ.
Po an o pZ´e um ideal p imo de Z.
Lema 6.3.12 Sejam IeJideais de um anel A, en ˜ao I+J:= {x+y|x∈I, y ∈
J}´e um ideal de A.
Demons a¸c˜ao: Ve i icamos que I+J´e um subg upo de A: (i) 0 ∈I⊆I+J;
(ii) ∀x, x0∈Iey, y0∈J: (x+y)+(x0+y0) = (x+x0)+(y+y0)∈I+J; en ˜ao
I+Jes ´a echado pa a +.
(iii) ∀x+y∈I+J: (−x)+(−y)∈I+J.
Sejam a∈Aex+y∈I+Jcom x∈Iey∈J. En ˜ao
a·(x+y) = a·x+a·y∈I+Je (x+y)·a=x·a+y·a∈I+J
Lema 6.3.13 Sejam Aum anel e I⊆Jideais de A. O subconjun o J/I :=
{a+I|a∈J}´e um ideal do anel quocien e A/I.
Demons a¸c˜ao: Exe c´ıcio.
Teo ema 6.3.14 Seja Aum anel comu a i o e Ium ideal de A. Tem-se
(1) I´e um ideal p imo se e s´o se o anel quocien e A/I ´e um dom´ınio de in e-
g idade.