L3D131

Prévia do material em texto

MAT 01375 � Matemática Discreta B 2013/1
Lista de Exercícios 3
1. Demonstre os fatos abaixo. (Lembre que, para números inteiros x, y, a notação
x | y significa que x divide y e x - y significa que x não divide y.)
(a) Se a | b e b | c, então a | c.
(b) Se dois números inteiros têm a mesma paridade, então a sua soma é par.
(c) Se x é um inteiro ímpar, então x3 é ímpar.
(d) Seja x um número inteiro tal que x3 é ímpar. Então x é ímpar.
(e) Se a, b ∈ Z e a ≥ 2, então a - b ou a - (b+ 1).
(f) (∀n ∈ N) n é ímpar ⇐⇒ n é soma de dois números naturais consecutivos.
2. Decida se as afirmações abaixo são verdadeiras ou falsas. Justifique (no caso de a
afirmação ser verdadeira, demonstre-a. Se for falsa, apresente um contra-exemplo).
(a) Sejam a, b, c números inteiros positivos tais que a | c, b | c e a < b. Então a | b.
(b) Sejam a, b números inteiros tais que a | b. Então a2 | b2.
(c) Sejam x e y números reais não-negativos. Então 2 · √xy ≤ x+ y.
(d) Se n ∈ N e 2n − 1 é primo, então n é primo.
(e) (∀a, b ∈ Z) a|b e b|a =⇒ a = b.
(f) A soma de três números naturais consecutivos é um número natural múltiplo de
três.
(g) Se n é número natural múltiplo de três, então n é a soma de três números naturais
consecutivos.
(h) Se n é número natural não nulo que é um múltiplo de três, então n é a soma de
três números naturais consecutivos.
3. Mostre que:
(a) (∀n ∈ N) k ≤ n =⇒ k | (n! + k)
(b) existem sequências arbitariamente longas de números consecutivos compostos.
4. Mostre que:
(a) (∀n ∈ N) n é um múltiplo de 3 ⇐⇒ n2 é um múltiplo de 3.
(b)
√
3 é um número irracional.
5. Dizemos que um inteiro positivo n ≥ 2 possui a propriedade de divisão de fatores
se, para quaisquer inteiros a, b, vale que
[(n | a · b) −→ (n | a ou n | b)]
.
(a) Mostre que todo número primo possui a propriedade de divisão de fatores.
(b) Mostre que se um número inteiro positivo possui a propriedade de divisão de
fatores então ele é primo.
(c) Utilize esse fato para demonstrar que
√
p é irracional para todo primo p.
6. Mostre que se a soma de dois primos é um número primo então um dos primos é 2.