Euclid's Division Lemma

Euclid’s division lemma states there are two positive integers a and b, where a ≥ b, there exists a unique set of integers q and r, such that:

a = bq + r

This lemma is the foundation of the Euclidean algorithm, used for computing the GCD of two numbers.  
 

The statement of Euclid’s division lemma for any two positive integers a and b, where a ≥ b, there exists a unique set of integers q and r, such that:
a = bq + r, where q is the quotient and r is the remainder, 0 ≤ r < b.

If two positive integers a and b satisfy a = bq + r, then any number that divides both a and b also divides b and q, and any number that divides both b and q also divides a and b.

Let us consider ‘c’ as the common divisor of ‘a’ and ‘b’, then:

\(c | a\), implies \(a = cq_1\) for some integer \(q_1\) and 

\(c | b\), implies \(b = cq_2\) for some integer \(q_2\)

Here, 

a = bq + r

Or, r = a – bq

Or, \(r=cq_1–cq_2q\)

Or, \(r=c(q_1–q_2q)\)

Or, \(c | r.\)

Or, \(c | r\) and \(c | b\)

Therefore, c is the common divisor of b and r.

Hence, a common divisor of a and b is a common divisor of b and r.

Let d be a common divisor of b and r. Then,

\(d | b\), or \(b=r_2d\) for some integers r1

\(d | r\), or, \(r=r_2d\) for some integers r2

Let us now show that d is the common divisor of a and b. 

We have, \(a = bq + r\)

Or, \(a=r_1dq+r_2d\)

Or, \(a=(r_1q+r_2)d\)

Or, \(d|a\)

That implies, \(d|a\) and \(d|b\)

Therefore, ‘d’ is the common divisor of ‘a’ and ‘b’.

Euclid’s division lemma is used to find the HCF of two given numbers. The steps to find the HCF of two numbers using Euclid’s division lemma is given below:

Let us take two numbers x and y for which we have to find the HCF using Euclid’s division lemma, such that x > y.

Step 1: First, we have to apply the Euclid’s division lemma to ‘x’ and ‘y’. We can find whole numbers, ‘q’ and ‘r’, such that x = yq + r, where 0 ≤ r < y.

Step 2: If r = 0, ‘y’ is the HCF of ‘x’ and ‘y’. If r is not equal to 0, apply the division lemma again to ‘y’ and ‘r’.

Step 3: Till the remainder is 0, this division continues. The divisor at this stage will be the required HCF.

To extend Euclid’s division algorithm, we apply it repeatedly to any two numbers 𝑎 and 𝑏. We have to continue using Euclid’s Division Lemma again and again, until the remainder becomes 0. The end process will give us the HCF.

\(a=b(q_1)+r_1\\[1em] b=r_1(q_2)+r_2\\[1em] r_1=r_2(q_3)+r_3\\[1em] r_n-2=r_n-1(q_n)+r_n\\[1em] r_n−1=r_n(q_n+1)+0\)

We will get that rn is the remainder in the second last step. Next, prove that every common divisor of a and b must also divide rn. Together, these two facts establish that rn is the highest common factor of a and b.

Here is a simple way to find the HCF. We use the long‑division method to do this, just as you learned in primary school. The steps of Euclid’s division algorithm are written in the same style. For example, to find the HCF of 120 and 96, we apply the familiar school formula using long division.

Dividend = Quotient x Divisor + Remainder

Let us consider two integers a and b, then there exists unique integers q and r, such that;

A = bq + r 

Where 0≤r<b.

If b completely divides a, then r = 0, otherwise, 0 < r < b.

Proof: 

Let us take an arithmetic progression like,

…., a − 3b, a − 2b, a − b, a, a + b, a + 2b, a + 3b, ….

This arithmetic progression has a common difference b, and extends indefinitely in both directions. 

Let r be the smallest non-negative term of this arithmetic progression. Therefore, there exists a non-negative integer q, such that:

a – bq = r,

a = bq + r

A and r are the smallest non-negative integers satisfying the above result. 

Therefore, 0≤r<b

Thus, we have a = bq + r, 

Where 0≤r<b

Now, we need to prove the uniqueness of ‘q’ and ‘r’.

a = bq + r, and \(a=bq_1+r_1\)

So, \(bq+r=bq_1+r_1\)

\(r_1–r=bq–bq_1\)

\(r_1=b(q–q_1)\)

Now, when \(b(q−q_1)=0\)

Then, \(r_1–r=0\)

That implies, \(r_1=r\)

Or, \(−r_1=−r\)

…By multiplying (-1) on both sides.

Or, \(a–r_1=a–r\)

…adding ‘a’ on both sides.

\(bq_1=bq\)

That implies, \(q_1=q\)

Mastering Euclid’s Division Lemma becomes easier with a few simple strategies. These tips help you apply the lemma quickly and accurately in solving division and HCF-related problems.
 

• Always remember the form a = bq + r, where 0 ≤ r < b.
   
• a is the dividend, b in the divisor, q is the quotient, and r is the remainder.
   
• Always ensure the remainder is smaller than the divisor.
   
• Practice with small numbers first in order to better grasp the pattern before moving to larger ones.
   
• If a number divides the product of two numbers, you can use the division lemma to check divisibility and solve problems involving factors and multiples efficiently.
   

• Teachers should start teaching Euclid’s division lemma with the meaning instead of teaching them the formula first. Before giving them the formula, tell them what it means. 
   

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

  
  Here, 
  a = the number being divided
  b = the number we divided by
  q = how many times b fits into a 
  r = what is left over. 
   

• Parents can make use of some examples that kids can understand immediately. Use sharing chocolates, dividing candies among friends, and packing markers in boxes as examples. For example, 30 chocolates divided among 4 kids, so that 4 kids get 7 each, and 2 are left over, can be written on Euclid’s division lemma as, 

  30 = 4 × 7 + 2

   

• Teachers can use concrete objects like marbles, blocks, coins, and beads to let learners physically divide objects into equal groups and count leftovers. This method helps in making the remainder theorem clear.

   

• Parents can make it a game for their children, so that they can learn faster. Ask them to write 3 lemmas in under 60 seconds, keep a competition on who can find the quotient faster, etc. 

Euclid's division lemma has practical uses in everyday life. Its applications vary from helping in dividing resources to technology enhancements. Let us take a look at some such uses.

 

• Finding HCF for Sharing: Helps in dividing items into equal groups without leftovers, like distributing sweets, pencils, or resources evenly among children or teams.
  
   
• Simplifying Fractions: Used to reduce fractions to their simplest form by finding the HCF of numerator and denominator.
  
   
• Scheduling Repeated Events: Helps determine common intervals for repeating events, like bus timings or rotating work shifts, using HCF.
  
   
• Cryptography and Security: Forms the basis for algorithms in encryption and secure communication, where number theory and HCF calculations are essential.
  
   
• Puzzle and Game Design: Useful in designing games and puzzles involving grouping or arranging objects in patterns without remainder, ensuring fairness and balance.