Euclid's Division Algorithm

Euclid's division lemma states that for any two positive integers a and b, where a > b, there are integers q (quotient) and r (remainder) where:

\(a = bq + r (0 ≤ r < b).\)

For example, we can try to find the remainder and quotient of 72 ÷ 60.

Upon long division, we can divide the two numbers to get, 1 as its quotient and 12 as its remainder.

Let's see if this satisfies the Euclid's division algorithm.

Substitute the values of the quotient and remainder in the Euclid's division algorithm.

\(a = bq + r (0 ≤ r < b).\)

\(72 = 60 × 1 + 12\)

\(72 = 60 + 12 \)

\(72 = 72\)

L.H.S = R.H.S

Hence, proved.

Therefore, Euclid's division algorithm satisfies the given numbers.

Euclid’s division algorithm is the process of repeatedly applying Euclid’s division lemma several times, so that we can obtain the HCF of any two numbers. An algorithm is a sequence of steps used to achieve a specific task. 

Let us now assume that there are two numbers a and b. By applying Euclid’s Division Lemma, we will get the quotient and remainder, which are in the form
 
a = b(q) + r.

Here, the common factors of a and b are also factors of r. 

To prove that, let us assume that an integer k is a common factor of both a and b. 

Now, by dividing the above relation on both sides by k, we have:

\(\frac ak = \frac bk (q) + \frac rk \\[1em] \frac ak - \frac bk (q) = \frac rk\)

Since k is a common factor of both a and b, the left side is clearly an integer. Therefore, the right side is also an integer. Thus, r must be divisible by k.

This equation helps us in understanding Euclid’s Division Algorithm.

Euclid's division algorithm uses a repeated long division method to simplify the problem until the GCD or HCF is found. We have to keep on dividing the previous divisor by the remainder we got, until the remainder becomes 0. Let's understand this with the help of the example given below:

E.g., find the HCF of 168 and 408

Step 1: Applying Euclid's division lemma on the given numbers

\(408 = 168 × 2 + 72 \)

Step 2: The HCF of 408 and 168 must also be the HCF of 168 and 72

\(168 = 72 × 2 + 24\)

Step 3: Again, here the HCF is a common factor of 168 and 72, which must also be a common factor of 24

\(72 = 24 × 3 + 0\)
 

Step 4: If the remainder is 0, it means the last non-zero remainder is the HCF. This is because in Euclid's division algorithm, when the remainder becomes 0, it means we’ve found the HCF. Therefore, the HCF is 24.

Hence, 24 is the highest possible common factor of 168 and 408.

Let us now try to generalize Euclid’s division algorithm. Let us assume we need to find the HCF of any two arbitrary numbers, a and b. 

Apply Euclid’s Division Lemma repeatedly until we get the value of the remainder as zero.

\(a=b(q_1)+r_1 \\[1em] b=r_1(q_2)+r_2 \\[1em] r_1=r_2(q_3)+r_3 \\[1em] ⋮ \\[1em] r_{n−2}=r_{n−1}(q_n)+r_n \\[1em] r_{n−1}=r_n(q_{n+1})+0\)

The remainder of the second-to-last step is the remainder. 

That is, \(HCF (a, b) = r_n\)

In order to prove this, we must first show that \(r_n\) is indeed a common factor of a and b. Then we should show that any common factor of a and b must also be a factor of \(r_n\). This would support, that \(r_n\) is the highest common factor of a and b.

We can also find the HCF of two numbers using the long division method. We will use this method to write the steps of Euclid's division algorithm. 

Let us perform the long division method and write the steps of Euclid's division algorithm. 

Let us take the example of the numbers 320 and 132.

The divisor of the last step, which leads to the remainder zero, is the HCF.

Therefore, from the division method, we found that the HCF(320, 132) = 4.

Here are some easy and affective tips and tricks for the students to master Euclid's division algorithm, which will useful for them to learn number theory:
 

• Understand that the algorithm is basically based on repeated division. Keep dividing the previous divisor by the remainder until the remainder becomes 0.
   
• Always keep the order right. Out of the two numbers, we have to take the largest number as 'a' and the smallest number as 'b'.
   
• Each step should follow the same pattern of the algorithm. Do not switch the places of the remainder and the quotient. 
   
• Once the remainder is 0, stop immediately. The previous remainder is the HCF.
   
• For large numbers, Instead of doing prime factorization (which can be time-consuming), use Euclid’s Algorithm. It’s faster and works even for big numbers.
   
• Parents and teachers can start teaching Euclid’s division algorithm using a story to help students understand it effectively. Tell them,  “Euclid said that his algorithm is just a simple way of repeatedly subtracting or dividing to find the HCF.”
   
• Before formally teaching the algorithm, teachers should develop the habit of always dividing the larger number by the smaller one. This will help the students avoid confusion while dealing with tougher problems.
   
• Parents can try to connect the algorithm to real life. We can ask the children to split crayons equally and divide pencils among themselves. Then ask, “How many are left over?” Finally, we can use the remainders to explain the algorithm to them the right way.
   
• Teachers can use the concept of number shrinking to explain it to to students. Tell them that each step makes the numbers smaller and smaller. We would stop calculating when the remainder becomes zero.

Euclid’s division algorithm is used in various aspects of everyday life, and some of them are mentioned below:

• Used in carpeting, tiling, and packaging to get help with the sizes and dimensions. E.g., using the algorithm to find the perfect square tile for a floor of size 168 cm × 408 cm helps save time and avoids gaps or overlaps.

• The algorithm plays an important role in determining the GCD in RSA encryption. In this method, large prime numbers are utilized to form secure keys. 

• While cutting and measuring, Euclid’s division algorithm helps in cutting anything into equal pieces with no leftovers or overlaps. 

• It helps in solving puzzles that involve step cycles and repeated actions by identifying and simplifying common patterns.

• In software and game development, it helps in reducing processing time for tasks involving repeat patterns, grids, and loops.