# Suck on proving factoring part of Euclid's GCD problem

I am trying to understand why Elucid's GCD algorithm works given two integers $a$ and $b$

$$gcd(a,b) = gcd(q \cdot b +r, b)\\\ q = \frac{a}{b} \;\; \text{where q is the quotient} \\ r = a \bmod b \;\; \text{where r is the remainder} \\ x = \text{is a common factor between a and b} \\ x \shortmid a \; \& \Rightarrow x \shortmid (q \cdot b) \; \& \; x \shortmid r$$ I know for sure that x divides $(q \cdot b)$ because q is an integer scalar, but how can I prove that x must also be a factor of r? I believe that this is the critical part of the proof that I can't understand.

I am following along this video of the proof on youtube if you need to reference that specific part that I am stuck on.

• I like your pun in the title: Suck on proving... instead of saying Stuck on proving... – Toby Mak Jul 1 '17 at 7:08

If $x$ divides both $a$ and $b$ (and hence also divides $\gcd(a,b)$), then it also divides $a-b$, $a-2b$, $a-3b$, and so on, all the way to $r=a-qb$, which means $x$ divides $\gcd(r,b)$.
If $x$ divides both $r$ and $b$, i.e. $x$ divides $\gcd(r,b)$, then it also divides $a=r+qb$.
So any number that divides $\gcd(a,b)$ also divides $\gcd(r,b)$, and vice versa, which (because $\gcd$'s are positive) means we must have $\gcd(a,b)=\gcd(r,b)$.