Algorithm:-
An algorithm is a series of well defined steps which gives a procedure for solving a type of problem.
Lemma:– A 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.