EUCLID'S DIVISION LEMMA AND ALGORITHM
EUCLID'S DIVISION LEMMA 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 ...