Question

# Find the HCF of integers 375 and 675 by the prime factorization method.

Hint: First find the prime factorization of given two numbers by dividing them with their prime factors till you get 1. Now combine them and write the terms as their powers. Then use least power in each term and multiply them to get the solution. The highest common factors are found in this way.

Highest common factor: Mathematically, the greatest number which divides the both given numbers is called the common factor. It is also called the greatest common divisor.
Prime factorization of 375.
First the number given in the question is written as: 375
By dividing it by 5, and writing it as product of 5, quotient:
$5\times 75$
By dividing it by 5 and writing it as product of 5, quotient:
$5\times 5\times 15$
By dividing it by 5 and writing it as product of 5, quotient:
$5\times 5\times 5\times 3$
By dividing it by 3 and writing it as product of 3, quotient:
$5\times 5\times 5\times 3\times 1$
We got 1 so, we stop at this point and equate it to original number
$375=5\times 5\times 5\times 3$
By combining the similar prime numbers, we get it as:
$375={{5}^{3}}\times 3$

Now, the second number given in the question is: 675
By dividing it by 5, and writing it as product of 5, quotient:
$5\times 135$
By dividing it by 5, and writing it as product of 5, quotient:
$5\times 5\times 27$
By dividing it by 3, and writing as product of 3, quotient:
$5\times 5\times 3\times 9$
By dividing it by 3, and then writing it as product of 3, quotient:
$5\times 5\times 3\times 3\times 3$
By dividing it by 3, and writing it as product of 3, quotient:
$5\times 5\times 3\times 3\times 3\times 1$
We got 1. So, we stop here and equate it to original.
$675=5\times 5\times 3\times 3\times 3$
By combining the similar prime numbers.
\begin{align} & 675={{5}^{2}}\times {{3}^{3}} \\ & 375={{5}^{3}}\times 3 \\ \end{align}
So, by looking at both equations, we can say the primes involved in this highest common factor calculation are 5,3.
By definition we say the value of highest common factor is ${{5}^{p}}\times {{3}^{q}}$ where p, q are least power of 5,3 in them both. So, p= min (3,2) q=min (3,1). So, we get p=2, q=1.
HCF$={{5}^{2}}\times 3=25\times 3=75$
Therefore, HCF of 675, 375 is 75.

Note: Be careful you must do until you get 1. The steps of division are very important. Dividing must be performed again and again on the last term in the product which makes our primes product look better and easy to find when we get 1. The combining part is also crucial. Do it carefully.