Sejam a, b, c in Z. Prove que existem x, y, z in Z tal que
mdc(a, b, c)=x cdot a+y cdot b+z cdot c
Dica: Utilize o principio de boa ordem no conjunto
S=m cdot a+n cdot b+k cdot c mid m, n, k in Z e m cdot a+n cdot b+k cdot c>0
e prove que m d c(a, b, c)=min S

Passo 1

O enunciado pede para mostrar que, dados a,b,cinZ, existe uma combinação inteira
xcdot a + ycdot b + zcdot c
que é exatamente gcd(a,b,c).
O método sugerido usa o princípio da boa ordem no conjunto
S = ,m,a + n,b + k,c mid m,n,kinZ e m,a+n,b+k,c>0
A ideia é definir
d = min S
e provar que d é o máximo divisor comum de a,b,c, logo d=gcd(a,b,c) e já está escrito como combinação linear de a,b,c.

Passo 2

Primeiro, S é não-vazio. Se a=b=c=0, basta tomar x=y=z=0 e gcd(0,0,0)=0. Caso contrário, pelo menos um de a,b,c é não-nulo; sem perda de generalidade, digamos aneq0. Então, tomando m=sign(a) e n=k=0, temos
m,a + n,b + k,c = |a| > 0,
logo |a|in S. Pelo princípio da boa ordem, S tem um mínimo, que chamamos de
d = min S

Passo 3

Mostramos que d divide a. Aplique o algoritmo da divisão de inteiros para dividir a por d: existem q,rinZ com
a = q,d + r, 0 <= r < d
Reescrevendo
r = a - q,d = a - q,(m,a+n,b+k,c) = (1 - q,m),a ;+;(-q,n),b;+;(-q,k),c
Se r>0, então rin S mas r<d, contradizendo a minimalidade de d. Logo r=0 e dmid a.

Passo 4

De modo totalmente análogo, dividimos b por d e c por d, obtendo restos rb,rc>=0. A mesma argumentação força rb=rc=0. Portanto
d mid a, dmid b, dmid c,
ou seja, d é um divisor comum de a,b,c.

Passo 5

Finalmente, seja e qualquer outro divisor comum de a,b,c. Então emid a, emid b, emid c. Logo e divide toda combinação inteira m,a+n,b+k,c. Em particular, emid d. Assim todo divisor comum e satisfaz e<= d, o que mostra que d é o máximo divisor comum. Logo
d = gcd(a,b,c)
E como din S, existem inteiros x,y,z tais que
d = x,a + y,b + z,c

Resposta

Existem x,y,zinZ tais que
gcd(a,b,c) = x,a + y,b + z,c

Exercícios relacionados