01 – Determinar:
(a) mdc(11, 99). Solução: 99 : 11 = 9 , resto zero ? mdc(11,99) = 11 .
(b) mdc(-21,14). Solução: mdc(-21, 14) = mdc(21, 14) ? 21 : 14 = 1 resto 7 ? 14:7 = 2, resto zero ? mdc(-21, 14) = 7 .
(c) mdc(17, 18). Solução: 18 : 17 = 1, resto 1 ? 17 : 1 = 17 resto 0 ? mdc(17, 18) = 1.
02 – Achar os elementos do conjunto A = {1, 2, 3, 4, 5} que são primos com 8.
/Solução: Os primos com 8 são aqueles que não têm fatores primos iguais aos fatores primos de 8. Como 8 só tem fator primo igual a 2 (8 = 23), e os únicos que não apresentam o fator 2 na decomposição são: 1, 3 e 5. Resposta: 1, 3 e 5
03 – Seja o conjunto A = {1, 2, 3, 4, 5, 6}. Enumerar os elementos do conjunto X = {x ? A | mdc(x, 6) = 1}.
Solução: Se mdc(x, 6) = 1, x e 6 são primos entre si. Os fatores de 6 são 2 e 3. Os elementos de A que, na decomposição não apresentam os fatores 2 e 3 são: 1 e 5. Resposta: 1 e 5
04 – Sabendo que o mdc(a, 0) = 13, achar todos os valores do inteiro a.
Solução: Todo número é divisor de 0. O maior divisor de 13 é 13, portanto, mdc(a, 0) = 13.
05 – Achar o menor inteiro positivo c, da forma c = 22x + 55y, onde x e y são dois inteiros.
Solução: Como c = 22x + 55y, c é múltiplo do mdc(22, 55). ? 55 : 22 = 2, resto 11 ? 22 : 11 = 2, resto zero. Portanto, mdc(22, 55) = 11.
Como c é inteiro positivo e múltiplo de 11, o menor inteiro nestas condições é o próprio 11.
06 – Sendo n um inteiro qualquer, calcular o mdc(n, n + 1).
Solução: (n + 1):n = 1, resto 1 Þ n : 1 = n, resto 1 ? 1:1 = 1, resto zero. Portanto, mdc(n, n + 1) = 1.
07 – Calcular
(a) mdc(n, n + 2), sendo n um inteiro par.
Solução: Se n é par, temos n = 2k e n + 2 = 2k + 2 = 2(k + 1).
Como foi visto no exercício 06, deste capítulo, k e k + 1 são primos entre si.
Portanto, mdc[2k, 2(k + 1)] = 2, pois 2 é o único fator comum de 2k e 2(k + 1).
(b) mdc(n, n + 2), sendo n um inteiro ímpar.
Solução: (n + 2) : n = 1, resto = 2. ? n : 2 = k, resto 1.
2 : 1 = 2, resto zero. Portanto, mdc(n, n + 2) = 1.
08 – Sendo n um inteiro qualquer, achar os possíveis valores do máximo divisor comum dos inteiros n e n + 10.
Solução:- Seja k, o mdc de n e n + 10.
Podemos então escrever: n = qa e n + 10 = q’a.
Substituindo n de (n = qa) em n + 10 = q’a, resulta qa + 10 = q’a ? 10 = a(q’ – q) ? a | 10. Portanto, a = 1, 2, 5 ou 10, que são os divisores de 10.
09 – Sendo n um inteiro qualquer, calcular o mdc(n – 1, n2 + n + 1).
Solução: (n2 + n + 1) : n – 1 = n + 2, resto 3.
(n – 1) : 3 = k, qualquer, restos possíveis 1, 2, 0.
Se o resto for zero, mdc(n – 1, n2 + n + 1) = 3.
Se o resto for 1, 3 : 1 = 3, resto zero ? mdc(n – 1, n2 + n + 1) = 1
Se o resto for 2, 3 : 2 = 1, resto 1 ? 2 : 1 = 2, resto zero ? mdc(n – 1, n2 + n + 1) = 1.
Portanto, mdc(n – 1, n2 + n + 1) = 1 ou 3.
10 – Sendo a e b dois inteiros não conjuntamente nulos (a ? 0 ou b ? 0), mostrar:
mdc(a, b) = mdc(-a, b) = mdc(a, -b) = mdc(-a, -b).
Solução: Se c | a então a = qc. Temos que - a = (-q)c ? c | (-a) ? todo divisor de a é divisor de (-a) ? maior divisor de a é também o maior divisor de –a . O mesmo ocorre com b e –b. Portanto, podemos concluir que o maior divisor comum de a e b, é também de (–a) e b, de a e (–b) e o de (-a) e (-b). Assim, mdc(a, b) = mdc(-a, b) = mdc(a, -b) = mdc(-a, -b). Cqd.
11 – Sejam a, b e c inteiros. Demonstrar:
(a) existem inteiros x e y tais que c = ax + by se e somente se o mdc(a, b) | c.
Solução: suponhamos que ax + by = c tenha uma solução axo + byo = c.
Se d = mdc(a, b) existem os inteiros r e s tais que a = dr e b = ds, e temos:
c = axo + byo = drxo + dsyo = d(rxo + syo). Como rxo + syo é um inteiro, d | c ou mdc(a, b) | c.
Por outro lado, se d = mdc(a, b) | c, c = dk, com k inteiro.
Por ser d = mdc(a, b), existem os inteiros xo e yo tais que d = axo + byo ? c = dk = a(xok) + b(yok) = ax + by. Cqd.
(b) se existem inteiros x e y tais que ax + by = mdc(a, b) então mdc(x, y) = 1.
Solução: Seja d = mdc(a, b). Temos então ax + by = d ? (a/d)x + (b/d)y = (d/d) ? (a/d)x + (b/d)y = 1. (a/d) e (b/d) são inteiros pois d é divisor comum de a e de.
Portanto existem os inteiros (a/d) e (b/d), tais que (a/d)x + (b/d)y = 1 ? 1 é múltiplo do mdc(x, y). Como 1 só é múltiplo de 1, conclui-se que mdc(x, y) = 1. Cqd
12 – Sejam a, b e c inteiros. Demonstrar:
(a) se o mdc(a, b) = 1 então o mdc(ac, b) = mdc(b, c)
Solução: Mdc(a,b) = 1 ? 1 é o único divisor comum de “a” e “b” ? ?x, se x | b então x 
a.
Seja d = mdc(ac, b). Portanto, d | ac e d | b.
Se x é um divisor de d, temos d = kx (k inteiro) e, como d | ac, temos ac = dq (q inteiro) ? ac = kxq = x(kq). Como kq é inteiro, x | ac. Portanto, todo divisor de d é divisor de ac.
Seja então d = x1.x2.x3....xn onde x1, x2, x3, ... xn são os fatores primos de d.
De ac = dq, obtemos ac = x1.x2.x3....xn . q. Como q é inteiro, ac/x1.x2.x3....xn = q ? ac/x1.x2.x3....xn é inteiro.
Um vez que nenhum dos xi (divisores de d) divide a, todos os xi dividem c ? d /c.
Assim d | c e d | b ? mdc(b, c) = kd, k > 1 (1) (o mdc de 2 números é positivo).
Como d = maior divisor comum de ac e b e | c | < | ac | e D( C ) ? D(ac) ? kd não pode ser maior que d. Portanto kd < d com k positivo como visto acima ? k < 1 (2)
De (1) e (2) conclui-se que k = 1 ? kd = d. Portanto, mdc(b, c) = d = mdc(ac, b). Cqd.
(b) Se o mdc(a, b) = 1 e se c | (a + b), então o mdc(a, c) = 1 e o mdc(b, c) = 1.
Solução:
(1) Mdc(a, b ) = 1 ? então existem os inteiros x e y, tais que ax + bx = 1 (i) .
Se c | (a + b) então a + b = qc , q inteiro ? b = qc – a (ii)
Substituindo ( ii) em (i), resulta ax + (qc – a)y = 1 ? ax – ay + qcy = 1 ? a(x – y) + c(qy) = 1 com (x – y) e qy inteiros.
Assim, existem os inteiros x’ = x – y e y’ = qy, tais que ax’ + cy’ = 1 ? mdc(a, c) = 1.
(2) De a + b = qc tira-se a = qc – b, que substituído em ( i ) resulta:
qc – b)x + by = 1 ? qcx – bx + by = 1 ? b(y – x) + c(qx) = 1. Como y – x e qx são inteiros, , conclui-se que
mdc(b, c) = 1. Cqd.
(c) se b | c, então o mdc(a, b) = mdc(a + c, b).
Solução: Se b | c então c = bq (q inteiro).
Seja então d = mdc(a + c, b) (1) ? existem x e y inteiros tais que (a + c)x + by = d ? ax + bqx + by = d ? ax + b(qx + y) = d, sendo x e qx + y inteiros ? (a/d)x’ + (b/d)y’ = 1 ? mdc[(a/d), (b/d)] = 1 ? (2) (a/d) e (b/d) são primos entre si.
De (a/d)x’ + (b/d)y’ = 1 temos ax’ + by’ = d ? mdc(a, b) é múltiplo de d. Assim, temos mdc(a,b) = d’ ? d = kd’.
De ax’ + by’ = kd’ tiramos (a/kd’)x’ + (b/kd’)y’ = 1 ? a/kd’ e b/kd’ são primos entre si.
Ora a / d = a/ kd’ = (a/d’)/k e b / d = b/kd’ = (b/d’)/k ? a/d’ e b/d’ têm pelo menos um fator comum que é k.
Como visto acima a/d’ e b/d’ são primos entre si. Portanto, o único fator comum é 1. Assim, a/d = a/d’ e b/d = b/d’ ? d = d’ . Portanto, mdc(a, b) = d’ = d (4).
De (1) e (4) conclui-se mdc(a, b) = mdc(a + c, b). Cqd.
(d) Se mdc(a, b) = 1, então mdc(am, bn) = 1.
Solução: Seja d = mdc(am, bn). Temos então que existem os inteiros x e y tais que amx + bny = d ? a(am –1)x + b(bn –1)y = d.
Como (am –1)x e (bn –1)y são inteiros, podemos escrever ax’ + by’ = d ? d é múltiplo do mdc(a,b).
Tiramos então (a/d)x’ + (b/d)y’ = 1.
Como mdc(a, b) = 1, a e b são primos entre si portanto, o único divisor comum de a e b é 1 ? d = 1. Portanto, mdc(am, bn) = 1. Cqd.
13 – Calcular o mdc(a + b, a – b) sabendo que a e b são inteiros primos entre si.
Solução: Se a e b são primos entre si, não podem ser ambos pares pois o mdc seria 2 ou múltiplo de 2. Portanto, a e b são ambos ímpares ou são de paridades diferentes.
(1º caso) - a e b com paridades diferentes – (a = 2k + 1 b = 2k’)
Temos então:
a + b = 2k + 1 + 2k’ = 2(k + k’) + 1 = 2n + 1 ? a + b é ímpar.
a – b = 2k + 1 – 2k’ = 2(k – k’) + 1 = 2m + 1 ? a – b é ímpar.
Portanto, o mdc(a + b, a – b) é um número ímpar.
Seja então mdc(a + b, a – b) = 2k + 1 ? existem x e y tais que (a + b)x + (a – b)y = 2k + 1 ?
[(a + b)/(2k+1)]x + [(a – b)/(2k + 1)]y = 1 ? (a + b)/(2k + 1) e (a – b)/(k + 1) são primos entre si.
Fazendo r = (a + b)/(2k + 1) e s = (a – b)/(2k + 1), resulta: a + b = r(2k + 1) (i) e a – b = s(2k + 1) (ii).
Como (a + b), (a – b) e (2k + 1) são ímpares, r e s também são ímpares.
Além disso r e s ímpares, r + s e r – s são pares.
Somando membro a membro as igualdades (i) e (ii), resulta:
2a = (2k + 1)(r + s) ? a = (2k + 1)[(r + s)/2] pois s + r é par (inteiro), portanto 2 | (r + s).
Assim, existe o inteiro (r + s)/2, tal que a = (2k + 1)[(r + s)/2) ? 2k + 1 | a .
Subtraindo membro a membro as igualdades (i) e (ii),
2b = (2k + 1)(r – s) ? b = (2k + 1)[(r – s)/2]. (r – s) é par. Portanto, (r – s)/2 é inteiro.
Assim, existe o inteiro (r – s)/2, tal que b = (2k + 1)[(r – s)/2] ? 2k + 1 | b.
Ora, a e b são primos entre si. Portanto, o único divisor comum é 2k + 1. Disto permite-se escrever 2k + 1 = 1 ? = mdc(a + b, a – b).
(2º caso) a e b são ímpares ? a = 2k + 1 e b = 2k’ + 1.
Temos, então:
(a + b) = 2k + 1 + 2k’ + 1 ? (a + b) = 2(k + k’ + 1)
(a – b) = 2k + 1 – 2k’ – 1 = 2(k – k’)
Das igualdades acima, concluímos que (a + b) e (a – b) são pares. Portanto, o mdc é da forma 2k. Assim, existem x e y, tais que: (a + b)x + (a – b)y = 2k ? r = (a + b)/2k e s = (a – b)/2k são primos entre si.
(a + b) = 2kr (i) e (a – b) = 2ks (ii).
Somando membro a membro, 2a = 2k(r + s) ? a = k(r + s) ? k | a
Subtraindo membro a membro, 2b = 2k(r – s) ? b = k(r – s) ? k | b.
Como a e b são primos entre si, o único divisor comum de a e b é 1. Portanto, k = 1 e
Mdc(a + b, a – b) = 2k ? mdc(a + b, a – b) =2.1 = 2.
Portanto, se a e b são primos então mdc(a + b, a – b) é 1 ou 2.
14 – O mdc de dois inteiros positivos é 10 e o maior deles é 120. Determinar o outro inteiro.
Solução: Seja a < 120, tal que mdc(a, 120) 10. O mdc de dois números é igual ao produto dos fatores primos comuns (com seus menores expoentes) desses dois números. Os fatores de 120 são 23.3.5. Assim, "a" deve ser um múltiplo de 10, menor que 120 que contenha os fatores 2 e 5 e outros fatores primos que não sejam outro 2, e 3. Portanto, resta apenas os fatores primos 5, 7 e 11. Deste modo "a" pode ser 2.5 = 10, 2.5.7 = 70 ou 2.5.11 = 110. Resposta: 10, 70, 110.
15 – Achar o maior inteiro positivo pelo qual se devem dividir os inteiros 160, 198 e 370 para que os restos sejam respectivamente 7, 11 e 13.
Solução: Se 7, 11 e 13 são os restos, a divisão de 160 – 7 = 153, 198 – 11 = 187 e 370 – 13 = 357 pelo inteiro positivo é exata. Como esse inteiro é o maior inteiro positivo, esse número é o mdc(153, 187, 357).
Mdc(357, 187)
357 = 187x1 + 170
187 = 170x1 + 17
170 = 17x 10 + 0 ? mdc (357, 187) = 17.
Mdc(153, 17)
153 = 17x9 ? mdc(153, 17) = 17. Portanto, o número é 17. Resposta: 17.
16 – Determinar os inteiros positivos a e b, sabendo-se que:
(a) a + b = 64 e mdc(a, b) = 9
Solução: Se mdc(a, b) = 9, então a e b são múltiplos de 9.
Portanto, 9x + 9b = 63 ? x + y = 7. ? x = 1, y = 6; x = 2, y = 5; x = 3, y = 4. Os demais valores inteiros de x resultarão em iguais valores para o para (a, b).
Para x = 1, a = 9.1 = 9 e b = 9.6 = 54; para x = 2, a = 9.2 = 18 e b = 9.5 = 45; a = 9.3 = 27 e b = 9.4 = 36.
Resposta, 9 e 54; 18 e 45 ou 27 e 36.
(b) ab = 756 e mdc(a, b) = 6.
Solução: Como acima, 6r.6s = 36rs = 756 ? rs = 21 ? r = 7 e s = 3 ou r = 3 e s = 7.
Portanto, os números são 6.3 = 18 e 6.7 = 42.
Resposta:42.
17 – Os restos das divisões dos inteiros 4933 e 4435 por um inteiro positivo n são respectivamente 37 e 19. Achar o inteiro n.
Solução: Como os restos são 37 e 19, 4933 – 37 = 4896 e 4435 – 19 = 4416 são múltiplos comuns de n.
Portanto, n é divisor comum de 4896 e 4416 ? n é divisor do mdc(4869, 4416).
Mdc(4869, 4416)
4896 = 4416x1 + 480
4416 = 480x 9 + 96
480 = 96x5 + 0 ? mdc(4896, 4416) = 96.
N é um divisor de 96, maior que 37 que é o resto da divisão de 4933 por n. Portanto, n = 96 ou n = 48. Resposta: 96 e 48.
18 – Demonstrar que se n = abc + 1, então o mdc(n, a) = mdc(n, b) = mdc(n, c) = 1.
Solução: n = abc + 1 ? n – abc = 1 ? n(1) + a(-bc) = 1. Como (1) e (-bc) são inteiros, conclui-se que mdc(n,a) = 1.
De forma semelhante:
n(1) + b(-ac) = 1 n(1) + c(-ab) = 1 ? mdc(n, a) = mdc(n, b) = mdc(n, c) = 1. Cqd.
19 – Demonstrar que mdc(mdc(a, b), b) = mdc(a, b)
Solução: A definição do mdc de três números mdc(a,b, c) = mdc(mdc(a, b), c), quaisquer que sejam a, b e c.
Fazendo c = b, temos mdc(mdc(a, b), b) = mdc(a, b, b) = mdc(a, mdc(b, b)) = mdc(a, b) pois mdc(b, b) = b. Cqd.
20 – Demonstrar que o mdc(n + k, k) = 1 se e somente se o mdc(n, k) = 1.
Solução: Se mdc(n + k, k) = 1, então existem os inteiros x e y, tais que (n + k)x+ ky = 1 ? nx + k(a + b) = 1 ? (n, k) = 1.
Por outro lado, se mdc(n, k) = 1, então existem a e b tais que na + kb = 1. Fazendo a = x e b = x + y, teremos nx + k(x + y) = 1 ? (n + k)x + ky = 1 ? mdc(n + k), k) = 1. Cqd.
21 – Demonstrar que, se a | bc e se mdc(a, b) = d, então a | cd.
Solução: a | bc ? existe o inteiro “x” tal que a.x = bc. (1)
Mdc(a, b) = d ? a/d e b/d são primos entre si. (2)
Dividindo os dois membros da igualdade (1) por d, resulta: (ax)/d = (bc)/d ? (a/d)x = (b/d).c
Como (a/d) e (b/d) são primos, (a/d) | c, de acordo com o teorema de Euclides (se m | np e mdc(m, n) = 1 então m | p). Ora a/d | c ? (a/d).d | c.d ? a | cd. Cqd.
22 – Demonstrar que, se a | c, se b | c e se o mdc(a, b) = d então ab | cd.
Solução: a | c ? existe k inteiro tal que c = a . k ? c = (a/d).d.k pois d | a uma vez que mdc(a,b) = d. Portanto, existe o inteiro x = dk, tal que c = (a/d).x (i).
Da mesma forma pode-se escrever c = (a/d)y (ii).
Multiplicando (i) por (ii), temos c2 = (a/d)(b/d)xy ? c2.d2 = (ab)xy ? (cd)2 = (ab)xy. ? (ab) | (cd)2.
De (ab) | (cd)2, tiramos mdc(ab, (cd)2) = ab ? existem x e y tais que (ab)x + (cd)2 y = ab ? (ab) + (cd)[(cd)y] = ab ? ab é múltiplo do mdc(ab, cd). Como o mdc é menor ou igual a ab, então mdc(ab, cd) = ab ? ab | cd. Cqd.
23 – Demonstrar que se mdc(a, b) = 1 e se mdc(a,c) = d,então mdc(a, bc) = d.
Solução: Se mdc(a, b) = 1, os únicos divisores de a que dividem b são -1 e + 1.
Como mdc(a, c) = d, todos os divisores de d dividem a e c. Assim, nenhum divisor de d divide b.
Temos então dc(a, bc) = conjunto dos divisores de a que dividem bc.
Como dos divisores de bc são divisores de b ou de c, somente os divisores de c, não divisores de b, (exceto –1 e 1), podem ser divisores de a . Portanto, existem divisores comuns a “a” e “c” que são os mesmos de “a” e “bc” . Portanto, max(divisores de a e c) = max(divisores de a e bc) ? mdc(a, bc) = mdc(a, c) = d. Cqd.
24 – O inteiro ímpar d é um divisor de a + b e de a – b. Demontrar que d também é um divisor do mdc(a, b).
Solução: Como d é divisor de (a + b) e (a – b) então existem os inteiros x e y tais que (a + b) = d.x e (a – b) = d.y. Somando membro a membro as expressões, resulta 2a = d (x + y). Como d é ímpar, (x+y) é par pois o produto d(x+y) é par (igual a 2a). Portanto, a = d[(x + y)/2] ? d|a.
Subtraindo as expressões, temos 2b = d(x–y). Como d é ímpar e o produto d(x–y) é par, (x–y) é par ? (x – y)2 é inteiro. Assim, b = d[(x – y)/2] ? d | b.
Como visto, d | a e d | b ? d | mdc(a, b) ou d é um divisor do mdc(a, b). Cqd.
25 – Os inteiros positivos a, b e c são tais que o mdc(a, b) = 1, a | c e c | b. Demonstrar que a = 1.
Solução: Se a | c e c | b então a | b. Como a | b, resulta mdc(a, b) = a. Como o mdc de dois números é único e mdc(a, b) = 1, temos mdc(a,b) = 1 = a ? a = 1. Cqd.
26 – O mdc(n, n + k) = 1 para todo inteiro positivo n. Demonstrar que k = 1 ou k = -1.
Solução: Mdc(n, n + k) = 1 ? existem os inteiros x e y, tais que nx + (n + k)y = 1 ? n(x – y) + ky = 1 ? mdc(n, k) =1. Como os divisores comuns de dois números são divisores de seu mdc, temos que os divisores comuns de n e k são – 1 e + 1. Conforme enunciado, n é todo inteiro positivo. Isto permite concluir que k = 1 ou k = - 1. Cqd.
27 – Demonstrar que mdc(a, b) = mdc(a + kb, b) para todo inteiro k.
Solução: Seja d = mdc(a + kb, b). Portanto, existem os inteiros x e y tais que (a + kb)x + by = d ? ax + b(kx + y) = d ? d é múltiplo do mdc(a, b) (1).
Como d é o mdc(a + kb, b) então d | (a + kb) e d | b (2) que leva a concluir que existem os inteiros r e s tais que (a + kb) = dr (3) e b = ds (4).
Substituindo (4) em (3) resulta a + kds = dr ? a = dr – kds = d(r – ks). (r – ks) é um inteiro pois k, r e s são inteiros. Portanto, existe o inteiro (r – ks) tal que a = d(r – ks) ? d | a (5) .
Conforme (2) e (5), d | a e d | b ? d | mdc(a, b) (6).
De (1) d é múltiplo do mdc(a, b) e de (6) d é divisor do mdc(a, b). Somente d é ao mesmo tempo múltiplo de divisor de d. Portando, d = mdc(a, b). Assim, d = mdc(a = kb, b) = mdc(a, b) ? mdc(a, b) = mdc(a + kb, b). Cqd.
28 – Dividindo-se dois inteiros positivos pelo seu mdc, a soma dos quocientes é 8. Determinar os dois inteiros, sabendo-se que sua soma é 384.
Solução: Sejam a e b os dois inteiros positivos e x e y os quocientes de a e b pelo mdc(a, b). Esses quocientes são primos entre si e positivos pois a e b são positivos e mdc(a, b) também é positivo. Temos então: x + y = a/(mdc(a, b) + b/mdc(a, b) = 8 ? a + b = 8.mdc(a, b) ? 384 = 8.mdc(a,b) ? mdc(a, b) = 48.
Como x + y = 8 e x e y são inteiros positivos e primos entre si, os únicos valores possíveis para o par (x, y) são (1, 7) e (3,5). Como a = x.mdc(a, b) e b = y.mdc(a, b) resulta: a = 48.1 = 48 e b = 48.7 = 336 ou a = 48.3 = 144 e b = 48.5 = 240.
Resposta: 48 e 336 ou 144 e 240.
29 – Os inteiros positivos m e n são tais que o mdc(m, n) = d. Mostrar que o mdc(2m – 1, 2n – 1) = 2d – 1.
Solução: Na divisão de polinômios temos que:
(2a – 1) = (2b – 1)(2a – b + 2a – 2b + 2a – 3b + ... + 2a – kb) + (2a – kb – 1) com k maior inteiro positivo tal que a – kb > 0. Se b | a então existe k, tal que a – kb = 0 pois a = kb.
Neste caso (2a – kb – 1) = 20 – 1 = 0 ? a divisão é exata. Portanto, a divisão é exata quando b|a.
Assim se d = mdc(m,n), 2m–1 é divisível por 2d–1 e 2n–1 é divisível por 2d–1.
Portanto 2d - 1 é um divisor comum de 2m – 1 e 2n – 1. Como d é o maior divisor comum de m e n, 2d – 1 é o maior divisor comum de 2m – 1 e 2n – 1 ? mdc(2m – 1, 2n – 1) = 2d – 1. Cqd
30 – Demonstrar que mdc(a, b) = mdc(a, b, a + b).
Solução: De acordo com o exercício nº 27, mdc(a, b) = mdc(a + kb, b), para todo inteiro k.
Como mdc(a + kb, b) = mdc(b, a + kb) temos mdc(a, b) = mdc(b, a + kb).
Fazendo k = 1, temos: mdc(a, b) = mdc(b, a + b)
Temos então que Mdc(a, b) = mdc(a, b, b) pois mdc(a, b, b) = mdc(a, mdc(b, b)).
Portanto, mdc(a, b) = mdc(a, b, b) = mdc(mdc(a,b), b) (definição do mdc de três ou mais números) = mdc(mdc(a, a + b), b) ) de acordo com o mostrado acima = mdc(a, a + b, b) (definição do mdc de três ou mais números) = mdc( a, b, a + b). Cqd.
31 – Demonstrar que mdc(a, b) = mdc(a, b, ax + by), quaisquer que seja os inteiros x e y.
Solução: Seja k, o inteiro tal que ax + by = k. Isto implica em k é múltiplo do mdc(a, b).
Seja d = mdc(a, b). Temos então k = ds, s inteiro, pois k é múltiplo de d.
Temos então que Mdc(a, b, dr) = mdc(mdc(a, b), dc)) = mdc(d, dr) = d pois dr é múltiplo de d.
Portanto, d = mdc(a, b) = mdc(a, b, ax + by). Cqd
32 – O mdc(a, b) = p, sendo p um primo. Achar os possíveis valores do
(a) mdc(a2, b).
Solução: Sejam a = p.a1.a2.a3 ...an, onde p, a1, a2, a3, ... an são os fatores primos de a e b = p.b1.b2.b3...bn, onde p, b1, b2, b3, ...bn são os fatores primos de b.
Assim, a2 = p.p.a1.a2.a2.a3a3...an.an ? que a2 e b são divisíveis ao mesmo tempo apenas por p ?
? mdc(a2, b) = p.
(b) mdc(a3, b) = p, mesma conclusão acima.
(c) mdc(a2, b3) = p2. Pois aparecem 2 fatores iguais a p em a2 e 3 fatores iguais a p em b3.
33 – Sabendo que o mdc(a, p2) = p e que o mdc(b, p3) = p2, onde p é um primo, calcular o mdc (ab, p4) e o mdc(a + b, p4).
Solução:
(i) Mdc(ab, p4). De acordo com o exercício anterior: De mdc(a, p2) = p, p primo, conclui-se que em a existe um p como fator primo e os demais diferentes de p.
De mdc(b, p3) = p2, p primo, conclui-se que em b existe dois fatores iguais a p e os demais diferentes de p. Portanto: em ab irão figurar 1 + 2 = 3 fatores iguais a p e os demais diferentes de p. Daí Conclui-se que mdc(ab, p4) = p3.
(ii)Mdc(a + b, p4). Seja a’ o produto dos fatores primos de a, excluído o p. Temos: a’ = kp + r (o < r < p), e b’ o produto dos fatores primos de b, excluído exluido um dos fatores iguais a p.
Portanto, b’ = kp pois b tem dois fatores iguais a p.
Somando membro a membro a’ + b’ = p(k + k’) + r ? a’ + b’ não é múltiplo de p.
Assim temos: a + b = pa’ + pb’ = p(a’ + b’) sendo a’ + b’ não múltiplo de p.
Portanto, a + b tem apenas um p como fator comum. Disto se conclui que mdc(a + b, p4 ) = p.
34 – Demonstrar que se o mdc(a, b) = d então o mdc(a2, b2) = d2.
Solução: Seja d = d1.d2.d3...dn, onde cada di é um fator primo de d.
Como d = mdc(a,b), os fatores primos de d são fatores de a e b e estes são os únicos fatores comuns.
Façamos então: a = d1.d2.d3...dn.a1.a2.a3 ...an, e b = d1.d2.d3...dn.b1.b2.b3...bn onde ai e bi são os fatores primos de a e b além dos di.
Em consequência temos: a2 = d1.d2.d3...dn.a1.a2.a3 ...an. d1.d2.d3...dn.a1.a2.a3 ...an e
b2 = d1.d2.d3...dn.b1.b2.b3...bn . d1.d2.d3...dn.b1.b2.b3...bn .
Como pode ser observado o produto dos fatores comuns de a2 e b2 e d1.d2.d3...dn. d1.d2.d3...dn = d.d = d2 ? Mdc(a2, b2) = d2. Cqd
35 – Sejam a e k inteiros não conjuntamente nulos. Demonstrar que mdc(a, a + k) | k.
Solução: Seja m o mdc(a, a + k). Assim, existem os inteiros x e y tais que: a = mx e a + k = my. Subtraindo primeira igualdade da segunda resulta: (a + k) – a = my – mx ? k = m(y – x). Como x e y são inteiros, y - x é inteiro. Portanto, existe o inteiro (y – x) tal que k = m(y – x) ? m | k ou mdc(a, a + k) | k. Cqd.
36 – Demonstrar que mdc(a, b) = mdc(a, c) implica mdc(a2, b2) = mdc(a2, c2).
Solução: Se mdc(a, b) = d então mdc(a2, b2) = d2, conforme demonstrado no exercício 34.
Se mdc(a, c) = d então mdc(a2, c2) = d2. Portanto: mdc(a2, b2) = mdc(a2, c2). Cqd.
37 – Demonstrar que mdc(a, b) = mdc(a, c) implica mdc(a, b) = mdc(a, b, c).
Solução: Mdc(a, b, c) = mdc(a, mdc(b, c)) = mdc(a, mdc(a,b)) = mdc(a, a, b) = mdc(a, b). Cqd.
38 – Demonstrar que mdc(a, b, c) = mdc(mdc(a, b), mdc(a, c).
Solução: Mdc(a, b, c) = mdc( a, a, b, c) pois mdc(a, a) = a.
Portanto, mdc (a, b, c) = mdc(a, a, b, c) = mdc (a, b, a, c) = mdc(mdc(a,b), mdc(a,c)). Cqd.
39 – Sejam a e b inteiros positivos tais que ab é um quadrado perfeito e o mdc(a, b) = 1. Demonstrar que a e b são quadrados perfeitos.
Solução: Os fatores primos de ab são os fatores primos de a e b.
Portanto, ab = a1.a2.a3 ...an. b1.b2.b3...bn . Como mdc(a, b) = 1, nenhum dos fatores de b é fator de a.
Se ab é um quadrado, a quantidade de cada fator primo deve ser par. Assim, cada fator de a aparece uma quantidade par de vezes, bem como cada fator de b. Portanto, a e b são são quadrados perfeitos. Cqd.
40 – Demonstrar que mdc( a + b, a – b) > mdc(a, b)
Solução: Seja d = mdc(a + b, a – b) ? existem os inteiros x e y tais que (a + b)x + (a – b)y = d ? a(x + y) + b(x – y) = d ? d é múltiplo do mdc(a, b). Se d é múltiplo do mdc(a, b) então d > mdc(a, b) ? mdc(a + b, a – b) > mdc(a, b). Cqd.
41 – Mostrar que o mdc(5n + 6, 5n + 8) = 1 onde n é um inteiro ímpar.
Solução:
- Se n é um inteiro ímpar, então
5n + 6 = 5(2k + 1) + 6 = 10k + 11 = 10(k + 1) + 1 = 10x + 1
5n + 8 = 5(2k + 1) + 8 = 10k + 13 = 10(k + 1) + 3 = 10x + 3
Calculando o mdc de 10k + 1 e 10x + 3 pelo processo das divisões sucessivas, temos:
(10x + 3) = (10x +1). 1 + 2
(10x + 1) = 2.5x + 1. Como o último resto é 1, resulta que mdc(5n + 5, 5n + 8) = 1. Cqd.
42 – Sejam a, b, c, d (b ? d) inteiros tais que mdc(a, b) = mdc(c, d) = 1. Mostrar que a soma a/b + c/d não é um inteiro.
Solução: (a/b + b/d) = (ad + bc)/bd será um inteiro se e somente se bd | (ad + bc).
bd | (ac + bc) ⇒ b | (ac + bd) e d | (ac + bd).
Se b | (ad + bc) teremos ad + bc = bk ad = b (k – c). Como k e c são inteiros, k – c é um inteiro. Assim, existe um inteiro (k – c) tal que ad = b(k – c) ⇒ b | ad. Como mdc(a, b) = 1 resulta b | d.
Se d | (ad + bc) teremos ad + bc = dk bc = d(k – a) ⇒ d | bc. Mas, mdc(d, c) = 1. Assim conclui-se d | b. Ora, é impossível ocorrer b | d e d | b pois d ≠ b, conforme enunciado.
Assim, (ad – bc) somente será divisível por bd se b = d, quando mdc(a, b) = 1 e mdc(c, d) = 1. Como essas condições não são são todas verificadas, (ad – bc) não é divisível por bd ⇒ (a/b + c/d) não é um inteiro. Cqd.
43 – Determinar os inteiros positivos a e b, sabendo que a2 – b2 = 7344 e mdc(a, b) = 12.
Solução: De mdc(a, b) = 12 resulta, existem os inteiros x e y tais que a = 12x e b = 12y.
Substituindo esses valores em a2 – b2 = 7344, temos: 144x2 – 144y2 = 7344 ⇒ x2 – y2 = 51 ⇒ (x – y)(x + y) = 51. Como x e y são inteiros, (x – y) e (x + y) também são inteiros. Ora, 51 admite, somente, os inteiros (1, 51) e (3, 17) cujos produtos sejam 51.
Portanto, (1) x – y = 1 e y + x = 51 ⇒ x = 26 e y = 25 ⇒ a = 12x = 12.26 = 312 e b = 12.25 = 300, ou (2) x – y = 3 e x + y = 17 ⇒ x = 10 e y = 7 ⇒ a = 12.10 = 120 e b = 12.7 = 84.
Resposta: (312, 300) ou (120, 84)
4 Comentários