Question

(Lema de Euclides) Sejam x e y dois números inteiros em que x é não nulo. Mostre que mdc(x,y) = mdc(x,x-y)

Answer 1

Denote por d o divisor de x e y. Se d = 4, então necessariamente x e y deverão ser múltiplos de 4. Assim, a soma e a subtração de ambos, resultará em um múltiplo de d.

Exemplos:

$*$ É fácil ver que 84 e 35 são múltiplos de 7. Então 84 + 35 = 119 e 84 - 35 = 49 são múltiplos de 7.

$*$ O número $d=4$ é um divisor de $x = 20$ e de $y = 48$, pois $20 = 4 \cdot 5$ e $48 = 4 \cdot 12$. Daí $d = 4$ é um divisor de $y - x = 28$, pois $y - x = (4 \cdot 12) - (4 \cdot 5) = 4 \cdot (12 - 5) = 4 \cdot 7$.

$*$ Sabe-se que x e y - x são múltiplos de d. Como y = x + (y - x) é uma soma de múltiplos de d, segue que b também é um múltiplo de d.

Observe o cálculo do mdc(18, 60) com essa propriedade.

$mdc( 18, 60) = mdc( 18, 60 - 18) = mdc( 18, 42) =\\ mdc( 18, 42) = mdc( 18, 42 - 18) = mdc( 18, 24) =\\ mdc( 18, 24) = mdc( 18, 24 - 18) = mdc( 18, 6) = 6.$

Veja que paramos ao chegar no 6, pois se subtrairmos 18 - 6 por 3 vezes encontramos 6 novamente. Resumindo, quando chegamos a um número que ao ser dividido pelo maior tenha como resto o número 0, este é o mdc desejado. 

Espero ter ajudado!!!
Bons estudos!!!