máximo divisor comum

Prévia do material em texto

6
M¶aximo divisor comum
6.1 Conceitua»c~ao e propriedades elementares
Se x e a s~ao inteiros, com a6= 0, e x j a (lembre-se de que \x j a" signi¯ca \x divide
a") ent~ao jxj · jaj. De fato, como a = xc, para algum inteiro c, e c6= 0 (pois a6= 0),
temos jcj ¸ 1, e portanto
jxj · jxjjcj = jxcj = jaj
Como jxj · jaj , ¡jaj · x · jaj, se a 6= 0, o conjunto D(a), dos inteiros
divisores de a, ¶e limitado superiormente por jaj (e inferiormente por ¡jaj).
Se a = 0, ent~ao D(a) = D(0) = Z, pois cada inteiro ¶e divisor de zero.
Agora, dados dois inteiros a e b, com a6= 0 ou b6= 0, existe pelo menos um divisor
comum de a e b, a saber, 1, j¶a que 1 j a e 1 j b. Al¶em disso, se x 2 Z ¶e um divisor
comum de ambos a e b ent~ao, pela observa»c~ao acima, jxj · jaj (se a6= 0) ou jxj · jbj
(se b6= 0).
Assim sendo, o conjunto dos divisores comuns de a e b, D(a) \D(b), ¶e limitado
superiormente pelo maior dos inteiros jaj e jbj, e portanto possui um m¶aximo d, sendo
d ¸ 1, j¶a que 1 j a e 1 j b. A este inteiro d chamamos m¶aximo divisor comum de a e b.
De¯ni»c~ao 6.1 Dados dois inteiros a e b, com a 6= 0, ou b 6= 0, chama-se m¶aximo
divisor comum de a e b, ao inteiro d, denotado por mdc(a; b), elemento m¶aximo do
conjunto D(a; b) = D(a) \D(b). Se a = b = 0, de¯nimos mdc(a; b) = mdc(0; 0) = 0
(muito embora n~ao exista o maior inteiro positivo divisor de 0).
Equivalentemente, mdc(a; b) ¶e o inteiro d ¸ 0 satisfazendo:
1. d = 0, se a = b = 0;
2. se a6= 0 ou b6= 0, d ¶e caracterizado pelas seguintes duas propriedades:
(i) d j a e d j b;
46
M¶aximo divisor comum 47
(ii) Para cada x 2 Z, se x j a e x j b ent~ao x · d.
Exemplo 6.1 mdc(12; 28) = 4, pois
D(12) = f¡12;¡6;¡4;¡3;¡2;¡1; 1; 2; 3; 4; 6; 12g, e
D(28) = f¡28;¡14;¡7;¡4;¡2;¡1; 1; 2; 4; 7; 14; 28g
Assim, D(12; 28) = D(12) \ D(28) = f¡4;¡3;¡2;¡1; 1; 2; 3; 4g, que tem m¶aximo
igual a 4, que ¶e o m¶aximo divisor comum de 12 e 28.
Os divisores comuns de 28 e 84 s~ao §1;§2;§3;§4;§6; e §12. Portanto,
mdc(24; 84) = 12. Analogamente, olhando os conjuntos de divisores comuns, con-
clu¶³mos que mdc(35; 45) = 5, mdc(17; 25) = 1, mdc(0;¡8) = 8 e mdc(¡9;¡15) = 3.
Proposi»c~ao 6.1 Sendo a e b inteiros quaisquer,
1. mdc(a; 0) = jaj;
2. mdc(a; b) = mdc(jaj; jbj);
3. mdc(a; b) = mdc(b; a).
Demonstra»c~ao. A demonstra»c~ao dos itens 2 e 3 ¶e imediata, j¶a que, para todo x 2 Z,
x j a e x j b, x j b e x j a, x j jaj e x j jbj
e assim
D(a; b) = D(b; a) = D(jaj; jbj)
Demonstra»c~ao do item 1.
Se a = 0, mdc(a; 0) = mdc(0; 0) = 0 = jaj.
Se a6= 0, jaj divide a. Tamb¶em jaj divide 0.
Agora, para cada x 2 Z, se x j a e x j 0, ent~ao x divide jaj, logo x · jaj.
Logo, pela de¯ni»c~ao de mdc, jaj = d = mdc(a; 0).
6.2 O algoritmo euclidiano para o c¶alculo do mdc
Estabeleceremos agora um algoritmo para o c¶alculo de mdc(a; b), no caso em que a e
b s~ao inteiros ambos n~ao nulos, realizado atrav¶es de uma seqÄue^ncia ¯nita de divis~oes
euclidianas. Antes de enunci¶a-lo ilustr¶a-lo-emos atrav¶es de um exemplo.
Considere o problema de calcular mdc(91; 35).
Come»camos fazendo
M¶aximo divisor comum 48
91 35
21 2
Consideramos ent~ao o divisor 35 e o resto 21 dessa primeira divis~ao e efetuamos
a divis~ao Euclidiana de 35 por 21.
35 21
14 1
Agora repetimos o processo iniciado acima, isto ¶e, tomamos, na pr¶oxima divis~ao,
21 como dividendo e 14 como divisor:
21 14
7 1
Finalmente, chegamos µa divis~ao exata
14 7
0 2
Tendo chegado a um resto igual a zero, o algoritmo termina. O ¶ultimo resto n~ao
nulo, das divis~oes sucessivas realizadas, ¶e o mdc procurado, ou seja, mdc(91; 35) = 7.
Estaremos justi¯cando este algoritmo no teorema 6.1.
Lema 6.1 Sejam a e b dois inteiros, com b6= 0, e seja r o resto da divis~ao Euclidiana
de a por b. Ent~ao mdc(a; b) = mdc(b; r).
Demonstra»c~ao. Para demonstrar o resultado enunciado no lema, ¶e su¯ciente provar que
todo divisor de a e b ¶e tamb¶em divisor de b e r, e reciprocamente. Assim sendo, o maior
divisor de a e b coincidir¶a com o maior divisor de b e r. Note que esse \maior divisor"
existe, j¶a que b6= 0.
Temos, por hip¶otese, a = bq + r, logo r = a¡ bq.
Seja x um inteiro divisor de a e b. Ent~ao
x j a e x j b) x j (a¡ qb)) x j r
Logo, x j b e x j r. Logo, D(a; b) ½ D(b; r).
Agora, seja x um inteiro divisor de b e r. Ent~ao
x j b e x j r) x j (qb+ r)) x j a
Logo, x j b e x j a. Logo, D(b; r) ½ D(a; b).
Portanto,D(a; b) = D(b; r), e assim sendo,mdc(a; b) =maxD(a; b) = maxD(b; r)
= mdc(b; r).
M¶aximo divisor comum 49
Lema 6.2 Sejam a e b inteiros ambos positivos com a ¸ b e de¯namos uma seqÄue^ncia
de inteiros n~ao negativos da seguinte forma:
² r1 = a;
² r2 = b;
² Para cada ¶³ndice k, com k ¸ 2, se rk 6= 0, rk+1 ¶e o resto da divis~ao Euclidiana de
rk¡1 por rk:
rk¡1 rk
rk+1 ¤
e se rk = 0, a seqÄue^ncia termina em rk. Ent~ao a seqÄue^ncia r1; r2; : : : ¶e ¯nita e termina
em um zero, ou seja, existe um indice n tal que r1 ¸ r2 > : : : > rn > 0 e rn+1 = 0.
Demonstra»c~ao. Por hip¶otese, r1 ¸ r2 e, pela de¯ni»c~ao de rk+1, para k ¸ 2 temos
rk+1 < rk.
Considere o conjunto de n¶umeros naturais S = fr1; r2; : : : g.
Como S ½ N e S6= ¿, pelo princ¶³pio da boa ordena»c~ao dos n¶umeros naturais, S
possui um m¶³nimo, o qual denotaremos por rn+1.
Pelo que foi observado acima, teremos r1 ¸ r2 > ¢ ¢ ¢ > rn > rn+1.
A¯rmamos que rn+1 = 0. Para justi¯car isto, basta observar que se rn+1 6= 0
ent~ao podemos de¯nir rn+2 2 S como sendo o resto da divis~ao de rn por rn+1. Teremos
ent~ao 0 · rn+2 < rn+1, contrariando o fato de rn+1 ser m¶³nimo de S.
Teorema 6.1 (Algoritmo euclidiano para o c¶alculo do mdc) Sejam a e b inteiros
ambos positivos, com a ¸ b, e seja
r1; r2; : : : ; rn; rn+1
a seqÄue^ncia de¯nida pelo lema 6.2, sendo
r1 ¸ r2 > : : : > rn > rn+1 = 0
Ent~ao rn = mdc(a; b).
Demonstra»c~ao. Para cada k ¸ 3, rk ¶e o resto da divis~ao de rk¡2 por rk¡1. Pelo lema
6.1,
mdc(rk; rk¡1) = mdc(rk¡1; rk¡2)
M¶aximo divisor comum 50
Logo
rn = mdc(0; rn)
= mdc(rn+1; rn) (pois rn+1 = 0)
= mdc(rn; rn¡1) (pelo lema 1)
= : : :
= mdc(r3; r2)
= mdc(r2; r1)
= mdc(a; b)
6.3 O mdc(a; b) caracterizado como combina»c~ao linear
dos inteiros a e b
O seguinte teorema, um teorema n~ao intuitivo de nossa introdu»c~ao µa aritm¶etica dos
inteiros, nos d¶a uma segunda e importante caracteriza»c~ao do m¶aximo divisor comum.
Teorema 6.2 O m¶aximo divisor comum de dois inteiros a e b, a 6= 0 ou b 6= 0, ¶e a
menor combina»c~ao linear positiva de a e b, com coe¯cientes inteiros, ou melhor, ¶e o
menor inteiro positivo da forma ma+ nb com m e n inteiros.
Em outras palavras, se a6= 0 ou b6= 0, ent~ao
mdc(a; b) = minfx 2 Z j x > 0 e x = ma+ nb; com m;n 2 Zg
Demonstra»c~ao. Seja d = ma + nb o menor inteiro positivo que ¶e combina»c~ao linear de
a e b, com coe¯cientes inteiros.
A existe^ncia de d ¶e garantida pelo principio da boa ordena»c~ao dos inteiros positivos
(existe uma combina»c~ao linear de a e b que ¶e positiva: basta considerar jaj + jbj =
(§1)a+ (§1)b).
Vamos mostrar que d j a e d j b. Pelo algoritmo da divis~ao podemos escrever
a = dq + r, para certos inteiros q e r, com 0 · r < d.
Logo r = a ¡ dq = a ¡ q(ma + nb) = (1 ¡ qm)a ¡ (qn)b, e portanto r ¶e uma
combina»c~ao linear de a e b.
Como 0 · r < d e d ¶e o menor inteiro positivo que ¶e uma combina»c~ao linear de
a e b, conclu¶³mos que r = 0 e que portanto d j a.
Analogamente, podemos demonstrar que d j b.
Para mostrar que d ¶e o m¶aximo divisor comum de a e b precisamos mostrar que
qualquer divisor comum c de a e b ¶e menor que ou igual a d.
M¶aximo divisor comum 51
Como d = ma+ nb, se c j a e c j b, tem-se imediatamente que c j d, e portanto,
c · d.
Corol¶ario 6.1 Se a e b s~ao inteiros e d = mdc(a; b), ent~ao existem inteiros r e s tais
que d = ra+ sb.
De¯ni»c~ao 6.2 Dois inteiros a e bs~ao primos entre si ou relativamente primos se
mdc(a; b) = 1.
Corol¶ario 6.2 Sendo a e b dois inteiros, a e b s~ao primos entre si se e somente se
existem inteiros r e s satisfazendo ra+ sb = 1.
Demonstra»c~ao.
()): Se mdc(a; b) = 1 ent~ao, pelo corol¶ario 6.1, existem inteiros r e s tais que
ra+ sb = 1.
((): Reciprocamente, se ra+sb = 1, ent~ao a6= 0 ou b6= 0 e, al¶em disso, 1 ¶e a menor
combina»c~ao linear positiva de a e b, com coe¯cientes inteiros. Pelo teorema 6.2,
mdc(a; b) = 1.
Alternativamente, temos tamb¶em a seguinte demonstra»c~ao. Sendo ra + sb = 1,
se x j a e x j b ent~ao x j (ra + sb), e assim x j 1. Logo, x · 1. Portanto
1 = mdc(a; b).
Corol¶ario 6.3 Sejam a, b e c inteiros, com a6= 0 ou b6= 0, e mdc(a; b) = d. Ent~ao
a=d e b=d s~ao inteiros primos entre si, ou seja, mdc
¡
a
d
; b
d
¢
= 1.
Demonstra»c~ao. Sendo mdc(a; b) = d, temos que d j a, d j b e existem inteiros r e s
tais que ra+ sb = d. Logo, r(a=d) + s(b=d) = 1, e portanto os inteiros a=d e b=d s~ao
primos entre si.
A propriedade rec¶³proca ¶e tamb¶em facilmente deduzida, e ser¶a deixada para o
leitor.
Corol¶ario 6.4 Sejam a; b 2 Z e d = mdc(a; b). Sejam
A = fx 2 Z j x = ma+ nb; com m;n 2 Zg; e
M = fy 2 Z j y = ¸d; com ¸ 2 Zg:
Ent~ao A =M , isto ¶e, as combina»c~oes lineares ma+ nb, com m e n inteiros, coincidem
com os inteiros m¶ultiplos de mdc(a; b).
M¶aximo divisor comum 52
Demonstra»c~ao. Se a = b = 0, temos d = 0 e A =M = f0g. Suponhamos ent~ao a6= 0
ou b6= 0. Para provar que A =M , provaremos que A ½M e M ½ A.
(i) A ½M :
Seja x um elemento de A.
x 2 A) x = ma+ nb, para certos inteiros m e n.
Sendo d = mdc(a; b), temos que
d j a e d j b ) d j (ma+ nb) ) d j x ) x = ¸d, para algum inteiro ¸.
Portanto, x 2M .
(ii) M ½ A:
Seja y um elemento de M .
y 2M ) y = ¸d, para algum inteiro ¸.
Pelo teorema 6.2, d = ra+ sb, para certos inteiros r; s.
Logo, y = ¸d = ¸(ra+ sb) = (¸r)a+ (¸s)b.
Portanto, y 2 A.
Por (i) e (ii), temos A =M .
Corol¶ario 6.5 (Caracteriza»c~ao alternativa do mdc) Sendo a e b dois inteiros dados,
temos:
d = mdc(a; b),
8<
:
(1) d ¸ 0
(2) d j a e d j b
(3) para todo x 2 Z; se x j a e x j b ent~ao x j d
Demonstra»c~ao.
()): Note que (1) e (2) j¶a s~ao propriedades estabelecidas do mdc. Assim s¶o nos resta
demonstrar que d = mdc(a; b) satisfaz µa condi»c~ao (3).
Pelo teorema 6.2, d = ra+ sb para certos inteiros r e s. Logo, para cada x 2 Z,
se x j a e x j b ent~ao x j (ra+ sb), logo x j d.
((): Suponhamos que a = b = 0, e que d ¶e um inteiro satisfazendo as condi»c~oes (1),
(2) e (3).
Por (3), todo inteiro x que divide a e b deve tamb¶em dividir d. Agora, x = 0
divide a e b, logo divide d.
Mas 0 j d, d = 0. Logo, pela de¯ni»c~ao 6.1, d = 0 = mdc(a; b).
Suponhamos agora a6= 0 ou b6= 0, e que d ¶e um inteiro satisfazendo as condi»c~oes
(1), (2) e (3). Por (2), d j a e d j b. Por (1) e (2), d > 0.
M¶aximo divisor comum 53
Por (3), se x ¶e um inteiro tal que x j a e x j b, ent~ao, x j d. Logo, como d > 0,
x · d.
Portanto, conforme a de¯ni»c~ao 6.1, d = mdc(a; b).
Podemos ter inteiros a, b e c tais que a j bc, mas a6j b e a6j c. Por exemplo,
6 j (4 ¢ 15), mas 66j 4 e 66j 15.
No entanto, h¶a uma circunsta^ncia particular em que podemos garantir que se a
divide bc ent~ao a divide um dos fatores b e c.
Proposi»c~ao 6.2 Dados inteiros a, b e c, se a j bc, e a e b s~ao primos entre si, ent~ao
a j c.
Demonstra»c~ao. Como a e b s~ao primos entre si, ra+ sb = 1 para certos inteiros r e s.
Logo, rac+ sbc = c.
Agora, a j (rac) e a j (sbc) (pois a j bc). Logo a j (rac+ sbc), e portanto a j c.
Proposi»c~ao 6.3 Sejam a e p inteiros, sendo p um n¶umero primo positivo. Ent~ao a n~ao
¶e divis¶³vel por p se e somente se a e p s~ao primos entre si.
Demonstra»c~ao.
()) Sejam a e p como no enunciado da proposi»c~ao, suponhamos que p6j a, e seja d
= mdc(a; p). Ent~ao d > 0, d j a e d j p. Como p ¶e primo, temos que d = 1 ou
d = p. Mas p6j a e d j a, logo d = 1, e portanto a e b s~ao primos entre si.
(() Suponhamos agora que a e p s~ao primos entre si, ou seja mdc(a; p) = 1. Como
p j p, se tamb¶em p j a, ent~ao mdc(a; b) ¸ p ¸ 2, e temos uma contradi»c~ao.
Portanto p6j a.
Proposi»c~ao 6.4 Sejam a, b e p inteiros, com p primo. Se p j ab ent~ao p j a ou
p j b (podendo ser fator de ambos, a e b).
Demonstra»c~ao. Temos que p j a ou p6j a.
Se p6j a, ent~ao, pela proposi»c~ao anterior, p e a s~ao relativamente primos. Como
p j ab, pela proposi»c~ao 6.2, temos que p j b.
6.4 Calculando inteiros r e s tais que
mdc(a; b) = ra + sb.
Veremos agora como o algoritmo euclidiano, do c¶alculo do mdc de dois inteiros, pode
ser usado para obtermos o mdc como uma combina»c~ao linear desses inteiros.
M¶aximo divisor comum 54
Vimos acima que mdc(91; 35) = 7. Para expressar 7 como combina»c~ao linear de
91 e 35, consideramos as divis~oes euclidianas usadas no c¶alculo de mdc(91; 35),
91 35
21 2
35 21
14 1
21 14
7 1
14 7
0 2
Lembremo-nos de que ¶ultimo resto n~ao nulo, das divis~oes sucessivas realizadas, ¶e o mdc
procurado.
As tre^s primeiras divis~oes estabelecem
91 = 35 ¢ 2 + 21
35 = 21 + 14
21 = 14 ¢ 1 + 7
E ent~ao, isolando os restos, temos
21 = 91¡ 35 ¢ 2
14 = 35¡ 21 ¢ 1
7 = 21¡ 14 ¢ 1
de onde ent~ao obtemos, passo a passo, cada um dos tre^s restos como combina»c~ao linear
de 91 e 35:
21 = 91¡ 35 ¢ 2, conforme j¶a estabelecido.
14 = 35¡ 21 ¢ 1
= 35¡ (91¡ 35 ¢ 2)
= (¡1) ¢ 91 + 3 ¢ 35
e ¯nalmente
7 = 21¡ 14 ¢ 1
= (91¡ 35 ¢ 2)¡ [(¡1) ¢ 91 + 3 ¢ 35] ¢ 1
= 2 ¢ 91 + (¡5) ¢ 35
ou seja,
7 = 2 ¢ 91 + (¡5) ¢ 35
obtendo-se assim 7 = mdc(91; 35) como combina»c~ao linear r ¢ 91 + s ¢ 35, com r e s
inteiros.
Teorema 6.3 Sejam a e b inteiros ambos positivos com a ¸ b, e considere a seqÄue^ncia
de¯nida no lema 6.2, r1; r2; : : : ; rn; rn+1, em que r1 = a, r2 = b, rn = d = mdc(a; b) e
rn+1 = 0. Ent~ao cada rk, para 1 · k · n, pode ser escrito como combina»c~ao linear de
a e b.
M¶aximo divisor comum 55
Demonstra»c~ao. Pelo modo como a seqÄue^ncia ¶e formada,
r1 = r2q2 + r3
r2 = r3q3 + r4
...
rn¡2 = rn¡1qn¡1 + rn
rn¡1 = rnqn:
Da¶³,
r3 = r1 ¡ r2q2
r4 = r2 ¡ r3q3
...
rn = rn¡2 ¡ rn¡1qn¡1
Temos que r1 = a e r2 = b s~ao combina»c~oes lineares de a e b. Logo, r3 =
r1 ¡ r2q2 = a¡ bq2 tamb¶em ¶e combina»c~ao linear de a e b.
E supondo que rk¡1 e rk, k ¸ 2, sejam combina»c~oes lineares de a e b, deduzimos
que
rk+1 = rk¡1 ¡ rkqk
ser¶a tamb¶em combina»c~ao linear de a e b. Assim, cada rk (1 · k · n) ¶e combina»c~ao
linear de a e b.
6.5 O mdc de tre^s ou mais inteiros
De¯ni»c~ao 6.3 Seja a1; a2; : : : ; an uma cole»c~ao ¯nita de inteiros, n~ao todos nulos. O
m¶aximo divisor comum dessa cole»c~ao ¶e o maior inteiro d que divide simultaneamente
todos os inteiros da cole»c~ao, e ser¶a denotado por mdc(a1; a2; : : : ; an).
Se a1; a2; : : : ; an s~ao todos zeros, de¯nimos mdc(a1; a2; : : : ; an) = 0.
Por exemplo, mdc(12; 18;¡30) = 6 e mdc(10;¡15; 25) = 5.
Proposi»c~ao 6.5 Se a1; a2; : : : ; an ¶e uma cole»c~ao ¯nita de inteiros, n~ao todos nulos,
ent~ao
mdc(a1; a2; : : : ; an¡1; an) = mdc(a1; a2; : : : ; an¡2;mdc(an¡1; an)
Demonstra»c~ao. Qualquer divisor comum dos inteiros a1; a2; : : : ; an ¶e, em particular,
um divisor de an¡1 e an, e portanto um divisor comum dos inteiros a1; a2; : : : ; an¡2,
mdc(an¡1; an).
M¶aximo divisor comum 56
Reciprocamente, todo divisor comum de a1, a2, : : : , an¡2, e mdc(an¡1; an), ¶e um
divisor comum dos inteiros a1; a2; : : : ; an, pois para dividir mdc(an¡1; an) ter¶a neces-
sariamente que dividir an¡1 e an. Como as duas cole»c~oes possuem o mesmo conjunto
de divisores comuns, conclui-se a proposi»c~ao.
Por exemplo,
mdc(405; 225; 75) = mdc(405;mdc(225; 75)) = mdc(405; 25) = 5:
De¯ni»c~ao 6.4 Dizemos que os inteiros a1; a2; : : : ;an s~ao primos entre si se
mdc(a1; a2; : : : ; an) = 1. Dizemos que os inteiros a1; a2; : : : ; an s~ao dois a dois primos
entre si, quando ai e aj s~ao primos entre si para cada par de inteiros ai e aj.
Exemplo 6.2 Considere os inteiros 10, 12 e 15. Como
mdc(10; 12; 15) = mdc(10;mdc(12; 15)) = mdc(10; 3) = 1
vemos que esses inteiros s~ao primos entre si. Contudo, os tre^s inteiros n~ao s~ao dois a
dois primos entre si, pois mdc(10; 12) = 2, mdc(12; 15) = 3 e mdc(10; 15) = 5.
6.6 Exerc¶³cios
1. Encontre o m¶aximo divisor comum de cada par de inteiros dados.
(a) 15, 35; (b) 0, 111; (c) -12, 18; (d) -25, -100.
2. Sejam a e n inteiros positivos. Determine o m¶aximo divisor comum de
(a) a e na (b) a e an (c) a e a+ n.
3. Mostre que se a, b e c s~ao inteiros positivos, ent~ao mdc(ac; bc) = c ¢mdc(a; b).
Sugest~ao. Chame d = mdc(a; b). Lembre-se de que existem inteiros r e s tais que
d = ra + sb. Ent~ao cd = r(ac) + s(bc). Da¶³, se x j ac e x j bc (x 2 Z), tem-se
ent~ao que x j cd. O resto ¶e por sua conta.
4. Mostre que se a e b s~ao inteiros primos entre si, ent~ao mdc(a+ b; a¡ b) = 1 ou
2. Sugest~ao. Mostre que se d j (a+ b) e d j (a¡ b) ent~ao d j 2a e d j 2b. Agora,
estude o caso em que d ¶e par, e depois o caso em que d ¶e ¶³mpar.
5. Mostre que se a e b s~ao primos entre si, ent~ao tamb¶em s~ao primos entre si os
seguintes pares de inteiros:
(a) a e b2 (b) a e bn (n 2 N) (c) an e bm (m;n 2 N)
Sugest~ao. Sendo a e b primos entre si, ra + sb = 1 para certos inteiros r e s.
Fa»ca sb = 1¡ ra e eleve ambos os membros ao mesmo expoente.
6. Mostre que se a e b s~ao inteiros primos entre si, ent~ao mdc(a2 + b2; a + b) = 1
ou 2.
Sugest~ao. Se d divide a2+b2 e tamb¶em a+b, ent~ao d divide (a¡b)(a+b)+a2+b2.
Agora, h¶a duas possibilidades: (i) d ¶e par; (ii) d ¶e ¶³mpar.
M¶aximo divisor comum 57
7. Mostre que se a e b s~ao ambos inteiros pares, n~ao ambos nulos, ent~ao mdc(a; b) =
2mdc(a=2; b=2).
8. Demonstre que se a, b e c s~ao inteiros tais que a j c e b j c, com a e b primos
entre si, ent~ao ab j c.
Sugest~ao. Temos ra + sb = 1, para certos inteiros r e s. Logo, rac + sbc = c.
Al¶em disso, como a j c e b j c, existem x; y 2 Z tais que c = ax e c = by. Na
combina»c~ao linear rac+ sbc, troque o primeiro c por by, e o segundo por ax.
9. Demonstre que se a, b e c s~ao inteiros tais que mdc(a; b) = mdc(a; c) = 1, ent~ao
mdc(a; bc) = 1. Sugest~ao. Existem inteiros r; s;m e n tais que ra + sb = 1, e
ma+ nc = 1. Multiplique as igualdades, membro a membro.
10. Encontre o m¶aximo divisor comum de cada um dos seguintes conjuntos de inteiros
dados.
(a) 6, 15, 21 (b) -7, 28, -35 (c) 0, 0, 1001
11. Mostre que se k ¶e um inteiro, ent~ao os inteiros 6k ¡ 1, 6k + 1, 6k + 2, 6k + 3, e
6k + 5 s~ao 2 a 2 primos entre si.
12. Mostre que se k ¶e um inteiro positivo, ent~ao 3k + 2 e 5k + 3 s~ao primos entre si.
13. Use o algoritmo euclidiano para encontrar
(a) mdc(45; 75) (b) mdc(666; 1414)
(c) mdc(102; 222) (d) mdc(20785; 44350)
14. Para cada par de inteiros do problema anterior, expresse o m¶aximo divisor comum
do par de inteiros como combina»c~ao linear desses inteiros.
15. Para cada cole»c~ao de inteiros dada abaixo, expresse o m¶aximo divisor comum como
uma combina»c~ao linear dos inteiros da cole»c~ao.
(a) 6; 10; 15 (b) 70; 98; 105
16. Seja a0; a1; a2; a3; : : : , uma seqÄue^ncia in¯nita de inteiros, com a0 = 0, satisfazendo
a seguinte propriedade:
mdc(am; an) = mdc(an; ar) sempre que n6= 0 e a divis~ao euclidiana de m por n
deixa resto r.
Mostre que, para quaisquer dois ¶³ndices m e n, sendo d = mdc(m;n), temos
mdc(am; an) = ad = amdc(m;n).
Sugest~ao. Considere o algoritmo euclidiano para o c¶alculo de mdc(m;n) e imite o
procedimento usado na demonstra»c~ao do teorema 6.1.
17. Sejam m e n dois inteiros positivos e seja a um inteiro maior que um. Mostre
que, sendo d = mdc(m;n), tem-se mdc(am ¡ 1; an ¡ 1) = ad ¡ 1.
Sugest~ao. Mostre que se a divis~ao de m por n deixa resto r, ent~ao todo divisor de
am ¡ 1 e an ¡ 1 ¶e tamb¶em divisor de an ¡ 1 e ar ¡ 1, e vice-versa. Use ent~ao o
resultado do exerc¶³cio 16.
M¶aximo divisor comum 58
18. Mostre que se a e b s~ao inteiros tais que ma+ nb = ¡26 para certos inteiros m
e n ent~ao mdc(a; b) 2 f1; 2; 13; 26g.
19. Descreva, como m¶ultiplos de um ¶unico inteiro, os elementos do conjunto
(a) A = f12m+ 18n j m;n 2 Zg
(b) B = f24m+ 18n+ 30p j m;n; p 2 Zg
20. Mostre que existem in¯nitos pares de inteiros (r; s) satisfazendo
r ¢ 2 + s ¢ 3 = mdc(2; 3) = 1
Sugest~ao. Mostre que a equa»c~ao
x ¢ 2 + y ¢ 3 = 0 (6.1)
tem um n¶umero in¯nito de solu»c~oes. Determine uma solu»c~ao da equa»c~ao
r ¢ 2 + s ¢ 3 = 1 (6.2)
Mostre ent~ao que os pares de inteiros da forma (x + r; y + s), sendo (x; y) uma
solu»c~ao de 6.1, e (r; s) a solu»c~ao encontrada de 6.2, s~ao tamb¶em solu»c~oes de 6.2.
21. Mostre que se m e n s~ao inteiros primos entre si, ent~ao existem inteiros x e y tais
que
1
mn
=
x
m
+
y
n
A partir deste fato, justi¯que o seguinte argumento:
Sendo m e n inteiros positivos primos entre si, se uma circunfere^ncia pode ser
dividida, com o uso de r¶egua e compasso, em m arcos congruentes, e tamb¶em em
n arcos congruentes, ent~ao ela tamb¶em pode ser dividida, com r¶egua e compasso,
em mn arcos congruentes.