aula03_2010

Prévia do material em texto

A´lgebra A - Aula 03
Relac¸o˜es de equivaleˆncia, Zn,
divisibilidade e poteˆncias
Elaine Pimentel
Departamento de Matema´tica, UFMG, Brazil
2o Semestre - 2010
Relac¸o˜es de equivaleˆncia
Seja X um conjunto e ∼ uma relac¸a˜o entre elementos de X .
Dizemos que ∼ e´ uma relac¸a˜o de equivaleˆncia se, para todos
x , y , z ∈ X :
1. Reflexiva x ∼ x .
2. Sime´trica Se x ∼ y enta˜o y ∼ x .
3. Transitiva Se x ∼ y e y ∼ z enta˜o x ∼ z .
Exemplos: <,≤, 6=,= nos nu´meros inteiros.
Classes de equivaleˆncia
Se x ∈ X enta˜o a classe de equivaleˆncia de x e´ o conjunto de
elementos de X que sa˜o equivalentes a x por ∼. Denotamos:
x = {y ∈ X : y ∼ x}.
Propriedades:
I Qualquer elemento de uma classe de equivaleˆncia e´ um
representante de toda a classe.
I X e´ a unia˜o de todas as classes de equivaleˆncia.
I Duas classes de equivaleˆncia distintas na˜o podem ter um
elemento em comum.
Conjunto quociente = conjunto das classes de equivaleˆncia de ∼
em X .
Inteiros mo´dulo n
Dois inteiros a e b sa˜o congruentes mo´dulo n se a− b e´ mu´ltiplo
de n:
a ≡ b (mod n)
Exemplos:
10 ≡ 0 (mod 5) 23 ≡ 1 (mod 11)
Observac¸a˜o: Congrueˆncia mo´dulo n e´ uma relac¸a˜o de
equivaleˆncia:
I a ≡ a (mod n) (trivialmente)
I Se a ≡ b (mod n), enta˜o a− b e´ mu´ltiplo de n. Mas
b − a = −(a− b); logo, b − a tambe´m e´ mu´ltiplo de n.
Portanto b ≡ a (mod n).
I Transitividade: exerc´ıcio.
Zn
Zn = o conjunto de inteiros mo´dulo n. Ou seja, se a ∈ Z, enta˜o
a = {a + kn | k ∈ Z}
Em particular, 0 e´ o conjunto dos mu´ltiplos de n.
Algoritmo da divisa˜o de Euclides: dados a e n inteiros positivos,
a > n, existem inteiros q e r tais que
a = n.q + r 0 ≤ r ≤ n − 1
Ou seja, a− r ≡ 0 (mod n) e portanto a ≡ r (mod n). Em outras
palavras,
Zn = {0, 1, . . . , n − 1}
Artime´tica modular
Sejam a e b classes de Zn. Enta˜o,
a + b = a + b
Exemplo:
5 + 4 ≡ 9 ≡ 1 (mod 8)
Logo,
5 + 4 = 9 = 1
A diferenc¸a entre duas classes e´ definida de maneira ana´loga.
A fo´rmula para a multiplicac¸a˜o das classes a e b de Zn e´:
a.b = a.b
Artime´tica modular
Propriedades da adic¸a˜o:
A1 (a + b) + c = a + (b + c).
A2 a + b = b + a.
A3 a + 0 = a.
A4 a +−a = 0.
Artime´tica modular
Propriedades da multiplicac¸a˜o:
M1 (a.b).c = a.(b.c).
M2 a.b = b.a.
M3 a.1 = a.
AM a.(b + c) = a.b + a.c .
Exemplo: em Z6,
2.3 = 6 = 0!!!
Crite´rios de divisibilidade
Divisibilidade por 3: 3|a se a soma de todos os algarismos de a e´
divis´ıvel por 3.
Prova: Seja
a = anan−1 . . . a1a0
= an.10
n + an−1.10n−1 + . . . + a1.10 + a0
Como 10 ≡ 1 (mod 3),
a ≡ an + an−1 + . . . + a1 + a0 (mod 3)
Logo, a ≡ 0 (mod 3) se e somente se
an + an−1 + . . . + a1 + a0 ≡ 0 (mod 3)
Divisibilidade por 9 = mesma coisa!
Crite´rios de divisibilidade
Divisibilidade por 11: 11|a se a soma alternada de todos os
algarismos de a e´ divis´ıvel por 11.
Prova: Observe que 10 ≡ −1 (mod 11). Portanto,
10k ≡ (−1)k (mod 11)
e´ igual a 1 ou -1 dependendo da paridade de k. Logo,
a ≡ (−1)n.an + (−1)n−1.an−1 + . . . + a2 − a1 + a0 (mod 11)
Poteˆncias
Vamos calcular
3515 (mod 20)
Em primeiro lugar, escrevemos o expoente 15 na base 2:
15 = 23 + 22 + 2 + 1
Logo,
3515 = 352
3+22+2+1 = 35.352.352
2
.352
3
= 35.(35)2.(352)2.((352)2)2
Poteˆncias
Como 35 ≡ 15 (mod 20), 152 ≡ 5 (mod 20) e 52 ≡ 5 (mod 20),
temos:
3515 = 35.352.352
2
.352
3
≡ 15.(15)2.(352)2.((352)2)2 (mod 20)
≡ 15.5.(5)2.((352)2)2 (mod 20)
≡ 15.5.5.(5)2 (mod 20)
≡ 15.5.5.5 (mod 20)
≡ 15.5 (mod 20)
≡ 15 (mod 20)