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
    The greatest common divisor of $12$ and $6$ is $6$.2012-03-07
  • 0
    take a look at http://en.wikipedia.org/wiki/File:Euclid%27s_algorithm_Book_VII_Proposition_2_3.png to see why the euclidean algorithm works. You cant start out by dividing the smaller of the two with the larger.2012-03-07
  • 0
    @user996522: You can begin either way; you just have to know what you’re doing.2012-03-07
  • 2
    Given two (say positive, though that can be relaxed) positive integers $a \leq b,$ we set $r_{-1} = a, r_0 = b$ and we define $r_{n+1}$ inductively via $r_{n} = q_{n}r_{n-1} + r_{n+1},$ where $0 \leq r_{n+1} < r_{n-1}$ and $q_{n}$ is an integer. On the first occasion when $r_{n+1} =0,$ we have $r_{n-1} = {\rm gcd}(a,b).$ The real gcd is $6$ in your case. Remember that the gcd must divide both integers you start with2012-03-07
  • 0
    You might find this link helpful: http://www.math.sc.edu/~sumner/numbertheory/euclidean/euclidean.html You can enter 2 numbers and the page runs the extended Euclidean algorithm showing all of the intermediate steps.2012-03-07
  • 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
    Will I avoid all further troubles, using $gcd(a,b)$ and impose b>a?2012-03-07
  • 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