MAT01375 - MATEMÁTICA DISCRETA B Eduardo Brietzke Lista 7

Prévia do material em texto

MAT 01375 – Matemática Discreta B – 2019/2 – Lista 7
1. Determine o resto da divisão de :
a) 210001 + 102001 por 7.
b) 102019 por 11.
c) 1010
10
por 7. Sugestão: Comece determinando a classe residual de 1010 módulo 6
(i.e., o resto da divisão de 1010 por 6).
2. a) Prove que todo número natural é congruente módulo 9 à soma de seus algarismos
(quando representado em base 10). Sugestão: Dado N ∈ N, seja N = anan−1 . . . a0
sua representação em base 10. Então N = an ·10n+ · · ·+a1 ·10+a0. Use que 10 ≡ 1
(mod 9) e, portanto, 10k ≡ 1 (mod 9).
b) Use o item anterior para justificar que um número natural é diviśıvel por 9 se e
somente se a soma de seus algarismos for diviśıvel por 9.
c) Obtenha o análogo aos itens anteriores com 3 em lugar de 9. Sugestão: Comece
mostrando que 9 | a −→ 3 | a.
3. a) Prove que todo número natural é congruente módulo 11 à soma alternada de seus
algarismos, mais precisamente
N = anan−1 . . . a0 =⇒ N ≡ a0 − a1 + a2 − · · ·+ (−1)nan (mod 11).
Sugestão: Use que 10 ≡ −1 (mod 11) e, portanto, 10k ≡ (−1)k (mod 11).
b) Use o item anterior para justificar que um número natural N = anan−1 . . . a0 é
diviśıvel por 11 se e somente se 11 |
(
a0 − a1 + a2 − · · ·+ (−1)nan
)
.
c) Justifique que são diviśıveis por 11 o números:
(i) 123456789987654321, (ii) 11111111 · · · 111 (cem 1s)
4. Seja S a relação em R× R = R2 definida por ((a, b), (c, d)) ∈ S ⇐⇒ a+ 2b = c+ 2d.
a) Mostre que S é uma relação de equivalência.
b) Determine as classes de equivalência de [(1, 1)] e [(2, 3)].
5. Prove que valem as seguintes propriedades em Z:
a) a | b e b | c =⇒ a | c.
b) a | r e a | s =⇒ a | (ur + vs).
c) a | b e a | (b+ c) =⇒ a | c.
d) a ≡ b (mod m1) e m2 | m1 =⇒ a ≡ b (mod m2).
6. Seja R a relação sobre Z dada por xRy ⇐⇒ 4 | (x+ 3y).
a) Mostre que a relação R é uma relação de equivalência.
b) Descreva a classe de equivalência [0].
c) Descreva a classe de equivalência [3].
7. Sejam P1 e P2 duas partições de um conjunto A. Dizemos que P2 é um refinamento de
P1 se qualquer conjunto de P2 estiver contido em algum conjunto de P1.
a) Mostre que a partição em Z determinada pela relação congruência módulo 6 é um
refinamento da partição determinada pela relação de congruência módulo 3.
b) Se P1 e P2 forem as partições determinadas pelas relações de equivalência R1 e R2
em A, mostre que P1 é um refinamento de P2 ⇐⇒ R1 ⊆ R2.
8. Seja xn o número de partições de conjunto de n elementos em exatamente duas partes.
Por exemplo, x2 = 1 porque a única partição de um conjunto A = {a, b} em exatamente
duas partes é como A = {a}∪{b}. Já x3 = 3, pois se A = {a, b, c}, então a = {a}∪{b, c} =
{b} ∪ {a, c} = {c} ∪ {a, b}.
a) Mostre que xn+1 = 2xn + 1, para todo n ≥ 2. Sugestão: Se |A| = n + 1, fixamos
um elemento a ∈ A e chamamos de B = A − {a}. Então |B| = n e o número de
partições de B é xn. Cada partição B = E ∪ F de B dá origem a duas partições de
A, A = (E ∪ {a}) ∪ F e A = E ∪ (F ∪ {a}). Além dessas, A ainda tem a partição
a = {a} ∪ (A− {a}).
b) Use o item anterior para completar a tabela
n xn
2 1
3 3
4 7
5
6
7
c) Use a tabela do item anterior para formular uma conjectura sobre uma expressão
para xn.
d) Prove a conjectura do item anterior por indução.
9. a) Prove que qualquer natural é congruente módulo 4 ao número formado com os dois
últimos algarismos de sua expansão decimal (por exemplo, 830552 ≡ 52 (mod 4)).
b) Mostre que um natural N é diviśıvel por 4 ⇐⇒ o número formado com os dois
últimos algarismos de sua expansão decimal for diviśıvel por 4.
10. a) Prove que qualquer natural é congruente módulo 8 ao número formado com os três
últimos algarismos de sua expansão decimal (por exemplo, 830552 ≡ 552 (mod 8)).
b) Mostre que um natural N é diviśıvel por 8 ⇐⇒ o número formado com os três
últimos algarismos de sua expansão decimal for diviśıvel por 8.
11. Considere a expansão binária N = an · 2n + an−1 · 2n−1 + · · ·+ a1 · 2 + a0 de um número
natural N , onde (∀k)
(
ak ∈ {0, 1}
)
.
a) Mostre que N ≡ a0 − a1 + a2 − · · ·+ (−1)nan (mod 3).
b) Mostre que 3 | N ⇐⇒ 3 |
(
a0 − a1 + a2 − · · ·+ (−1)nan
)
.
2