Sejam a e b dois números naturais não ambos nulos e c um terceiro número natural não nulo. Mostre que mdc(c × a, c × b) = c × mdc(a, b)

temos que:

d = mdc (ac,bc) => d | r * (ac) + s * (bc)

                          => d | ac + bc

                          => d | c * (a+b)

                          =>(d/c) | a + b

temos agora que:

d/c = mdc (a,b) => d = c* mdc (a,b)

No cálculo do MDC dos números naturais aa e bb, não precisamos nos preocupar quando a condição a>b>0a>b>0 não for satisfeita, uma vez que:

(i)  mdc(0,0)   (i)  mdc(0,0) não está definido;
(ii)  mdc(n,n)=n   (ii)  mdc(n,n)=n, para qualquer natural não nulo nn;
(iii)  mdc(m,n)=mdc(n,m)   (iii)  mdc(m,n)=mdc(n,m), para quaisquer números naturais não ambos nulos mm e nn;
(iv)  mdc(n,0)=n   (iv)  mdc(n,0)=n, para qualquer número natural não nulo nn.

O máximo divisor comum entre dois números naturais não nulos e distintos é igual ao máximo divisor entre o menor e o resto da divisão do maior pelo menor. Em símbolos, se x e y são números naturais tais que \( x>y>0\) , e se

então \(mdc(x,y)=mdc(y,r)mdc(x,y)=mdc(y,r)\)

Pelo até agora exposto, para calcularmos o MDC de dois números naturais aa e b b  tais que a>b>0a>b>0, fazemos a divisão euclidiana de aa por b b :

com 0≤r1≤b0≤r1≤b.

Se o resto dessa divisão for zero, então mdc(a,b)=mdc(b,0)=bmdc(a,b)=mdc(b,0)=b e acabou o problema. (veja (iv)(iv))
Caso o resto r1r1 seja diferente de zero, então mdc(a,b)=mdc(b,r1)mdc(a,b)=mdc(b,r1) e passamos a nos preocupar agora com o MDC de bb e r1r1.

Observe que, se nas nossas divisões obtivermos um resto rn+1rn+1 igual a zero, o processo termina pois
mdc(a,b)=mdc(b,r1)=mdc(r1,r2)=mdc(r2,r3)=⋯=mdc(rn−1,rn)=mdc(rn,rn+1)=mdc(rn,0)=rn

Portanto, se não encontrarmos um resto zero, obteremos uma sequência decrescente de infinitos números naturais não nulos, todos menores do que b:

b>r1>r2>r3>r4>⋯>0      b>r1>r2>r3>r4>⋯>0

o que não é possível, pois sabemos que existem apenas b−1b−1 números naturais não nulos que são menores do que bb.

Fonte: http://clubes.obmep.org.br/blog/sala-de-estudos-algoritmo-de-euclides-para-determinacao-de-mdc/