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

  1. 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.