Euclid’s Division Algorithm.
- It is a technique to compute (divide) the HCF of two positive integers ‘a’ and ‘b’ in such a way that it leaves a remainder ‘r’ that is smaller than ‘b’.
Here a = Dividend b = Divisor
q = Quotient r = Remainder
i.e. Dividend = (Divisor x Quotient) + Remainder
a = bq + r O r b
The Fundamental Theorem of Arithmetic.
- This theorem is also called a unique factorization theorem.
- It involves multiplication of positive integers, where every positive number can be expressed as a product of primes in a unique way
Application of Fundamental Theorem of Arithmetic.
I)We use it to prove the irrationality of many numbers such as, 11 and 13
- II) We apply this theorem to explore when exactly the decimal expansion of a rational number, say ( q 0 )is terminating and when it is non-terminating repeating.
Note: We do this by looking at the prime factorization of the denominator q of we can also see that the prime factorization of q will completely reveal the nature of the decimal expansion
Euclid’s Division Lemma:- (Theorem 1.1 )
Given positive integers a and b, there exist unique integers q and r satisfying a=bq+r, where
o r b.
Euclid’s division algorithm is based on this lemma.
What is an algorithm?
An algorithm is a series of well defined steps which gives a procedure for solving a type of problem.
What is a Lemma?
A lemma is a proven statement used for proving another statement.
Let us see how an algorithm works, through an example.
Stating Euclids division algorithm ( to obtain the HCF of two positive integers)
Follow steps below.
Example 1 : Use Euclid’s algorithm to find the HCF of 4052 and 12576.
Solution :
Step 1 :Since 12576 > 4052, we divide 12576 by 4052
12576 = 4052 × 3 + 420
Step 2 : Since the remainder in not 0, we divide 4052 by 420,
4052 = 420 × 9 + 272
Step 3 :Since the remainder in not 0, we divide 420 by 272,
420 = 272 × 1 + 148
Since the remainder is not 0, we divide272 by 148,
272 = 148 × 1 + 124
Since the remainder is not 0, we divide 148 by 124 ,
148 = 124 × 1 + 24
Since the remainder is not 0, we divide 124 by 24 , 124 = 24 × 5 + 4
Since the remainder is not 0, we divide 24 by 4 ,
24 = 4 × 6 + 0
The remainder has now become zero, so our procedure stops. Since the divisor at this stage is 4, the HCF of 12576 and 4052 is 4.
Note: Euclid’s division lemma and algorithm are so closely interlinked that people often call former as the division algorithm also.
