Exercicios resolvidos

Prévia do material em texto

Fundamentos de A´lgebra: Exerc´ıcios 4, Umas
Soluc¸o˜es
1. Utilize o algoritmo de Euclides para calcular d = mdc(a, b) e escrever
d = xa + yb, sendo
(a) a = 232, b = 136
(b) a = 187, b = 221
(c) a = −39, b = 17.
R:
(a) 8
(b) 17
(c) 1
2. Encontre os poss´ıveis valores de a ∈ Z tal que mdc(20 + a, a) = 4.
R: Observe primeiro que mdc(20 + a, a) = 4, implica que 4 | a. Mas
quando 4 | a, podemos escrever a = 4k e temos que
20 + a = 20 + 4k = 4(5 + k),
logo 4 | (20 + a) tambe´m, logo 4 | mdc(20 + 4k, 4k). Estamos procurando
k tal que mdc(4(5 + k), 4k) = 4. Logo, estamos procurando k tal que
mdc(5 + k, k) = 1. Seja d = mdc(5 + k, k). Enta˜o d | k e d | (5 + k), logo
d | (5 + k)− k = 5. Segue que d = 5 ou 1.
5 | k =⇒ 5 | (5 + k) =⇒ mdc(5 + k, k) = 5.
5 6| k =⇒ 5 6| mdc(5 + k, k) =⇒ mdc(5 + k, k) = 1.
Logo, os a tais que mdc(20 + a, a) = 4 sa˜o os a tais que 4 | a mas 5 6| a.
3. Se p e´ um primo e mdc(a, b) = p, quais sa˜o os poss´ıveis valores de
mdc(a2, b)? E de mdc(a2, b2)?
R: Observamos primeiro que nenhuns primos ale´m de p dividem mdc(a2, b)
(ou mdc(a2, b2)). Seja q 6= p primo. Enta˜o q | mdc(a2, b) implica que q | b
e q | a2. Mas q | a2 implica que q | a pois q e´ primo, logo q | mdc(a, b)
tambe´m – imposs´ıvel, pois mdc(a, b) = p.
Logo mdc(a2, b2) = pn para algum n. Dois casos:
1
Caso p2 | b: Logo p divide a mas p2 na˜o divide a. Segue que p2 divide a2
mas p3 na˜o divide a2. Logo mdc(a2, b) = p2.
Caso p2 6| b: logo p2 6| mdc(a2, b) e mdc(a2, b) = p.
Agora consideramos mdc(a2, b2). Temos que p2 6| a ou p2 6| b, mas p | a e
p | b. Logo p2 | a2 e p2 | b2, mas p3 6| a ou p3 6| b. Logo a u´nica possibilidade
e´ ‘mdc(a2, b2) = p2.
4. Seja n um natural tal que mdc(n, 6) = 1. Mostre que n2− 1 e´ mu´ltiplo de
12.
Escreve n = 6k+ r por algum k e algum r ∈ {0, 1, 2, 3, 4, 5}. Sabemos que
r 6= 0, 2, 3, 4 pois nestes casos, mdc(n, 6) 6= 1. Logo n = 6k + 1 ou 6k + 5.
Caso n = 6k + 1: Logo
n2 − 1 = (6k + 1)2 − 1 = 36k2 + 12k + 1− 1 = 12(3k2 + 1),
logo 12 | n2 − 1. O caso n = 6k + 5 e´ similar.
5. Se mdc(a, b) = 1 enta˜o mdc(a + b, a− b) = 1 ou 2.
R: Seja d = mdc(a + b, a− b). Enta˜o d | (a + b) e d | (a− b). Logo
d | ((a + b) + (a− b)) = 2a
d | ((a + b)− (a− b)) = 2b.
Logo d | mdc(2a, 2b) = 2 pois mdc(a, b) = 1.
Enta˜o, d > 0 e d | 2. Segue que d = 1 ou d = 2.
6. Considerando a, b ∈ Z e p um nu´mero primo nas afirmativas abaixo, veri-
fique se estas sa˜o verdadeiras ou falsas. Justifique.
(a) Se a + mdc(a, b) e´ par enta˜o a + b e´ par.
(b) Se a + mdc(a, b) e´ ı´mpar enta˜o a + b e´ ı´mpar.
(c) Se d = mdc(a, a2 + b2) enta˜o d | (a− b)2.
R:
(a) Falsa. Contraexemplo a = 1, b = 2. 1 + mdc(1, 2) = 1 + 1 = 2 e´ par,
mas 1 + 2 = 3 na˜o e´ par.
(b) Verdadeira. Dois casos:
a par implica que b e´ ı´mpar, pois mdc(a, b) precisa de ser ı´mpar. Logo
a + b e´ par + ı´mpar = ı´mpar.
a ı´mpar implica ja´ que mdc(a, b) e´ ı´mpar. Logo a+mdc(a, b) e´ ı´mpar
+ ı´mpar = par, enta˜o este caso na˜o acontece.
(c) Verdadeira. Sejam a = dk, (a2 + b2) = dq para alguns k, q. Logo
(a− b)2 = a2 − 2ab+ b2 = (a2 + b2)− 2ab = dq − 2bdk = d(q − 2bk),
logo d | (a− b)2.
2
7. Considere a e b inteiros na˜o nulos. Mostre que o conjunto
S = {ax + by | x, y ∈ Z e ax + by > 0}
das combinac¸o˜es lineares inteiras positivas de a e b conte´m um elemento
mı´nimo. Mostre que este elemento mı´nimo e´ exatamente o ma´ximo divisor
comum de a e b.
R: Omitida.
8. Considerando a sequeˆncia de Fibonacci dada por F1 = 1, F2 = 1 e
Fn = Fn−1 + Fn−2, para n > 3, mostre que mdc(Fn, Fn+1) = 1, para
todo n > 1.
R: Induc¸a˜o em n. Dois casos bases. mdc(F1, F2) = mdc(F2, F3) =
mdc(1, 2) = 1.
HI: Suponha que mdc(Fk, Fk+1) = 1 para algum k.
Etapa de induc¸a˜o: Queremos mostrar que d = mdc(Fk+1, Fk+2) = 1.
Escreve Fk+1 = dq, Fk+2 = ds para alguns q, s. Temos
ds = Fk+2 = Fk + Fk+1 = Fk + dq,
enta˜o Fk = d(s − q), logo d | Fk. Mas d | Fk, d | Fk+1 implica que
d | mdc(Fk, Fk+1) = 1. Logo d = 1 e a etapa de induc¸a˜o esta´ completa.
Agora o princ´ıpio da induc¸a˜o diz que mdc(Fn, Fn+1) = 1 para todo n > 1.
9. Calcule mmc(a, b) dos pares a, b da Questa˜o 1.
R: Simplesmente use a fo´rmula mmc(a, b) = |ab|mdc(a,b) :
(a) 3944
(b) 2431
(c) 663.
3