HCF of two numbers by Prime Factorization
When two numbers, say p and q are exactly divided by the largest possible number, the number is said to be the highest common factor of the respective numbers. When we show the product of two prime numbers, let's say x and y, that is their prime factorization. This means the product of two prime numbers represents prime factorization. Let's understand, how to find the HCF of two numbers by the prime factorization method. Following are the steps we need to follow:
- Find the prime factorization of given numbers individually.
- List out the common prime factors of those numbers.
- Product of common prime factors is the HCF of given numbers.
For better understanding, let's solve some examples of HCF of two numbers by prime factorization. We will find the HCF of 56 and 84. Let's represent the numbers using the prime factorization.
So, we have, 56 = 2 × 2 × 2 × 7 and 84 = 2 × 2 × 3 × 7 . Now, HCF of 56 and 84 will the product of common prime factors with the lowest exponential power, that is, 7 and 22. So, HCF of 56 and 84 = 7 × 2 × 2 = 28.
HCF of two numbers by Division Method
To find HCF of two numbers by division method, we need to follow the following steps.
- Divide the larger number by the smaller number.
- Make the remainder of the above step as the divisor and the divisor of the above step as the dividend and do the long division again.
- Continue the long division till the remainder becomes 0.
- HCF is the last divisor left, when remainder = 0
