## Fundamental theorem of Arithmetic, HCF and LCM by factorization and problem solutions

In the* first and second part of NCERT solutions for class 10 maths on Real Numbers*, we introduced

*basic concepts on real numbers*, the

*long division method*formalized by Euclid in his

*division lemma, solutions to Euclid's division lemma puzzle and Euclid's division algorithm for finding HCF along with solutions to problems.*

Building on these concepts, we will now present the Fundamental theorem of Arithmetic and HCF and LCM by Factorization followed by solutions to problems.

You **may skip the theory part** and **go straight to the problem solutions section**.

### Fundamental theorem of Arithmetic

Before stating the theorem, let's have a short recap on the concepts of factors, prime numbers and prime factors.

A

Factorof an integer is a second integer that divides the first integer fully leaving zero remainder.

For example, 3 and 4 are two factors of the integer 12.

Secondly,

A

prime numberis an integer that has only 1 and itself as its factors.

For example, 6 is not a prime number as it has 2 and 3 as factors. But 31 is a prime number as it has only 1 and itself as its factors.

From these two concepts, we can define a prime factor as,

A

prime factoris a prime number and is a factor of a second integer.

For example, among the two factors 3 and 4 of 12, 3 is a prime factor but 4 is not, as 4 has 2 as a prime factor. That's why when we express an integer as a product of factors by factorization, we find all the prime factors of the integer. For example, when we factorize 12, we find its three factors as 2, 2 and 3 and express it as the product of these prime factors as,

$12=2\times{2}\times{3}$.

Now we are ready to state the **Fundamental theorem of Arithmetic** as,

Every positive integer can be expressed as a product of a unique set of prime factors, where the individual factors may appear in any position in the product.

#### Reason why fundamental theorem of arithmetic is true

Let's assume the integer $N$ is factorized into two unique set of prime factors as,

$N_1=a_1\times{a_2}\times{c_3}\times{b_1}\times{b_2}\times{b_3}$, and,

$N_2=a_1\times{a_2}\times{a_3}\times{b_1}\times{b_2}\times{c_2}$.

Here, $N_1=N_2=N$.

Dividing the two and cancelling out common factors we get,

$\displaystyle\frac{N_1}{N_2}=\displaystyle\frac{c_3\times{b_3}}{a_3\times{c_2}}\neq 1$.

As $N_1$ and $N_2$ are two representations of same number $N$, result of division of one by the other must be 1 and so, $N$ **cannot be expressed as a product of more than one unique set of prime factors**.

In other words,

Any positive integer $N$ can have only one unique set of factors.

Let us now show you a few examples of breaking up a number into its component unique set of prime factors.

#### Examples of numbers expressed as product of prime factors

$32=2\times{2}\times{2}\times{2}\times{2}$

$60=2\times{2}\times{3}\times{5}$

$168=2\times{2}\times{2}\times{3}\times{7}$

$330=2\times{3}\times{5}\times{11}$

$13585=5\times{11}\times{13}\times{19}$.

Notice that in every example, the factors are prime factors, and **a prime factor might appear more than once in a number**, as in factor expansion of 32, 60 and 168.

Now we will introduce the mechanism of **finding HCF and LCM by factorization**.

### HCF and LCM of integers by factorization

Once you find the prime factors of two or more numbers, **to find the HCF,**

Just identify the prime factors

common to all the numbersand form the product of these common factors as the HCF of the numbers.

**Example:** Find the HCF of 60, 168 and 330.

**Solution:** Expressing the three numbers in the form of product of factors,

$60=2\times{2}\times{3}\times{5}$

$168=2\times{2}\times{2}\times{3}\times{7}$

$330=2\times{3}\times{5}\times{11}$.

Inspecting the three sets of factors, we identify the common factors 2 and 3, and the product 6 as the HCF.

The figure below shows the two factors common to each integer circled and HCF formed as the product of these two common factors.

Note that by factorization method you can find out **HCF of any number of integers** just by identifying the **factors common to ALL of the integers** and forming **their product**.

**To find the LCM** instead of HCF,

Just cross out the prime factors that are

common to more than one integer while preserving the highest power of every factor in an integer.Collect the remaining factors to a product to form the LCM. For LCM of two integers,you can divide one by the HCF and multiply the quotient with the other.

By the removal of all occurrences of a factor in more than one integer, it is ensured that **in LCM, HCF appears only once as well as it fulfills the requirement of smallest multiple of all the integers.**

