Lemma
A lemma is a proven statement used for proving another statementEuclid’s division Lemma
a = bq + r, 0 ≤ r < b.
➢ This is a restatement of the long division process, and that the integers q and r are called the quotient and remainder respectively.
➢ It was first recorded in Book VII of Euclid’s Elements.
➢ Euclid’s division algorithm is based on this lemma.
Algorithm
An algorithm is a series of well defined steps which gives a procedure for solving a type of problem.The word algorithm comes from the name of the 9th century Persian mathematician Muhammad ibn Musa al-Khwarizmi (C.E. 780 – 850) . Even the word ‘algebra’ is derived from a book, he wrote, called Hisab al-jabr w’al-muqabala .
Euclid’s division algorithm,
"Any positive integer a can be divided by another positive integer b in such a way that it leaves a remainder r that is smaller than b."➧ Series of steps based on Euclid's division lemma is used to obtain the required result.
➧ Euclid’s division lemma/algorithm has several applications related to finding properties of numbers.
➧ It is mainly applied to compute the Highest Common Factor (HCF) of two given positive integers.
➧ It is one of the earliest examples of an algorithm that a computer had been programmed to carry out.
➧ Although Euclid’s Division Algorithm is stated for only positive integers, it can be extended for all integers except zero, i.e.,b ≠ 0.
HCF of two Positive Integers
To obtain the HCF of two positive integers, say u and v, with u > v, we follow the steps below:Step 1 : Apply Euclid’s division lemma, to u and v. So, we find whole numbers, q and
r such that u = vq + r, 0 ≤ r < v.
Step 2 : If r = 0, v is the HCF of u and v. If r ≠ 0, apply the division lemma to v and r.
Step 3 : Continue the process till the remainder is zero. The divisor at this stage will be the required HCF.
Q)Use Euclid’s division algorithm to find the HCF of : 135 and 225.
(A) Step 1 : Since 225 > 135, we apply the division lemma to 225 and 135, to get
225 = 135 × 1 + 90
Step 2 : Since the remainder 90 ≠ 0, we apply the division lemma to 135 and 90, to get
135 = 90 ×1 + 45
Step 3 :We consider the new divisor 90 and the new remainder 45, and apply the division lemma to get
90 = 45 × 2 + 0
The remainder has now become zero, so our procedure stops. Since the divisor at this stage is 45, the HCF of 225 and 135 is 45.
| Real Numbers | |