Introduction
Consider any two numbers, such as 12 and 36. Make a list of all the numbers which are factors (numbers which can divide 12 and 36 without leaving any remainder) of both 12 and 36: {1, 2, 3, 4, 6, 12}. The greatest of these factors is '12'. Thus, 12 is called the greatest common divisor (GCD) or the greatest common factor (GCF) of 12 and 36.Thus, we can define GCD as the largest number which is a factor (or divisor) of both the given numbers.
Let's consider another example. List all numbers which are factors of both 18 and 27: {1, 3, 9}. Clearly, 9 is the largest number which can divide both 18 and 27 without leaving any remainder (that is, it is a factor of 18 and 27). Thus, 9 is the GCD of 18 and 27.
Prime factorization method to find GCD
It's quite easy to find the GCD of small numbers such as given above. On the other hand, when you have large numbers, finding their GCD is simpler by using the prime factorization method. Let us learn the method by taking an example: 512 and 216.
Prime factorize both numbers
`512 = 2 \times 2 \times 2 \times 2 \times 2 \times 2 \times 2 \times 2 \times 2``216 = 2 \times 2 \times 2 \times 3 \times 3 \times 3`
To find their GCD, take all the prime factors of both the numbers which are common to both numbers and multiply them. In the above prime factorization, both the numbers 512 and 216 have three 2's common, but no other number/s are matching. Thus, their GCD is,
GCD = `2 \times 2 \times 2 = 8`
Thus, the greatest common divisor of 512 and 216 is 8.
No comments:
Post a Comment