Theorem 1.1 (Euclid’s Division Lemma) : Given positive integers a and b, there exist unique integers q and r satisfying a = bq + r, 0 ≤ r < b.
Euclid’s Division Algorithm : This algorithm is used to find the h.c.f (Highest Common Factor) or g.c.d (Greatest Common Divisor)of two positive integers. It is based on Euclid’s Division Lemma that has been stated and explained above.
- Step 1 : Apply Euclid’s division lemma, to a and b to find integers (more precisely whole numbers) q and r such that a = bq + r, 0 ≤ r < b.
- Step 2 : If r=0, b is the g.c.d of a and b. If r≠0, apply the division lemma to b and r.
- Step 3 : Continue the process till the remainder is zero. The divisor at this stage will be the required GCD (HCF).
Theorem 1.3: Let p be a prime number. If p divides a2, then p divides a, where a is a positive integer.
Theorem 1.4: √2 is irrational.
Theorem – Good to know: If a non -ve integer is not a perfect square, then its square root is irrational.
Theorem 1.5: Let x be a rational number whose decimal expansion terminates. Then x can be expressed in the form p/q, where p and q are coprime, and the prime factorisation of q is of the form 2n5m, where n, m are non-negative integers.
Theorem 1.6: Let x = p/q be a rational number, such that the prime factorisation q of q is of the form 2n5m, where n, m are non-negative integers. Then x has a decimal expansion which terminates.
Theorem 1.7: Let x = p/q , where p and q are coprimes, be a rational number, such that the prime factorisation of q is not of the form 2n5m, where n, m are non-negative integers. Then, x has a decimal expansion which is non-terminating repeating (recurring).
