In the book of Silverman, the below proof is given of the above :

$$a= q_1b + r_1$$ $$b =q_2 r_1+ r_2$$ $$r_1 =q_3r_2 + r_3$$ $$\vdots$$ $$r_{n-3} = q_{n-1}r_{n-2} + r_{n-1}$$ $$r_{n-2} = q_n r_{n-1} + r_n$$ $$r_{n-1} = q_{n+1}r_n + 0$$

But why is $r_n$ the greatest common divisor of $a$ and $b$? Suppose that $d$ is any common divisor of $a$ and $b$. We will work our way back down the list of equations. So from the first equation $a = q_1b + r_1$ and the fact that $d$ divides both $a$ and $b$, we see that $d$ also divides $r_1$. Then the second equation $b = q_i + r_2$ shows us $d$ must divide $r_2$. Continuing down line by line, at each stage we will know $d$ divides the previous two remainders $r_{i-1}$ and $r_i$, and then the current line $r_{i-1} = q_{i+1}r_i+ r_{i +1}$ will tell us that $d$ also divides the next remainder $r_{i + 1}$. Eventually, we reach the penultimate line $r_{n-2} = q_nr_{n-1} + r_n$, at which point we conclude that $d$ divides $r_n$. So we have shown that if $d$ is any common divisor of $a$ and $b$, then $d$ will divide $r_n$. Therefore, $r_n$ must be the greatest common divisor of $a$ and $b$.

I take the above proof to an example, say $b = 32, a=33*8=264, r_n= gcd(a,b)= 8, d= 4$. Now, $a=32*8 + r_1$, with $b=32, q=8, r_1=8, d=4\mid r_n=4$. Similarly, the argument can continue on.

But, it appears unconvincing to me from the very start. May be a contradiction based proof would have worked better, by taking the prime factorization of $a,b$, and showing that a non-common divisor would not divide at any step at least two of the three terms.

Or may this approach is not proper itself.

  • 1
    $\begingroup$ What exactly “appears unconvincing ... from the very start” ? $\endgroup$ – Martin R Mar 29 '18 at 9:08
  • 2
    $\begingroup$ You omitted one step, namely that if you work from the bottom up, you can see that $r_n$ itself divides both $a$ and $b$, so it is a common divisor. After that you then work from top to bottom as described to show that every common divisor $d$ divides $r_n$. Therefore $r_n$ is the greatest of such common divisors. $\endgroup$ – Jaap Scherphuis Mar 29 '18 at 9:16
  • $\begingroup$ @MartinR Sorry, for being late. It appears that it is not rigorous. It is not a formal one, and cannot be convinced (at least to me) to be of that type. $\endgroup$ – jiten Mar 29 '18 at 9:27
  • 1
    $\begingroup$ That is too vague. You demonstrated that if $d$ is any common divisor of $a$ and $b$ then $d$ divides $r_n$. Please explain what you consider “not rigorous” in the proof. $\endgroup$ – Martin R Mar 29 '18 at 9:32
  • 1
    $\begingroup$ There's a typo in your post: $r_{n-i}$ should be $r_{n-1}$. $\endgroup$ – Bernard Mar 29 '18 at 10:08

DEFINITION: Let $a,b \in \mathbb Z$. Then $g \in \mathbb Z^+$ is the greatest common divisor of $a$ and $b$ if

$\qquad \text{$(1.) \quad g \mid a$ and $g \mid b$}$.

$\qquad \text{$(2.) \quad \forall x \in \mathbb Z, \ x\mid a$ and $x \mid b$ implies $x \mid g$}$.

Now, suppose $x \mid a$ and $x \mid b$. Then

\begin{array}{rcl} a= q_1b + r_1 &\implies &x \mid r_1 \\ b =q_2 r_1+ r_2 &\implies &x \mid r_2 \\ r_1 =q_3r_2 + r_3 &\implies &x \mid r_3 \\ &\vdots \\ r_{n-3} = q_{n-1}r_{n-2} + r_{n-1} &\implies &x \mid r_{n-1} \\ r_{n-2} = q_n r_{n-1} + r_n &\implies &x \mid r_n \\ \end{array}

So $r_n$ satisfies condition $(2.)$.

In the other direction.

\begin{array}{rcl} r_{n-1} = q_{n+1}r_n + 0 &\implies &r_n \mid r_{n-1} \\ r_{n-2} = q_n r_{n-1} + r_n &\implies &r_n \mid r_{n-2} \\ r_{n-3} = q_{n-1}r_{n-2} + r_{n-1} &\implies &r_n \mid r_{n-3} \\ &\vdots \\ r_1 =q_3r_2 + r_3 &\implies &r_n \mid r_1 \\ b =q_2 r_1+ r_2 &\implies &r_n \mid b \\ a= q_1b + r_1 &\implies &r_n \mid a \\ \end{array}

So $r_n$ satisfies conditions $(1.)$. Hence $r_n=\gcd(a,b)$

  • $\begingroup$ Basically it is elaboration of the comment of @JaapScherphuis to the OP, and might be (not clear) also incorporates the comment of 'dssknj' (for the 'other direction' part). $\endgroup$ – jiten Mar 29 '18 at 11:14
  • $\begingroup$ It also makes me feel that there is no 'more' formal proof possible. I attempted a wrong way in response to @dssknj, and feel something like that is not possible. Can you please comment on that. $\endgroup$ – jiten Mar 29 '18 at 11:15
  • $\begingroup$ Thanks a lot for your kindest elaboration that makes the book more clear, but still my earlier doubts (as in the previous two comments) are not escaping me. $\endgroup$ – jiten Mar 29 '18 at 11:35
  • 1
    $\begingroup$ Yes, I did nothing but make the others comments look "prettier". I also cannot see how to do a contradiction-based proof. In your question you proved that $r_n$ is a common divisor {(1.)}. It seemed to me that you couldn't "see" how to show that it was the **greatest ** common divisor {(2.)}. So I just formalized everything in my answer. $\endgroup$ – steven gregory Mar 29 '18 at 11:36
  • 1
    $\begingroup$ I think you just need to stop thinking about symbols for a while and get out a pencil and some paper and play with some numbers. Try reducing these fractions for example: $\dfrac{12}{15}, \quad \dfrac{74}{111}, \quad \dfrac{123}{173}$. $\endgroup$ – steven gregory Mar 29 '18 at 12:12

Here is a slightly different proof that $r_n$ is the greatest common divisor, based more on what @dssknj remarked (still not by contradiction though).

Lemma: $\gcd(x,y)=gcd(x,y+rx)$ for any integers $x,y,r$.

If $d|x$ and $d|y$ then clearly $d|y+rx$. So every common divisor of $x$ and $y$ is also a common divisor of $x$ and $y+rx$.
The converse is also true:
If $d|x$ and $d|y+rx$ then $d|y$ because $y=(y+rx)-rx$. So every common divisor of $x$ and $y+rx$ is also a common divisor of $x$ and $y$.

This means that $\{x,y\}$ have exactly the same common divisors as $\{x,y+rx\}$, and therefore will also have the same greatest common divisor. $\square$

You can now traverse the sequence of equations once in either direction to show that $$ \gcd(a,b) = \gcd(b,r_1) = \gcd(r_1,r_2) = \gcd(r_2,r_3) = ...\\ ... = \gcd(r_{n-2},r_{n-1}) = \gcd(r_{n-1},r_n) = \gcd(r_n,0) = r_n$$

Basically, instead of traversing the sequence of equations once in each direction, this proof builds a two-way connection between adjacent entries, and then you only have to go through the sequence once in either direction to fully prove the connection we want between the first and last.

  • $\begingroup$ How your answer incorporated @dssknj comment in the proof to show the dowinwards and upwards movement in the iterative runs of Euclidean algorithm, is not 'clear'. By 'clear'', I mean that the neccesity of incorporating his comment is not separate, but arising out of the need to prove that $r_n$ is $\gcd(a,b)$. May be 'dssknj' comment is not concerned with showing $r_n$ is the greatest common divisor, but with just showing that $r_n=\gcd(a,b)$. $\endgroup$ – jiten Mar 29 '18 at 12:09
  • 2
    $\begingroup$ @jiten "not concerned with showing $r_n$ is the greatest common divisor, but with just showing that $r_n$ is the $\gcd(a,b)$." Huh? It is not concerned with showing that but it is concerned with showing just that? $\endgroup$ – Jaap Scherphuis Mar 29 '18 at 12:14
  • $\begingroup$ I like this answer better than mine. $\endgroup$ – steven gregory Mar 29 '18 at 14:28

If you want it by contradiction then here it is...

1) $a=bq+r$ then any common divisor of $a$ and $b$ is common divisor of $b$ and $r$.

Using 1) it is easy to show that $r_n$ is a common divisor of $a$ and $b$. Let assume that $r_n\neq \gcd(a, b)$ then $\gcd(a, b)=d, d\gt r_n$ $\quad d$ is a common factor of $a$ and $b$ and using 1) we have $d\mid r_n \implies d\le r_n$ Hence contradiction.

  • $\begingroup$ You are using a proven result (that $\gcd$ is the biggest common divisor) to derive that $d\gt r_n$, which seems unfair to me. Please do not take this result for granted, which itself means that a proof derived using some other way was better to prove the topic of the post. $\endgroup$ – jiten Mar 29 '18 at 21:39
  • $\begingroup$ what is your definition of gcd if it is not the greatest common divisor? $\endgroup$ – Siong Thye Goh Mar 29 '18 at 23:00
  • 1
    $\begingroup$ @jiten definitions are things that don't need proof and you can't prove them by the way. $\endgroup$ – dssknj Mar 30 '18 at 2:03
  • 1
    $\begingroup$ @jiten not axiom its definition. You may have proven in your high school that perpendicular drawn from center to chord bisect the chord. In proving that you must have used the fact that end points of chord lie on the circle which is the definition of chord. $\endgroup$ – dssknj Mar 30 '18 at 2:22
  • 1
    $\begingroup$ My personal opinion: We define things, and then we verify whether it is well defined (i.e. some sort of check that whether two people can always compute the same quantity). ... and then we derived its properties ...If the same term is defined by two people, we check whether they mean the same thing. If one is not allowed to use its definition.... there is no reason why you can trust the properties derived from it. And we dont' even know what we are trying to prove if there isn't a definition to check. I am not a logician to comment such thing precisely though. $\endgroup$ – Siong Thye Goh Mar 30 '18 at 5:57

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.