Euclid’s Division Lemma & Algorithm

Euclid’s Division Lemma and Algorithm are fundamental concepts in number theory, particularly used to find the Highest Common Factor (HCF) of two positive integers. The lemma provides the foundation, while the algorithm provides a systematic method for calculating the HCF. The core idea revolves around repeatedly dividing a larger number by a smaller number and analyzing the remainders.

Formulae

Euclid’s Division Lemma: For any two positive integers, ‘a’ (dividend) and ‘b’ (divisor), there exist unique integers ‘q’ (quotient) and ‘r’ (remainder) such that:

$a = bq + r$, where $0 \le r < b$

Euclid’s Division Algorithm:

Apply the Division Lemma to ‘a’ and ‘b’.
If the remainder, $r = 0$, then the HCF is ‘b’.
If the remainder, $r \ne 0$, then apply the Division Lemma to ‘b’ (the previous divisor) and ‘r’ (the previous remainder).
Repeat the process until the remainder becomes 0. The divisor at this stage is the HCF.

Examples

Example-1: Find the HCF of 455 and 42.

Applying Euclid’s Division Lemma: $455 = 42 \times 10 + 35$
Since the remainder is not 0, apply the lemma to 42 and 35: $42 = 35 \times 1 + 7$
Again, the remainder is not 0, apply the lemma to 35 and 7: $35 = 7 \times 5 + 0$
The remainder is now 0. Therefore, the HCF of 455 and 42 is 7.

Example-2: Find the HCF of 135 and 225.

Applying Euclid’s Division Lemma: $225 = 135 \times 1 + 90$
Since the remainder is not 0, apply the lemma to 135 and 90: $135 = 90 \times 1 + 45$
Again, the remainder is not 0, apply the lemma to 90 and 45: $90 = 45 \times 2 + 0$
The remainder is now 0. Therefore, the HCF of 135 and 225 is 45.

Theorem with Proof

Theorem: Euclid’s Division Lemma: Given positive integers a and b, there exist unique integers q and r satisfying a = bq + r, where $0 \le r < b$.

Proof:

Let ‘a’ and ‘b’ be any two positive integers. Consider the multiples of ‘b’: $0, b, 2b, 3b, …$. Since ‘a’ is also a positive integer, ‘a’ will either be one of the multiples of ‘b’, or it will lie between two consecutive multiples of ‘b’.

If ‘a’ is a multiple of ‘b’, then $a = qb + 0$, where q is an integer and r = 0.

If ‘a’ lies between two multiples of ‘b’, let’s say $qb < a < (q+1)b$. Then, we can write 'a' as $a = qb + r$, where r is the difference between 'a' and 'qb'. Since $qb < a < (q+1)b$, subtracting $qb$ from all parts, we get $0 < r < b$. Thus, in this case, $0 < r < b$. If a = (q+1)b, then r would be 0.

Therefore, we can always express ‘a’ in the form $a = bq + r$, where $0 \le r < b$. The uniqueness of q and r arises from the fact that there's only one possible remainder for a given divisor.

Common mistakes by students

Incorrect Division: Making errors in the division process, leading to incorrect quotients and remainders.
Stopping Too Early: Stopping the algorithm before the remainder reaches 0.
Misidentifying the HCF: Incorrectly identifying the HCF (e.g., the last quotient instead of the last non-zero divisor).
Forgetting the Remainder Condition: Not understanding or applying the condition $0 \le r < b$.

Real Life Application

Euclid’s algorithm has applications in various real-life scenarios, including:

Cryptography: Used in algorithms for encrypting and decrypting messages.
Computer Science: Used in generating pseudo-random numbers and simplifying fractions.
Scheduling problems: Finding optimal time slots in a cyclic process.

Fun Fact

Euclid’s algorithm is one of the oldest algorithms known, dating back to ancient Greece. It’s mentioned in Euclid’s “Elements,” written around 300 BC. Despite its age, it remains a powerful and efficient method for finding the HCF.