Class 10 maths chapter 1 | Fundamental theorem of Arithmetic | Euclid Division Algorithm | How to find HCF and LCM using Prime factorization

Chapter 1

Euclid Division Algorithm:

Given positive integers a and b , there exist unique integers q and r satisfying
a = bq + r , 0 ≤ r < b

How to find HCF and LCM using Euclid's Algorithm

I) 135 and 225
let a = 225 , b = 135
Apply Euclid's Algorithm till remainder becomes zero , the corresponding divisor will be the HCF
225 = 135 × 1 + 90
135 = 90 × 1 + 45
90 = 45×2 + 0
So , HCF = 45 .

I) 455 and 42
let a = 455 , b = 42
Apply Euclid's Algorithm till remainder becomes zero , the corresponding divisor will be the HCF
445 = 42 ×10 + 35
42 = 35 × 1 + 7
35 = 7×5 + 0
So , HCF = 7 .

---

Fundamental theorem of Arithmetic:

"Every Composite number can be expressed as a product of primes and this factorizaion is unique."
Example : Let's take a composite number '12'
It can be written as factorization of prime numbers. i.e. 12 = 2 ×2 ×3 and this factorization is unique. this is the fundamental theorem of Arithmetic
Question : Check whether there is any value of n for which 6ⁿ can end with digit 0 .
Solution : For being end with '0' , 5 must be present as a prime factor in te given composite number . So let's check 6ⁿ.
6ⁿ = (2 ×3 )ⁿ = 2ⁿ×3ⁿ.
there is only 2 and 3 prime factors n given composite number. 5 is not factor of 6ⁿ. So 6ⁿ will not end with 0 for any value of n.

---

How to find HCF and LCM using Prime factorization

Understand this By taking an example.
i). 26 and 91
Step 1 : factorize the Number
26 = 2 × 13
91 = 7 × 13
Step 2 : For HCF : take the common factor present in both the number like in this example , 13 is only highest common factor.
So , HCF (26, 91 ) = 13
Step 3 : For LCM
multiply the remaining factors with HCF
LCM (26, 91) = 13 × 2 × 7 = 187

There is also a relation Between LCM and HCF
For any two positive integer a and b
HCF(a,b) × LCM(a,b) = a × b
Note : This formula is valid for two number.
Question : Given that HCF(306 , 657) = 9 , find LCM(306 , 657)
Solution :
HCF(306 , 657) = 9
HCF(a,b) × LCM(a,b) = a × b
LCM(306 , 657) × 9 = 306 × 657
LCM(306 , 657) = 201042/9 = 22338