# 6 - Greatest Common Divisor

## GCD

The GCD of two numbers is the Greatest Common Divisor to both numbers. The GCD of 42 and 49 is 7 since it is the largest number that divides both 42 and 49 (giving integers as a result). The GCD of 43 and 49 is 1 because there is no number that is greater than 1 that divides both 43 and 49. Two numbers whose GCD is 1 are called coprime, or relatively prime.

## Euclide's algorithm

Euclide's algorithm enables us to calculate the GCD of two numbers. We first write the largest number as a multiple of the smallest plus a remainder. Then we we write the smallest as a multiple of the remainder plus a new remainder. We carry on until we get a remainder equal to 0. The last non-zero remainder is the GCD of the two initial numbers. Example : GCD of 556 and 148 :

## Simplifying fractions

Calculating the GCD can be useful to make a fraction irreducible. To do that, we need to calculate the GCD of the numerator and the denominator, and then divide both by this GCD. For example, to simplify the fraction we calculate the GCD of 312 and 845, then we divide the top and bottom of this fraction by the GCD we just found.

Hence we divide the numerator and denominator by 13, which gives

## Application of the GCD

Calculating a GCD can be useful to solve some problems. For example, if a shopper orders 90 torches with 135 lightbulbs and he wants to sell identical batches without having any torch or bulb left, we can wonder how many torches and how many bulbs there will be in each batch. The number of torches must be a divisor of 90 so that he has no torch left, and must also be a divisor of 135 since otherwise he would have bulbs left. In order to have the least amount of torches and bulbs in each batch, he needs to find out the GCD of 90 and 135. Using Euclid's algorithm, we find 45. He must hence make 45 batches, and we finally easily find that each batch will consist of 2 torches and 3 lightbulbs (there will be a spare bulb).

>>> Statistics lesson >>>

GCD

lesson, problems