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 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.

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.

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.