To find the HCF of two numbers, we generally write them as a product of their prime factors. Then the product of all the common factors is the HCF. However, it may not be easy to apply the prime factorisation method if the numbers are large. In such cases, we use the Euclid's division lemma.
Euclid’s Division Lemma
Given a dividend and a divisor, there will be an unique pair of quotient and remainder, satisfying the equation
Dividend = Divisor x Quotient + Remainder
This is true for any two positive integers and is referred to as Euclid's Division Lemma.
It states that:
Given positive integers m and n, there exist two unique integers q and r, satisying m = nq + r,
where 0 ≤ r < n.
This lemma is useful to find the HCF of large numbers when breaking them into factors is difficult.
Euclid’s Division Algorithm
Euclid's Division Algorithm is a technique to compute the HCF of two given positive integers. HCF of two positive integers a and b is the largest positive integer d that divides both a and b. Follow the steps below to compute the HCF of two given positive numbers, a and b using Euclid's division algorithm. We assume that a > b.
Step 1: Apply Euclid’s division lemma, to a and b to find whole numbers q and r, such that a = bq + r,
0 ≤ r < b.
Step 2: If r = 0, then HCF (a, b) = b. If r ≠ 0, then apply the division lemma to b and r.
Step 3: Continue the same procedure till the remainder is 0. The divisor at this stage will be the HCF of a and b.
Note that HCF(a , b) = HCF(b , r)
As we count the natural numbers, there seem to be lesser prime numbers than composite numbers. But do you know that every composite number can be written as a product of powers of primes in a unique way? This result is known as the " Fundamental Theorem of Arithmetic". It is also referred to as the unique factorization theorem and states that every integer greater than 1 either is prime itself or is the product of prime numbers and that this product is unique.
The Fundamental Theorem of Arithmetic
Every composite number can be factorised as a product of prime numbers uniquely.
For example,
315 = 3 x 3 x 5 x 7
360 = 2 x 2 x 2 x 3 x 3 x 5
Application of Fundamental Theorem of Arithmetic
For any two positive integers a and b:
HCF (a, b) = Product of the smallest power of each common prime factor in the prime factorization of each of the numbers
LCM (a, b) = Product of the greatest power of each common prime factor in the prime factorization of each of the numbers
Then for any two positive integers a and b:
HCF (a, b) x LCM (a, b) = a x b
Recall that rational numbers are real numbers that can be expressed as a fraction where the numerator and the denominator of the fraction are both integers. This includes all whole numbers (for example, 3 be written as 3/1) and all finite or recurring decimals.
Numbers that cannot be written as fractions are called irrational numbers. For example, the square root of 2 is an irrational number. Irrational numbers have endless non-repeating digits to the right of the decimal point.
Here’s a fun fact about irrational numbers:
Apparently Hippasus (one of Pythagoras' students) discovered irrational numbers when trying to write the square root of 2 as a fraction (using geometry, it is thought). Instead he proved you couldn't write the square root of 2 as a fraction and so it was irrational!
Some example of irrational numbers are Pi and Euler’s number (e).
Theorems on Rational and Irrational Numbers
# Theorem 1: Let p be a prime number. If p divides a2, then p divides a, where a is a positive integer.
# Theorem 2: √2 is irrational. This can be proved by the method of contradiction.
# Theorem 3: Let x be a rational number with a terminating decimal expansion. Then x can be expressed in the form p/q, where p & q are co-prime numbers, and the prime factorization of q is of the form 2n5m, where m & n are non negative integers.
# Theorem 4: Let x = p/q be a rational number, such that the prime factorization of q is of the form 2n5m, where m & n are non negative integers. Then the decimal expansion of x terminates.
# Theorem 5: Let x = p/q be a rational number, such that the prime factorization q is not of the form 2n5m, where m & n are non negative integers. Then x has a decimal expansion which is non-terminating but repeating (recurring).
Properties of Rational and Irrational Numbers
- If m > 0 and is not a perfect square, then span id="MathJax-Element-1-Frame" class="MathJax" style="display: inline; font-style: normal; font-weight: normal; line-height: normal; font-size: 16px; text-indent: 0px; text-align: left; text-transform: none; letter-spacing: normal; word-spacing: normal; overflow-wrap: normal; white-space: nowrap; float: none; direction: ltr; max-width: none; max-height: none; min-width: 0px; min-height: 0px; border: 0px; padding: 0px; margin: 0px; position: relative;" tabindex="0" data-mathml="m">m−−√m is an irrational number.
- When we add or subtract two irrational numbers, the sum/difference is either a rational or an irrational number.
- When we add or subtract a rational number and an irrational number, the sum/difference is an irrational number.
- When we multiply a non-zero rational number and an irrational number, the product is an irrational number.
- When we multiply two irrational numbers, the product is either a rational or an irrational number.