4
$\begingroup$

I am not understanding how the following formular works

http://en.wikipedia.org/wiki/Greatest_common_divisor#Using_Euclid.27s_algorithm

Actually what I did (for my programming homework was loop through the max of 2 numbers until I get 1 that divides both given numbers without a remainder). Bruteforce, so not ideal. So I want to understand more about this formular instead of just using it.

public static int gcd(int a, int b) {
  /**
   * Get max of both numbers
   * Loop down max number and test if its divisible by both numbers
   * if yes, thats the answer, else continue
   * if no answer, return 0
   */
  int max = Math.max(a, b);
  for (int i = max; i > 0; i--) {
    if (a % i == 0 && b % i ==0) {
      return i;
    }
  }
  return 0;
}
  • 0
    Note that the comment says exactly what the loop does. (`a % i` takes the remainder after dividing `a` by `i`.)2011-08-23
  • 1
    Note that the [Euclidean algorithm article on Wikipedia](http://en.wikipedia.org/wiki/Euclidean_algorithm) gives a few better implementations...2011-08-23
  • 0
    @J.M. I am new to this site and not a maths person so I'm not sure what other tags should I put. I know the formula works. I know % or mod is the remainder. But I do not understand why after recursively dividing the quotient with the remainder (of the prev iteration) will give the gcd of 2 numbers. Hope you get what I mean2011-08-23
  • 0
    I will take a look at the article soon, gtg to next lesson2011-08-23
  • 0
    After peering closely at the code... you could have started with the *minimum* instead of the maximum; $a$ can't be divisible by $b$ is $b$ is bigger, no? The "Description" portion of the wiki-article explains Euclid's idea.2011-08-23
  • 0
    @J. M.:As Implementation I always find `int gcd(int a int b){return b?gcd(b,a%b):a;}` to be fairly simple and smooth :-)2011-08-23
  • 0
    @Fool: yes, if the environment supports recursion. If not, then some elaboration is necessary...2011-08-23
  • 0
    @jiewmeng:There is nothing much to understand unless you meant to a formal proof,it is the same old way we are taught to do find H.C.F or G.C.D since elementary.2011-08-23
  • 0
    @J.M:Umm..do you know about any *modern* environment that do not support recursion?2011-08-23
  • 0
    With the adjective *modern* @Fool, I can't think of any. On the other hand, people do still write for legacy systems... but we are already off-topic here.2011-08-23
  • 0
    Isn't it just pure brute-force, hardly an algo. then in terms of efficiency.2017-12-02

4 Answers 4

3

The basic idea is this: if you want gcd($a$, $b$) and $a>b$, then we can instead compute gcd($b, a \bmod b$) and we've made progress. It's progress because when $a>b$, we know $a \bmod b$ is smaller than $b$, it's a remainder after all. And if we make positive inputs smaller and smaller, eventually we must terminate.

The real question is this: why is gcd($a$, $b$) the same as gcd($b, a \bmod b$)?

Well, let's answer an easier question. Instead of trying to wrap your head around $a \bmod b$, let's restate the problem. Why is gcd($a$, $b$) the same as gcd($b, a-b$)? This question is almost the same, but we're using minus instead of mod because it's easier to understand when this stuff is new to you. And mod is just a repeated application of minus anyway, right?

So let's prove the "easier" version. Well, if some divisor $d$ goes evenly into $a$ and $b$, then it must go into their difference $a-b$, right? To be more mathematical, if $a = kd$ and $b=jd$, then $a-b = kd-jd = (k-j)d$ and clearly $d$ goes evenly into $(k-j)d$. Also, if $d$ goes evenly into $(a-b)$ then any $d$ dividing $a$ must divide $b$, so we're done.

If this still isn't clear, draw a number line and convince yourself that two multiples of 3 (for example) are always a multiple of 3 apart. Then convince yourself that any multiple of 3 plus a multiple of 3 must also be a multiple of 3.

Then try it for numbers other than 3.

  • 0
    One needs *both* directions: if $d|a$ then $d|b\ \iff\ d|a-b$2011-08-23
  • 0
    @Bill Dubuque: Thanks, Bill. I was trying to stay informal, but I shouldn't sacrifice such an essential part of the justification. Fixed.2011-08-23
  • 0
    Simplest explanation across SE for this.2017-12-02
2

$a{\rm\ mod\ }b$ is the remainder when you divide $a$ by $b$, so we can say two things about it: it is $a-bq$ for some integer $q$, and it is between $0$ and $b-1$, inclusive.

I want to show $\gcd(a,b)=\gcd(b,a{\rm\ mod\ }b)$.

Let $d=\gcd(a,b)$. Then $d$ divides both $a$ and $b$. So it divides both $a-bq$ and $b$. So it divides $\gcd(b,a{\rm\ mod\ }b)$.

Conversely, let $e=\gcd(b,a{\rm\ mod\ }b)$. Then $e$ divides both $b$ and $a-bq$. So it divides both $a$ and $b$. so it divides $\gcd(a,b)$, and we are done.

Now the only question remaining about the formula is why it always gives an answer, that is, why it can't just keep going forever. Well, supposing $a\gt b$, and comparing $\gcd(a,b)$ and $\gcd(b,a{\rm\ mod\ }b)$, we've decreased both arguments (that is, replacing $a$ with $b$, and replacing $b$ with $a{\rm\ mod\ }b$, we've replaced both with things that are smaller). The way the (positive) integers work, that can't go on forever. It has to stop sometime. But the only way it can stop is when $b=0$ (since if $b\gt0$ you can always keep going), and then $\gcd(a,0)=a$ kicks in.

2

If $\rm\:d\:|\:b\:$ then $\rm\:d\:|\:a\: \iff\: d\ |\ a-n\:b\:.\:$ Thus $\rm\ a,b\ $ and $\rm\ a-n\:b,\:b\ $ have the same common divisors, therefore the same greatest common divisor. Finally $\rm\ a-n\:b\ =\ a\ mod\ b\ $ for some $\rm\:n\in \mathbb Z\:.$

0

It all rests on one simple fact. If $b = aq + r$ and $b, q, a, r\in \mathbb{Z}$, then $\gcd(a,b) = \gcd(a,r)$. Just show that an integer divides $a$ and $b$ iff it divides $a$ and $r$ and you are done.