Lema de Euclides

Como $a$ y $b$ son primos relativos, por la identidad de Bezout, existe una $x_0$ e $y_0$ tales que $ax_0 + by_0 =1$. Multipliquemos esta identidad por $c$ y se obtiene que

Evidentemente $a| ca$ y por consiguiente

$a|cax_0 \ldots$ (1)

Por hipótesis, $a | cb$ en consecuencia

$a | cby_0 \ldots$ (2)

Entonces, por (1)  y (2) se tiene que:

$a |cax_0 + cby_0 = c$

Y queda demotrado lo deseado.