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