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

Lemma:–     lemma is a proven statement used for proving another statement.

Euclid division Lemma :- If a and b be two given positive  integers  there exist unique pair of integers q and r satisfying  

a = bq + r  ,   0≤r<b.

Euclid division algorithm is a technique to compute the Highest Common Factor HCF of two given positive integers.

We state Euclid’s division algorithm for positive integers only but it can be extended for all integers except zero.


Euclid’s division lemma and algorithm are so closely interlinked that people often call former as the division algorithm also.

Fundamental Theorem of Arithmetic

Every composite number can be expressed ( factorized ) as a product of primes, and this factorization is unique, apart from the order in which the prime factors occur.

Prime factorization method to Find HCF and LCM :-

First find all the prime factors of given numbers.


HCF of two or more numbers =  Product of the smallest power of each common prime factor    involved in the numbers.


LCM of two or more numbers =  Product of the greatest power of each prime factor   involved in the numbers.

Statement-1 :  


Let p be a prime number. If p divides a2, (where a is a positive integer),then p divides a.

Scroll to Top
%d bloggers like this: