AND
ALGORITHM

A lemma is a proven statement used for proving another statement.

An algorithm is a series of well defined steps which gives a procedure for solving a type of problem.

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 ALGORITM is a technique to compute HIGHEST COMMON FACTOR (HCF)

of two positive integers.

Let us take an example of euclid algorithm: Take two numbers 455 and 42

455 > 42

so, take the greater no. and apply euclid lemma

455=42 × 10 + 35

here we have Q=42,divisor=10 and remainder=35

Do these steps till the remainder become O

42= 35 × 1 +7

35=7 × 5 + 0

So, here the remainder becomes zero and algorithm works here cleary.

hence, the factor of 455 and 42 is 7

MATHSLEARNING