Sol_L3D131

Prévia do material em texto

MAT 01375 – Matemática Discreta B 2013/1
Lista de Exercícios 3
1.
(a) Sejam a, b, c ∈ Z tais que a | b e b | c. Por definição, existem k, ` ∈ Z tais que
b = k · a e c = ` · b. Portanto, c = ` · (k · a) = (` · k) · a, onde ` · k é inteiro, de
forma que a | c, como queríamos demonstrar.
(b) Sejam a, b números inteiros com a mesma paridade, isto é, ou ambos são pares
ou ambos são ímpares.
Caso 1 (a, b pares): Por definição, existem k, ` ∈ Z tais que a = 2k e b = 2`,
de forma que a+ b = 2k + 2` = 2(k + `). Esse número é par já que k + ` ∈ Z.
Caso 2 (a, b ímpares): Por definição, existem k, ` ∈ Z tais que a = 2k + 1 e
b = 2`+1, de forma que a+ b = (2k+1)+ (2`+1) = 2(k+ `+1). Esse número
é par já que k + `+ 1 ∈ Z.
(d) Por contraposição, suponha que x é par. Seja k ∈ Z tal que x = 2k. Portanto
x3 = (2k)3 = 2(4k3), que é par visto que 4k3 ∈ Z. Assim, se x é um número
inteiro tal que x3 é ímpar, temos que x também é ímpar.
(e) Por absurdo, suponha que existem a, b ∈ Z, a ≥ 2, tais que a | b e a | (b+1). Logo,
existem k, ` ∈ Z com b = ka e b+1 = `a, de forma que 1 = (b+1)−b = (`−k)a.
Isso implica que a | 1, contradizendo o fato de que a ≥ 2.
2.
(a) Falsa. (Contra-exemplo: a = 2, b = 3, c = 6.)
(c) Verdadeira. Sejam x e y números reais não-negativos. Os números
√
x e√y estão
bem definidos e satisfazem
0 ≤ (√x−√y)2 = (√x)2 − 2√x√y + (√y)2 = x+ y − 2√x√y.
Concluímos que 2√xy ≤ x+ y, como queríamos demonstrar.
(d) Verdadeira. Por contraposição, suponha que n é composto, isto é, n = ab para
certos inteiros positivos a, b com 1 < a, b < n. Lembrando que, dados um inteiro
positivo m e um número real arbitrário x, temos
xm − 1 = (x− 1)(xm−1 + xm−2 + · · ·+ x+ 1),
concluímos que
2ab − 1 = (2a)b − 1 = (2a − 1)
(
(2a(b−1) + 2a(b−2) + · · ·+ 2a + 1
)
.
Como a > 1, temos 2a − 1 > 1, e, como b > 1, temos n = 2ab − 1 > 2a − 1.
Portanto, na equação acima, temos uma fatoração de 2n− 1 em fatores próprios,
logo 2n − 1 é composto. Assim, se 2n − 1 é primo, o inteiro positivo n deve ser
primo.
(g) Falsa. Contra-exemplo: 0 é múltiplo de 3, mas não é a soma de três números
naturais consecutivos.
(h) Verdadeira. Seja n um número natural positivo que é um múltiplo de trés. Por
definição, temos n = 3k para certo inteiro k ≥ 1. Note que
n = 3k = (k − 1) + ((k − 1) + 1) + ((k − 1) + 2) ,
onde os termos da soma são números naturais consecutivos.
5.
(a) Suponha que n é primo e considere inteiros positivos a, b tais que n | a · b. Pelo
Teorema Fundamental da Aritmética, a · b pode ser escrito como
a · b = pe11 · · · pemm ,
onde p1, . . . , pm são primos e e1, . . . , em são inteiros positivos. Como n é primo e
divide a · b, temos n = pi para certo i ∈ {1, . . . ,m}. A unicidade da fatoração
em primos, a menos da ordem dos fatores, implica que pi aparece na fatoração de
a ou na fatoração de b, isto é, n | a ou n | b, como queríamos demonstrar.
(b) Por contraposição, suponha que n não é primo e seja n = a · b com 1 < a, b < n.
Logo, n divide a · b = n, mas não divide a nem b, isto é, n não tem a propriedade
de divisão de fatores. Isso implica que todo inteiro positivo com a propriedade de
divisão de fatores é primo.
(c) Por absurdo, suponha que p é primo e √p é racional. Considere inteiros positivos
a, b tais que √p = a/b. Podemos supor que a fração é irredutível.
É claro que
a = b
√
p =⇒ a2 = b2p, (1)
de forma que p divide a2. Como p tem a propriedade de divisão de fatores,
concluímos que p divide a, isto é, existe k ∈ Z tal que a = kp.
Substituindo a = kp em (1), temos
b2p = a2 = k2p2 =⇒ b2 = k2p.
Assim, p divide b2, logo divide b pela propriedade de divisão de fatores. Isso é
absurdo, já que implica que a fração a/b não é irredutível.
6. Por absurdo, suponha que p+q é um número primo, onde p, q são primos diferentes
de 2. Em particular, p e q são números ímpares maiores do que 2, de forma que a
sua soma p+ q é par pelo exercício 1(b). Isso implica que 2 é um fator de p+ q > 2,
contradizendo o fato de que p+ q é primo.