**Example:** Find the LCM of 60, 168 and 330.

**Solution:** Expressing the three numbers in the form of product of factors,

$60=2\times{2}\times{3}\times{5}$

$168=2\times{2}\times{2}\times{3}\times{7}$

$330=2\times{3}\times{5}\times{11}$.

Inspecting the three sets of factors, we identify the common factors 2 and 3, and remove these two from the first two numbers. Next we identify the factors 2 and 5 common to 60 and 330 and remove these two also. The product of the remaining factors form the LCM as,

$\text{LCM}$

$=2\times{2}\times{7}\times{2}\times{3}\times{5}\times{11}$

$=9240$.

Note that for preserving $2^3$, the highest power of 2 in 168 and all integers combined, we couldn't remove 2 common between 168 and 330.

The figure below shows this operation to find LCM of 60, 168 and 330.

The preservation of the highest power of each factor in LCM gives rise to the **mathematically rugged method of finding LCM** as,

Identify highest power of each factor in each of the numbers so that product of the highest power of each factor taken once form the LCM.

In the three integers 60, 168 and 330, $2^3=8$ is the highest power of 2 more than 1, and rest of the factors 3, 5, 7 and 11 occur with power unity. So the LCM would be,

$\text{LCM}=8\times{3}\times{5}\times{7}\times{11}=9240$.

Let us take up a simpler example.

**Example 2.** Find the LCM of 18 and 84.

$18=2\times{3}\times{3}$, and

$84=2\times{2}\times{3}\times{7}$.

HCF is $2\times{3}=6$.

LCM is, $3\times{84}=252$, factors of HCF 2 and 3 are removed from the first number leaving only 3 contributed by the first number. Just multiplying 3 by the second number ensures inclusion of only the highest powers (in this case 1) of each factor only once.

Notice that, $18\times{84}=6\times{3}\times{84}=\text{HCF}\times{LCM}$.

This **relation between HCF and LCM of two numbers as a product of the two numbers** follows from the definition of the two concepts.

Though the processes seem to be simple, you need to find out the factors first. How would you find out factors of an integer? Let us briefly go through this process of **factorization** of an integer.

If you decide, you may skip this section.

#### Finding out factors or factorization

The method is as follows,

**Step 1:** If the **number is even,** divide by 2 to get the quotient. Repeat till the quotient, which we call as **result number**, remains even. In this step we will extract all factors 2 from the number. We call 2 as the **test factor**.

**Step 2:** **Test factor as the next prime number:** Determine the **next prime integer** and repeat Step 1 with with this integer **as the test factor in place of 2**. *For the first time, either when the number is odd to start with, or after extracting all factors of 2 in Step 1, the test factor with which we will test the result number will be 3.*

**Step 3:** **End condition:** Repeat Step 2 and **stop** only when the result number becomes 1, or **square of the test factor** becomes **larger than the result number** at a particular stage.

For **example** if we factorize 8400,

**Step 1:** yields the factors, 2, 2, 2 and 2 with final quotient or result number as 525.

**Step 2:** test factor 3: factors: 3; result number 175.

**Step 3:** test factor 5: factors: 5 and 5; result number 7, the last factor.

So the factors of 8400 are,

2, 2, 2, 2, 3, 5, 5 and 7.

To determine at any stage whether the result number at that stage is divisible by the test factor, we need to do **divisibility test** before actual division.

Briefly the **divisibility tests** are,

**for 2:**if the number is even it is divisible by 2.**for 4:**if the number formed by the first two digits from right is divisible by 4, the main number is divisible by 4. For example, 168 is divisible by 4**as 68 is divisible by 4**.**for 8:**if the number formed by the first three digits from right is divisible by 8, the main number is divisible by 8. For example, 311144 is divisible by 8**as 144 is divisible by 8**.**for 3:**if the sum of the digits of the number (called integer sum) is divisible by 3, the number is divisible by 3. For example, 87123 is divisible by 3 as**integer sum 21 is divisible by 3.****for 9:**if the sum of the digits of the number or integer sum is divisible by 9, the number is divisible by 9. For example, 4959 is divisible by 9 as**integer sum 27 is divisible by 9.****for 25:**if the number formed by first two digits from right is 00, 25, 50 or 75, the main number is divisible by 25. For example 17625 is divisible by 25.**for 11:**if the sum of alternate digits are equal or difference between the sums is divisible by 11, the number is divisible by 11. For example, 539 is divisible by 11 as difference of alternate digits sums $14-3=11$ is divisible by 11. Similarly, 253 is divisible by 11 as alternate digit sums are equal to single value 5.**for 5:**if the unit's digit of the number is either 0 or 5, the number is divisible by 5. For example, 2345 is divisible by 5.

