1
$\begingroup$

Stpid question, I know, but I need to understand. As far as I know $\gcd(12, 6)$ is equal to $\gcd(6, 12)$. But, if I use extended euclidean algorithm I get: $\gcd(12, 6)\quad 12/6=2\quad12\%6=0$ While if I swap the two integers: $\gcd(6,12)\quad 6/12=0\quad 6\%12=6$ next step $12/6=2\quad 12\%6=0$

So, in first case the one and only remainder that I get is $0$ (there is no remainders first of null remainder). In the second place, first of null remainder there is $6$! What's the real $\gcd(12,6)$?

  • 0
    You've got the same bottom-line answer either way: the gcd is $6$.2012-03-07

2 Answers 2

7

When you apply the Euclidean algorithm to $a$ and $b$, $\gcd(a,b)$ is the last non-zero remainder. If you begin by dividing $12$ into $6$, your steps are:

$\begin{align*} 6&=12\cdot 0+6\\ 6&=6\cdot 1+0\;. \end{align*}$

The last non-zero remainder is $6$, and indeed $\gcd(6,12)=6$. If you begin the other way round, your only step is

$12=6\cdot 2+0\;.$

You might think that there is no non-zero remainder here, but you have to remember that the divisor at each step is the remainder from the previous step. Thus, the divisor of $6$ should be thought of here as being the remainder from a virtual previous step, so that we have a non-zero remainder. Thus, once again the last non-zero remainder is $6=\gcd(12,6)$.

0

this is not correct step, $\gcd(a,b)$ and $\gcd(b,a)$ are equal, but method that you described is not correct. Imagine that in one case $a but in other $b>a$ so if you do so next time,you would be in trouble again.

  • 0
    you should know that,while proof gcd(a,b)=gcd(b,a), no one try to proof is by compare results,which you described in your question2012-03-07