Euclid’s Division Lemma And Theorem of Arithmetic

1. Natural Numbers: The numbers generally used to count objects are calld Natural Numbers. The set of Natural Numbers is denoted by N.
    N = {1, 2, 3, 4, ........}
Note: (i)  The least natural numbers is 1
(ii) The greatest natural numbers is not defined.
(iii) The set of natural numbers is also known as counting numbers
2.    Properties of Natural Numbers :
(i) Closure Property : If a, b \(\in\) N then a+b  N, a.b N
(ii) Commutative Property : a, b \(\in\)N, a+b = b+a, a x b = b x a
(iii) Associative Property : a, b, c\(\in\) N,(a+b)+c = a+(b+c)
(iv) Distributive Property : a, b, c \(\in\) N, a. (b+c) = a.b + a.c
(v) Existence of Identity Element:
    a) If a, x\(\in\) N then a+x = a. But there does not exists any natural number x  such that a+x = a
    Hence, additive indentity does not exists in the set of natural numbers.
    b) If a, x \(\in\) N then we have a.x = x.a = a, here x =1
    Hence, the multiplicative identity in the set of natural numbers is 1.
(vi) Existence of Inverse Element:
    a) If a, b, x are natural numbers then a+b = x = b+a i.e., there does not exists any natural numbers b such that a+b = x, here x is equal to zero
2.    Whole Numbers : The set of Natural Numbers together with zero is called         set of whole numbers.
    The set of whole numbers is denoted by W.
    W = {0}U{N}
    W = {0, 1, 2, 3, 4, ......}
Note : i) The least whole numbers is zero i.e., 0.
    ii) The greatest whole numbers is not defined.
    iii) Set of natural numbers is subset of whole number
3.    Set of Integers : The set of whole numbers together with negatives of natural numbers is called the integers.
    Here Negatives of Natural Numbers means -1, -2, -3, .....
    The set of integers is denoted by Z or I.
    Z = {.....-3, -2, -1, 0, 1, 2, 3, .....}
    Here {1, 2,, 3, ....} are called positive integers.
     \(Z^{+}={1,2,3......}\)
    Here {-1, -2, -3, .....} are called negative integers.
      \(Z^{-}={{-1,-2,-3........}}\)
NOTE (i) : Natural Numbers are also known as positive integers i.e., N = Z⁺ or I⁺
    (ii) 0 i.e., zero is neither positive (or) negative
4.    Rational Numbers : The numbers which are of the form or which can be expressed in the form of  \(p\over q\), where p, q \(\in\)Z and \(q\ne0\) are called Rational Numbers.
    The set of Rational Numbers is denoted by Q.
    \(\text{Q=}\left\{ \frac{p}{q}/p,q\in z,q\ne 0 \right\}\)
Example : \(\frac{1}{2},\frac{-1}{3},\frac{4}{3},5,-4,0\)

NOTE : All integers are rational numbers, but all rational numbers need not be integers.

5. Irrational Numbers: The numbers which cannot be expressed in the form of \(p\over q\) where p, q \(\in\) Z  and \(q\ne0\) are called Irrational Numbers or Simply saying the numbers which are not rational are called irrational numbers
Example : \(\sqrt{2},\sqrt{3},\sqrt{1.5},\sqrt[3]{5},\sqrt[4]{8}\)
NOTE (i) : \(\pi\) is an irrational number where as \(22\over 7\) is rational number.

6. Real Numbers : The set of rational and irrational numbers is called Real Numbers i.e., R = QUQ<sup>1

7. Division Algorithm :

Dividend = Divisor x Quotient + Remainder
8. Fundamental Theorem of Arithmetic : Every composite number can be expressed as product of prime numbers uniquely.
 Ex : 4 = 23 x
9. Euclid’s Division Lemma :  For any two positive integers say x and y, there exists unique integers say q and r satisfying
 x = yq+r   where \(0\le r\)</sup>
We know

\(\therefore 1800={{2}^{3}}\times {{3}^{3}}\times {{5}^{2}}\)
Example : Show that 5 x 3 x 2 + 3 is a composite number.
Solution : 5 x 3 x 2 + 3 = 3(5 x 2 + 1) = 3(11)
    The number is a composite number
Example :: Find the HCF and LCM of 48 and 56 by prime factorisation method.
Solution : We know,  48 = 2⁴ x 3¹
                 56 = 2³ x 7¹
    HCF = 2³ (The product of common prime factors with lesser index)
    LCM = 2⁴ x 3¹ x 7¹ (product of common prime factors with greater index
Example : Two bells toll at intervals of 24 minutes and 36 minutes respectively. If they toll together at 9am, after how many times do they toll together again, at the earliest?
Solution : The required time is LCM of 24 and 36.
        24 = 2³ x 3
        36 = 2² x 3²
     LCM of 24 and 36 is  2² x 3² = 72
    So, they will toll together after 72 minutes.
Example : Check whether there is any value of x for which 6x ends with 5.
Solution : If 6x ends with 5, then 6x would contain the prime 5.
    But 6x = (2 x 3)^x = 2^x x 3^x 
    The prime numbers in the factorization of 6x are 2 and 3.
    By uniqueness of fundamental theorem, there are no primes other than 2 and 3 in 6^x.
     6^x never ends with 5.
<sup>Example : Consider the integers 9 and 19.
     19= 9 x 2 + 1
Example : Consider the integers 6 and 24.
     24 = 6 x 4 + 0
NOTE : Euclid’s Division Lemma is used to find the H.C.F or G.C.D of two numbers.
10. Example : Find the HCF of 250 and 30
Solution : Using Division Lemma we get 
        250 = 30 x 8 + 10
    Again 30 = 10 x 3 + 0
Here, we notice the remainder is zero and we cannot proceed further.
    The divisor at this stage is 10.
    The HCF of 250 and 30 is 10.
NOTE : Euclid’s division algorithm is stated for only positive integers. It can be extended for all negative integers also
11. Applications of Euclid’s Division Algorithm :
(i) Show that every positive even integer is of the form 2n and every positive odd integer is of the form 2n+1.
Solution : For any integers x and y, we have 
    x = 2n+r, where \(n\ge0\)
    But \(0\le r <2\)
     r = 0 or 1
    x is a positive even integer when r =1, x =2n+1
     x is a positive odd integer 
(ii) A trader has 612 dettol soaps and 342 pears soaps. He packs them in boxes and each box contains exactly one type of soap. If every box contains the same number of soaps, then find the number of soaps in each box such that the number of boxes is the least.
Solution : The required number is HCF of 612 and 342.
    This number gives the maximum number of soaps in each box and the number of boxes with them be the least.
By using Euclid’s Division Algorithm, we have
    612 = 342 x 1 + 270
    342 = 270 x 1 + 72
    270 = 72 x 3 + 54
    72 = 54 x 1 + 18
    54 = 18 x 3 + 0
Here we notice that the remainder is zero, and the divisor at this stage is 18.
    HCF of 612 and 342 is 18.
So, the trader can pack 18 soaps per box
12. Fundamental Theorem of Arithmetic : Every composite number can be expressed as the product of prime factors uniquely
NOTE: In general, if a is a composite number.
    a = p₁.p₂.p₃......... where  p₁.p₂.p₃.........are primes in ascending order
Example : Write 1800 as product of prime factors.</sup>