reducing a fraction/greatest common factor

[dbaryl]

I have the following way to find the GCF (greatest common factor) for two numbers, but I'm a little confused about the logic behind it. This is more of a math question if any, but...

Given 2 positive numbers p and q:

1. Store remainder of q divided by p into r.
2. While r is not 0:
__a. Copy p into q and r into p.
__b. Store remainder of q divided by p into r.
3. p is the GCF.

Lemme try that in code (should work...):

#include <stdio.h>

int find_gcf(int p, int q);

int main (void)
{
  int p, q, gcf;

  printf("Enter p:");
  scanf("%d", &p);
  printf("Enter q:");
  scanf("%d", &q);

  gcf = find_gcf(p, q);

  printf("GCF of %d and %d is %d.", p, q, gcf);

  return (0);
}


int find_gcf(int p, int q)
{
  int r;

  r = q % p;

  while (r)
  {
    q = p;
    p = r;
    r = q % p;
  }
  return(p);
}

Now, what I understand out of this... according to some logic, if there's no remainder after the division, the denomenator is the GCF, that makes sense. Also, I'm trying to make sure that this is correct:

if there's some whole number answer as well a remainder, both of these should be divisible by the GCF. This is because the numerator is initially divisible by GCF, if we subtract some integer multiple of the GCF from it (which is what the whole # answer is), the remainder is still divisible by GCF.

We can now look at the remainder and the denomenator, which are two smaller numbers then previously, but still divisible by GCF. By repeating this procedure (thus the while loop), we should be able to reach a point when there's no remainder...

I don't know, it kinda makes sense to me, but still a bit fuzzy. Does anyone have a better explanation, or better yet, a better and more efficient way to find the GCF of 2 numbers through code?

[Nick]

The proof of the gcd algorithm is well known.
p = q * n + r
Any divisor of p and q also divides r since p - q*n = r and any divisor of q and r is a divisor of p. Therefore since the set of all common divisors of p and q equals the set of all divisors of q and r, the greatest common divisor is the same.
gcd(p, q) = gcd(q, r).

You can probably find a better proof at web site.

[Shiro]

Maybe the recursive definition gives more insight:

gcd (x, y) = 
    x, y = 0 
    gcd (y, x mod y), y > 0

It is obvious that if y = 0, then x is the greatest common divisor.

If y is larger than 0, then check if y is a divisor of x. If not, which is for example when x is smaller then y, then x mod y = x. Now in the next step y and x will be swapped. And then it will be checked if x is a divisor of y. If not, then there must be a smaller number divisor of both x and y. This process goes on until the first divisor is found. This divisor, let's call it c, has property that x mod c = 0, so the end-step of the recursion is reached.