Greatest common divisor


Adding fractions

In elementary school, I learned how to add fractions. Let's take a look, shall we?

\[ \frac{1}{2} + \frac{1}{3} \]

First, I need the denominators to match, so I multiply the numerator and denominator of each fraction with the opposing denominator.

\[ \frac{1 \times 3}{2 \times 3} + \frac{1 \times 2}{3 \times 2} \]
\[ \frac{3}{6} + \frac{2}{6} \]

Now that both denominators match, I can combine the fractions and add the numerators.

\[ \frac{3 + 2}{6} \]
\[ \frac{5}{6} \]

That's simple enough. I'll try another one.

\[ \frac{1}{2} + \frac{1}{6} \]

I need the denominators to match. And I see if I multiply the left fraction by 3, I can make them match. So I proceed as before.

\[ \frac{1 \times 3}{2 \times 3} + \frac{1}{6} \]
\[ \frac{3}{6} + \frac{1}{6} \]
\[ \frac{3+1}{6} \]
\[ \frac{4}{6} \]

Now, the answer is true, but it can be simplified. I can factor out a 2 from the numerator and denominator.

\[ \frac{2 \times 2}{3 \times 2} \]
\[ \frac{2 \times \cancel{2}}{3 \times \cancel{2}} \]
\[ \frac{2}{3} \]

Perfecto! I factor out a 2 because \( \gcd(4, 6) = 2 \). I'll try one more with variables, so I can see beyond the numbers and get a recipe for understanding.

\[ \frac{a}{b} + \frac{c}{d} \]
\[ \frac{a \times d}{b \times d} + \frac{c \times b}{d \times b} \]
\[ \frac{a d + c b}{d b} \]

That works, and in algebra, that's where I should stop. But I do another step when I know the numbers which is to simplify the fraction. I find and cancel out the greatest common divisor as follows.

\[ \frac{(a d + c b)/C}{(d b)/C} \]
\[ C = \gcd(a d + c b, d b) \]
This answer is more complicated, but more clearly shows that when I cancel out, I am dividing the numerator and denominator by a common value.

Calculating the GCD by hand

Let's build up the meaning of the GCD, one word at a time.

divisor
factor (synonym)
An integer which exactly divides another without remainder.
common divisor
A divisor or factor in common between two integers.
greatest common divisor
The largest possible divisor in common between two numbers.

Suppose I want to find \( \gcd(a, b) \) with \( a \le b \). GCD by trial division: a rudimentary approach would be to test division downward from the smaller value \( a \) until I find a common divisor. I know I have found the common divisor when the remainder is 0 for both divisions.

\[ \left \{ \frac{a}{a} , \frac{b}{a} \right \} \]
\[ \left \{ \frac{a}{a-1} , \frac{b}{a-1} \right \} \]
\[ ... \]
\[ \text{ decrement denominators until remainders are 0, to give } \]
\[ \left \{ \frac{a}{\gcd(a,b)} , \frac{b}{\gcd(a,b)} \right \} \text{ when both divisions are integers } \]

GCD by subtraction: Clearly, the rudimentary approach will work, but I may be doing far more work than necessary. Now, if a and b are equal, I would be done at the first step, so \( \gcd(a, b) = a \). If not, let's say C is a common divisor, I can write the following.

\[ a = A C \]
\[ b = B C \]
\[ b - a = A C - B C \]
\[ b - a = (A - B) C \]

So all the common divisors of a and b must also be a divisor of \( b - a \). This means that the greatest common divisor must also divide \( b - a \). It is easy to show likewise that this new number has no new common divisors with either a nor b separately. With that, I can write this equivalence.

\[ \gcd(a, b) = \gcd(a, b - a) \]

I can repeat this process with a little care.

\[ a_0 = \min(a, b) \]
\[ b_0 = \max(a, b) \]
\[ \gcd(a, b) = \gcd(a_0, b_0) = \gcd(a_1, b_1) = ... \]
\[ a_{i+1} = \min ( a_i , b_i - a_i ) \]
\[ b_{i+1} = \max ( a_i , b_i - a_i ) \]
\[ a_n = b_n \implies \gcd(a, b) = a_n \]

GCD by division: in the subtraction method, it's easy to see I am whittling down the problem, and will eventually arrive at a stopping point. The subtraction method is great! I do not have to do any trial divisions, and I approach the GCD in larger steps. That being said, I approach the GCD from the larger number, rather than the smaller, which is an advantage of the rudimentary approach. Also, another inefficiency becomes apparent. Suppose one term is much smaller than the other. For example, \( 9 a_0 \ge b_0 \gt 10 a_0 \). Then I have the following.

