The Quotient-Remainder Theorem and Euclid's Algorithm

Theorem 3.4.1 The Quotient-Remainder Theorem
Given any integer n and positive integer d, there exist unique integers q and r such that

n = dq + r and 0 < r < d.

If you divide one number, n, by another, d, you get a quotient, q, and a remainder, r, and that the remainder is less than the divisor, d. For the cases where r = 0 we say d divides n or d | n. Here we call d a divisor of n or a factor of n. Symbolically

d | n iff $ k Î Z such that n = k·d.

 To recover the quotient using integer division use n div d in Pascal; n / d in C, C++, Java, and Ada. To recover the remainder using integer division use n mod d in Pascal; n % d in C, C++, and Java; n rem d in Ada. div is short for "divided by" and mod is short for "modulo". In Java when division is performed using two integers the result is the integer quotient (n / d = q). When modulo is performed on two integers the result is the remainder (n % d = r). In order to not perform integer division in Java one must cast one of the integers to a real or use a real literal as one of the operands. Consider these two assignments using the Java convention

1. ans1 = 5 / 10 * 2;

2. ans2 = (double) 5 / 10 * 2

The solution to the first problem is 0 while the solution to the second is 1.0.

What is the Greatest Common Divisor, GCD, of two numbers? It's just the largest number that divides both numbers exactly, leaving no remainder. For example, the divisors of 4 = {1, 2, 4} and the divisors of 12 = {1, 2, 3, 4, 6, 12}, so the GCD of 4 and 12 is the largest number to appear on both lists: 4. In the same way, you can check to see that the GCD of 36 and 210 is 6, and that the GCD of 15 and 4 is 1.

Euclid's Division Algorithm: To find the GCD of two numbers, divide one of them into the other, and note that the GCD will also exactly divide the remainder. For example, 210 = 5*36 + 30 the GCD of 210 and 36 is 6, and 6 does divide 30 exactly (30 = 5*6). Now divide the old remainder into the old divisor, and the GCD of the old divisor and the old remainder will exactly divide the new remainder. Keep doing this, until you get a remainder of 0. The last nonzero remainder you get will be the GCD of the two numbers you started with.

How is this so? First note that gcd(n, d) = gcd(d, r). So the problem of finding the GCD of n and d comes down to finding the GCD of d and r after dividing n by d to get r.

Here is a simple iterative solution to finding the greatest common divisor of two integers in Java.

class Calculate
{
   public static int gcd(int a, int b) //one, or both, of a and b is nonnegative
    {
        int n, d, r;
        d = b;
        r = a % b;

        while(r > 0)
        {
            n = d;
            d = r;
            r = n % d;
        }//while

        return d;
    }// gcd(int, int)
}// Calculate