Congruências

Prévia do material em texto

Congrueˆncias
Renata de Freitas e Petrucio Viana
Instituto de Matema´tica e Estat´ıstica, UFF
Abril de 2011
Suma´rio
• Congrueˆncia mo´dulo n.
• Conjunto quociente mo´dulo n.
Pele´
• O camisa 10.
Par ou ı´mpar
Congrueˆncia mo´dulo 2
Dois naturais sa˜o congruentes mo´dulo 2 quando deixam o mesmo
resto na divisa˜o por 2.
Definic¸a˜o Sejam a, b ∈ N.
Dizemos que a e b sa˜o congruentes mo´dulo 2, denotado por
a ≡2 b, se existem qa, qb, r ∈ N tais que 0 ≤ r < 2,
a = qan + r e b = qbn + r .
Congrueˆncia mo´dulo 2
Observe que ≡2 e´ uma relac¸a˜o em N:
≡2= {(a, b) ∈ N× N : a ≡2 b}
Congrueˆncia mo´dulo 2
Proposic¸a˜o ≡2 e´ uma relac¸a˜o de equivaleˆncia em N.
Par ou ı´mpar de muitos
Congrueˆncia mo´dulo n
Definic¸a˜o Seja n ∈ N∗. Sejam a, b ∈ N.
Dizemos que a e b sa˜o congruentes mo´dulo n, denotado por
a ≡n b, se existem qa, qb, r ∈ N tais que 0 ≤ r < n,
a = qan + r e b = qbn + r .
Congrueˆncia mo´dulo n
Proposic¸a˜o Seja n ∈ N∗.
≡n e´ uma relac¸a˜o de equivaleˆncia em N.
Classes de equivaleˆncia mo´dulo 5
Definic¸a˜o Seja a ∈ N.
A classe de equivaleˆncia de a mo´dulo 5 e´ o conjunto
[a]5 = {b ∈ N : a ≡5 b}.
Classes de equivaleˆncia mo´dulo 5
Proposic¸a˜o Para todos a, b ∈ N,
(1) a ∈ [a]5.
(2) Se a 6≡5 b, enta˜o [a]5 ∩ [b]5 = ∅.
(3) N = [0]5 ∪ [1]5 ∪ [2]5 ∪ [3]5 ∪ [4]5.
Classes de equivaleˆncia mo´dulo n
Definic¸a˜o Seja n ∈ N∗. Seja a ∈ N.
A classe de equivaleˆncia de a mo´dulo n e´ o conjunto
[a]n = {b ∈ N : a ≡n b}.
Classes de equivaleˆncia mo´dulo n
Proposic¸a˜o Para todos n ∈ N∗, a, b ∈ N,
(1) a ∈ [a]n.
(2) Se a 6≡n b, enta˜o [a]n ∩ [b]n = ∅.
(3) N = [0]n ∪ [1]n ∪ [2]n ∪ [3]n ∪ [4]n ∪ · · · ∪ [n − 1]n.
Conjunto quociente mo´dulo 3
Definic¸a˜o O conjunto quociente mo´dulo 3 e´ o conjunto
N3 = {[0]3, [1]3, [2]3}.
Observe que
[0]3 = {0, 3, 6, 9, . . .},
[1]3 = {1, 4, 7, 10, . . .},
[2]3 = {2, 5, 8, 11, . . .},
ou seja, N3 e´ um conjunto finito cujos elementos sa˜o conjuntos
infinitos.
Conjunto quociente mo´dulo n
Definic¸a˜o Seja n ∈ N∗. O conjunto quociente mo´dulo n e´ o
conjunto
Nn = {[0]n, [1]n, [2]n, . . . , [n − 1]n}.
Observe que
[0]n = {0, n, 2n, 3n, . . .},
[1]3 = {1, n + 1, 2n + 1, 3n + 1, . . .},
[2]3 = {2, n + 2, 2n + 2, 3n + 2, . . .},
· · ·
[n− 1]n = {n− 1, n + (n− 1), 2n + (n− 1), 3n + (n− 1), . . .},
ou seja, Nn e´ um conjunto finito cujos elementos sa˜o conjuntos
infinitos.
Exerc´ıcios
1. Exerc´ıcios do Menezes
(Paulo B. Menezes, Matema´tica Discreta para Computac¸a˜o e
Informa´tica, 2a. edic¸a˜o, Sagra Luzzatto / Instituto de Informa´tica da
UFRGS, Porto Alegre, 2006).
2. Exerc´ıcios do Scheinerman
(E.R. Scheinerman, Matema´tica Discreta, Thomson, Sa˜o Paulo, 2006).
3. Exerc´ıcios da Lista 12.
	Congruência módulo n