The greatest available number that splits both integers completely is the Highest Common Factor (HCF) of two numbers. The greatest common factor (HCF) is sometimes known as the greatest common divisor (GCD). HCF can be calculated using the prime factorisation and repeated division methods.
HCF by Prime Factorisation
When two numbers, say p and q, are divided exactly by the biggest available number, the result is known as the highest common factor of the two numbers. When we give the product of two prime numbers, say x and y, we are showing their prime factorization. This indicates that prime factorization is represented by the product of two prime integers. The following are the actions we must take:
Find the prime factorization of the given integers one by one.
Make a list of the numbers' similar prime factors.
The HCF of given numbers is the product of common prime factors.
Prime Factorization of 36
Example of HCF By Prime Factorisation
Let's solve some HCF problems to have a better idea.
Let's find out the HCF of 45 and 150 using the prime factorisation method.
First, find the prime factors of 150 and 45 separately.
The similar factors obtained by both of them need to be noted down.
These same numbers are then multiplied to obtain HCF.
Firstly write down what is the factor of 150 and 45. Prime factorisation of 45 will give \[5 \times 3 \times 3 \times 1\] as prime factors. The prime factorisation of 150 will give \[5 \times 5 \times 3 \times 2 \times 1\] as prime factors. Among these prime factors, 3 and 5 are common in both of them. If we multiply 3 and 5 we will get 15 as a result. So, 15 is the HCF of 45 and 150.
HCF by Repeated Division
To get the HCF of two integers using the division method, follow the steps below.
Divide the greater number by the lesser number.
Consider the remainder of the preceding step the divisor, and the divisor of the preceding step the dividend, then repeat the long division.
Continue long division until the remainder equals zero.
When remainder = 0, HCF is the last divisor left.
Example of HCF by Repeated Division
To understand this let's take an example of finding HCF of 56 and 84 using the repeated division method.
Divide 84 by 56. The remainder obtained from this would be 28.
Now we need to divide 56 with the remainder we got in the previous step.
As the remainder now we got is 0. So the HCF obtained is 28.
HCF of 56 and 84
The listed factors approach may also be used to calculate the HCF of two integers. In this procedure, we list all the factors of two integers and find the one with the greatest common factor. The HCF of two numbers is always less than or equal to one of them. The HCF between two prime numbers always equals one.
1. HCF of 20 and 15 is
Explanation: the prime factors of 20 are \[5 \times 2 \times 2 \times 1\] . And the prime factors of 15 are \[5 \times 3 \times 1\] . The factor 5 is common in both numbers. So, the HCF of 15 and 20 is 5.
2. HCF of 150 and 300 is
Explanation: The prime factors of 150 are \[5 \times 5 \times 3 \times 2 \times 1\] . And the prime factors of 300 are \[5 \times 5 \times 3 \times 2 \times 2 \times 1\] . 5, 5, 3, and 2 are common in both numbers making their product result 150. So, the HCF of 150 and 300 is 150.
3. HCF of 12 and 18 is
Explanation: the prime factors of 12 are \[3 \times 2 \times 2 \times 1\] and of 18 are \[3 \times 3 \times 2 \times 1\]. The common factors are 2 and 3 so the hcf of 12 and 18 is 6.