For rest of the tests recommendation is to directly divide.

**Recommendation:** To speed up factorization, if the number is even test for 8, then 4 and the 2. If the number is odd, test for 25 followed 5; then 11; and then 9 followed by 3.

### Solutions to problems based on factorization and HCF and LCM by factorization

**Problem 1.1 **Express 140 as a product of its prime factors.

**Solution problem 1.1.**

**Step 1:** As 140 is even: test for 8: fails. Test for 4: quotient result number 35 which is $7\times{5}$.

So, $140=2\times2\times{5}\times{7}$.

**Problem 1.2** Express 156 as a product of its prime factors.

**Solution problem 1.2.**

**Step 1:** As 156 is even: test for 8: fails. Test for 4: quotient result number 39 which is $3\times{13}$.

So, $156=2\times{2}\times{3}\times{13}$.

**Problem 1.3** Express 3825 as a product of its prime factors.

**Solution problem 1.3.**

**Step 1:** Test 25 success: quotient result number: 153.

**Step 2:** Result number 153: test for 9 success: quotient result number 17.

So, $3825=3\times{3}\times{5}\times{5}\times{17}$.

**Problem 1.4** Express 5005 as a product of its prime factors.

**Solution problem 1.4.**

**Step 1.** Test for 5: quotient result number 1001.

**Step 2:** Result number 1001: Test for 3 fails. Test for 7 by actual division mentally: quotient result number 143.

**Step 3:** Result number 143: Test for 11: quotient result number is the prime factor 13.

So, $5005=5\times{7}\times{11}\times{13}$.

**Problem 1.5** Express 7429 as a product of its prime factors.

**Solution problem 1.5.**

**Step 1:** Test for 3 fails; test for 7 fails; test for 11 fails; test for 13 fails; test for 17 success: quotient result number 437.

**Step 2:** Result number 437: test for next prime integer 19: quotient result number 23, which is a prime.

So, $7429=17\times{19}\times{23}$.

**Problem 2.1.** Find the HCF and LCM of 26 and 91 and verify $\text{HCF}\times{\text{LCM}}=26\times{91}$.

**Solution problem 2.1.**

By observation we express,

$26=2\times{13}$, and

$91=7\times{13}$.

So HCF is the single common factor 13 and LCM is, $2\times{91}=182$.

Also,

$\text{HCF}\times{\text{LCM}}=13\times{182}=2\times{13}\times{91}=26\times{91}$.

**Problem 2.2.** Find the HCF and LCM of 510 and 92 and verify $\text{HCF}\times{\text{LCM}}=510\times{92}$.

**Solution problem 2.2.**

By observation we can express,

$510=2\times{3}\times{5}\times{17}$, and

$92=2\times{2\times{23}}$.

So, $\text{HCF}=2$, and $\text{LCM}=510\times{46}=23460$.

Also,

$\text{HCF}\times{\text{LCM}}=2\times{510}\times{46}=510\times{92}$.

**Problem 2.3.** Find the HCF and LCM of 336 and 54 and verify $\text{HCF}\times{\text{LCM}}=336\times{54}$.

**Solution problem 2.3.**

By observation we can express,

$336=2\times{2}\times{2}\times{2}\times{3}\times{7}$, factors taken our first 8, then 2, then 3 and then 7.

$54=2\times{3}\times{3}\times{3}$.

So, $\text{HCF}=2\times{3}=6$.

Dividing 54 by 6 and taking the product of quotient 9 and 336 we get LCM as,

$\text{LCM}=9\times{336}=3024$.

Thus, $\text{HCF}\times{\text{LCM}}=6\times{9}\times{336}=336\times{54}$

**Problem 3.1.** Find HCF and LCM of 12, 15 and 21 by prime factorization method.

**Solution problem 3.1.**

By observation we can express the three integers as product of prime factors,

$12=2\times{2}\times{3}$

$15=3\times{5}$

$21=3\times{7}$.

Single common factor 3 is the HCF.

