Can you please explain to the last step of this proof of the euclidean algorithm? This is the proof of the euclidean algorithm my CS professor taught us last lecture:
For $a\gt b: \gcd(a,b) = \gcd(a-b,b)$
Let $g=\gcd(a,b), g'=\gcd(a-b,b)$
Then: 
$a=q_a \cdot g$ and $a-b = q'_\left(a-b\right) \cdot g'$
$b=q_b \cdot g $ and $b = q'_b \cdot g'$
$a-b=\left(q_a-q_b\right) \cdot g$ and $a =\left(q'_\left(a-b\right)-q'_b\right)\cdot g'$
That means:
$g$ divides $a-b,b$ and $g'$ divides $a,b$
Thus: $g \le g'$ and $g' \le g$ $\Rightarrow g = g' $
I don't understand how to arrive from "$g$ divides $a-b,b$ and $g'$ divides $a,b$" to "$g \le g'$ and $g' \le g$". Can you please explain that to me?
 A: This goes back to the formal definition of gcd.  In words, the formal definition says that if $d=\gcd(a,b)$, then $d$ is a divisor of both $a$ and $b$, and any other number that is a divisor of $a$ and $b$ is less than or equal to $d$.  (That is, to be pedantic, that $d$ is the greatest of all of the common divisors of $a$ and $b$.)
What your professor showed is that $g$ is a common divisor of $a-b$ and $b$, but they already defined $g'$ to be the greatest common divisor of those two numbers.  Therefore, $g\leq g'$.  At the same time, $g'$ was a common divisor of $a$ and $b$, but $g=\gcd(a,b)$, so $g'\leq g$.
A: Perhaps the same proof with a different twist helps:
If $d$ is any common divisor of $a$ and $b$, then $d$ is also a divisor of $a-b$ (for if $a=rd$ and $b=sd$, then $a-b=(r-s)d$). The same goes in the other direction, i.e., the set of common divisors of $a$ and $b$ is the same as the set of common divisors of $a-b$ and $b$. Therefore also the greatest elements of these equal sets are equal.
