0
$\begingroup$

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.

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

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)$.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.