Dividing the first two numbers by the HCF 3, the quotients 4 and 5 along with 21 are multiplied together to form the LCM as,

$\text{LCM}=4\times{5}\times{21}=420$.

**Problem 3.2.** Find the HCF and LCM of 17, 23, and 29 by prime factorization method.

**Solution problem 3.2.**

As the three given integers are all prime numbers, their HCF is 1.

So $\text{LCM}=17\times{23}\times{29}$

$=391\times{29}=11730-391=11339$.

**Problem 3.3.** Find the HCF and LCM of 8, 9, and 25.

**Solution problem 3.3.**

As in the previous problem, the three given integers 8, 9 and 25 do not have any common factor except 1 which is the HCF. The numbers in their product of prime factors are,

$8=2\times{2}\times{2}$

$9=3\times{3}$

$25=5\times{5}$.

Thus the LCM of the three numbers is their product as shown below,

$\text{LCM}=8\times{9}\times{25}=1800$.

**Problem 4.** Given that HCF of 306 and 657 as 9, find their LCM.

**Solution problem 4.**

Dividing 306 by 9 quotient is 34.

So LCM of the two numbers is,

$\text{LCM}=34\times{657}=22338$.

**Problem 5.** Check whether $6^n$ can end with the digit 0 for any natural number $n$.

**Solution problem 5.**

For a number to end with digit 0, that is, a multiple of 10, it must have a factor 2 as well as a factor 5.

As 6 has factors only 2 and 3 and no 5, any natural number power of 6 cannot have end digit as 0.

**Problem 6.** Explain why $7\times{11}\times{13}+13$ and $7\times{6}\times{5}\times{4}\times{3}\times{2}\times{1}+5$ are composite numbers.

**Solution problem 6.**

In the first number, all three of the product term factors are prime factors and the product term itself is a composite number. Adding 13 to it effectively adds 1 to the product $7\times{11}$ and converts it from an odd number to an even number as follow,

$7\times{11}\times{13}+13=13\times{(7\times{11}+1)}=13\times{78}$.

Now the first given number has more number of prime factors as follows,

$7\times{11}\times{13} + 13$

$13\times{78}=2\times{3}\times{13}\times{13}$.

Thus the first given number is a composite number.

**Concept:**

If you add any combinaton of factors of a product of factors to the product of factors itself, the result will always remain a composite number.

This happens because the additive term is absorbed into the product of factors generating an additional group of factors. The final result will thus have at least two prime factors.

For the second number we get,

$7\times{6}\times{5}\times{4}\times{3}\times{2}\times{1}+5$

$=5\times{(1008+1)}=5\times{1009}$, a composite number.

**An example of an addition of a factor to a product of factors resulting just two prime factors**

$2\times{3}\times{5}\times{5}+5$

$=5\times{(30+1)}=5\times{31}$.

Even though 5 and 31 are two prime factors, their product by definition is a composite number.

**Problem 7.** There is a circular path around a sports field. Sonia takes 18 minutes to drive one round of the field, while Ravi takes 12 minutes for the same. If they both start at the same point at the same time going in the same direction, after how many minutes will they meet again at the starting point?

**Solution problem 7.**

At LCM 36 minutes of 18 and 12, the two numbers meet for the first time and that's why 36 is the smallest number fully divisible by both 18 and 12.

In this period of 36 minutes, Ravi covers 3 rounds and Sonia 2 rounds of the circular course, 3 and 2 being the quotients of division of 36 by 12 and 18 respectively.

**Answer:** 36 minutes.

Related articles on NCERT solutions follow.

### NCERT Solutions for Class 10 Maths

#### Real Numbers

**NCERT Solutions for Class 10 Maths on Real numbers part 3, HCF and LCM by factorization and problem solutions**

**NCERT Solutions for Class 10 Maths on Real numbers part 1, Euclid’s division lemma puzzle solutions**

#### Introduction to Trigonometry

**NCERT Solutions for Class 10 Maths on Trigonometry, solution set 6**

**NCERT Solutions for Class 10 Maths on Trigonometry, solution set 5**

**NCERT Solutions for Class 10 Maths on Trigonometry, solution set 4**

**NCERT Solutions for Class 10 Maths on Trigonometry, solution set 3**

**NCERT Solutions for Class 10 Maths on Trigonometry, solution set 2**

**NCERT Solutions for Class 10 Maths on Trigonometry, solution set 1**