Thread: reducing a fraction/greatest common factor

  1. #1
    back? dbaryl's Avatar
    Join Date
    Oct 2001

    reducing a fraction/greatest common factor

    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;
    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?
    This is my signature. Remind me to change it.

  2. #2
    Join Date
    Aug 2001
    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.

  3. #3
    Join Date
    Aug 2001
    Groningen (NL)
    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.
    Last edited by Shiro; 07-21-2002 at 03:11 PM.

Popular pages Recent additions subscribe to a feed

Similar Threads

  1. C program for finding highest common factor!!
    By visham in forum C Programming
    Replies: 11
    Last Post: 08-02-2007, 07:10 AM
  2. Greatest Common Factor
    By cppdungeon in forum C++ Programming
    Replies: 5
    Last Post: 11-28-2005, 11:06 AM
  3. Binary Search Trees Part III
    By Prelude in forum A Brief History of
    Replies: 16
    Last Post: 10-02-2004, 03:00 PM
  4. Lowest Common Factor
    By PJYelton in forum C++ Programming
    Replies: 9
    Last Post: 12-23-2002, 09:30 AM
  5. Greatest Common Factor problem
    By Unregistered in forum C++ Programming
    Replies: 2
    Last Post: 10-08-2001, 03:29 PM