Sejam d1=mdc(a, b1) e d2=mdc(a, b2). Prove que mdc(a, b1 b2)= =m d c(a, d1 d2).
Sugestão: Se ré um divisor qualquer de b1 b2, entāo r=r1 r2, onde r1 é divisor de b1 e r2 é divisor de b2 - o que é consequência do teorema fundamental da aritmética.

Passo 1

O enunciado define
d1 = gcd(a,b1), d2 = gcd(a,b2)
e pede para mostrar
gcdl(a,b1b2r) ;=;gcdl(a,d1d2r)
O conteúdo que vamos usar é o Teorema Fundamental da Aritmética, que diz que se um inteiro r divide o produto b1b2, então podemos fatorar r=r1r2 com r1mid b1 e r2mid b2, e também a propriedade de máximo divisor comum: o gcd é um divisor comum que “engloba” todos os outros, isto é, qualquer outro divisor comum divide o gcd.

Passo 2

Seja
g = gcdl(a,b1b2r)
Então gmid a e gmid b1b2. Pelo Teorema Fundamental da Aritmética, como gmid b1b2 podemos escrever
g = r1,r2,
com r1mid b1 e r2mid b2.

Passo 3

Além disso gmid a implica r1mid a e r2mid a. Mas
d1 = gcd(a,b1)
é o maior divisor comum de a e b1, logo r1mid d1. Analogamente r2mid d2. Portanto
g = r1r2 ;m|; d1d2
Como também gmid a, concluímos que g é divisor comum de a e d1d2. Pela definição de gcd, isso força
g ;m|;gcdl(a,d1d2r)

Passo 4

Agora seja
h = gcdl(a,d1d2r)
Então hmid a e hmid d1d2. De novo, pelo Teorema Fundamental da Aritmética, como hmid d1d2 podemos escrever
h = u,v,
com umid d1 e vmid d2.
Mas d1mid b1 e d2mid b2, então umid b1 e vmid b2. Como também hmid a, segue que h é divisor comum de a e b1b2. Novamente pela definição de gcd, isso implica
h ;m|;gcdl(a,b1b2r)

Resposta

Juntando os dois resultados, temos
gcdl(a,b1b2r) ;m|;gcdl(a,d1d2r) e gcdl(a,d1d2r);m|;gcdl(a,b1b2r),
logo os dois números são iguais. Portanto
boxedgcdl(a,b1b2r) ;=;gcdl(a,d1d2r)

Exercícios de Livros Relacionados