\[ a_0 = a_1 = a_2 = ... = a_8 \]
\[ 8 a_1 \ge b_1 \gt 9 a_1 \]
\[ 7 a_2 \ge b_2 \gt 8 a_2 \]
\[ ... \]
\[ a_8 \ge b_8 \gt 2 a_8 \]
\[ b_8 = b_0 - 8 a_0 \]

Finally, the smaller value becomes the larger.

\[ a_9 = b_0 - 9 a_0 \]
\[ b_9 = a_0 \]

I can create a new method which skips to this turning point each time. For that I simply do a trial division of a into b. If the remainder is 0, then \( \gcd(a, b) = a \). If the remainder is r > 0, then \( b_1 = a \) and \( a_1 = r \). This successive division and remainder approach is commonly called the Euclidean algorithm.

GCD calculator

With N serial divisions, I may calculate:

GCD.
Calculator code

Relationship to least common multiple

A value closely related to the GCD is the least common multiple, or LCM for short. It represents the smallest value which is a multiple of the numbers in question. To find this, firstly I observe that \( A B \) is a common multiple of A and B. But the least common multiple could be smaller.

\[ a = A \gcd(a, b) \]
\[ b = B \gcd(a, b) \]
\[ a b = A B (\gcd(a, b))^2 \]
\[ \frac{a b}{\gcd(a, b)} = A B \times \gcd(a, b) = a B = b A \]

In fact, because \( \gcd(a, b) = 1 \), this must be the least common multiple.

\[ \frac{A B}{\gcd(A, B)} = \text{lcm}(A, B) \]

This gives me a marvelous theorem relating the LCM and GCD.

Theorem
\[ \gcd(a, b) \text{lcm}(a, b) = a b \]

To prove this fact, I resort to the fundamental theorem of arithmetic, which states that every natural number has a unique factorization in prime numbers, up to the order of the factors. So I may consider the prime factors of this equation individually to prove equality. For a prime factor p, I can find the powers i and j, that divide a and b, respectively.

\[ \gcd(a, p^{i+1}) = p^i \]
\[ \gcd(b, p^{j+1}) = p^j \]

On the lefthand side of my theorem's equation, I need to comprehend how the GCD and LCM behave with respect to prime factors. The greatest common divisor requires as many factors of p as are found in common between a and b, which is the lesser of i and j. The least common multiple requires as many factors of p as can be found in either a or b, which is the greater of i and j.

The lefthand side of my equation, therefore, has \( p^{\min(i,j)} \times p^{\max(i,j)} = p^{\min(i,j)+\max(i,j)} = p^{i+j} \). And it is simple to see that the righthand side of my equation also has a factor of \( p^{i} \times p^{j} = p^{i+j} \). Having spoken generically about any prime factor, I have proven equality by the fundamental theorem of arithmetic.

Coprime certificates

It's fun to play on the calculator and see how the GCD works on large numbers. Now, back on the investigation of common divisors, I can prove another result. Suppose I write down an equation in the integers as follows.

\[ B = A + 1 \]

I can write A as a product of two of its divisors.

\[ B = a c + 1 \]

Immediately, I can see that dividing a into B will leave a remainder of 1. So no divisor of A could be a common divisor. I can do likewise for B, but also find that dividing b into A will also result in a remainder (of one less than the factor).

\[ b d = A + 1 \]

So \( \gcd(A, B) = 1 \), but I also know that for any factors of each, \( \gcd(a, b) = 1 \). So this leads me to a classic result which si a special case of B├ęzout's identity It is that if \( a c + b d = 1 \), then \( \gcd(a, b) = 1 \). So if I found values to satisfy the equation, I could certify that \( \gcd(a, b) = 1 \). In this condition we also say, that the two numbers are coprime. And if I find a multiple of the one, call it Q, where Q+1 is a multiple of the other, then Q is the essence of a coprime certificate.

In fact, I may create a GCD certificate in like manner.

\[ \gcd(a, b) = C \]
\[ \gcd(a/C, b/C) = 1 \]

Now I just find a coprime certificate for \( (a/C, b/C) \) and call it Q. Then my GCD certificate is Q and C, the latter of which is the GCD which I am certifying.

I have dodged the question of how to generate such a value Q to save that topic for another day. Most commonly this value Q may be found by the extended Euclidean algorithm.