Euclid’s division lemma/algorithm has several applications related to finding properties of numbers. We give some examples of these applications below:

Example: Show that every positive even integer is of the form ${2q}$, and that every positive odd integer is of the form ${2q + 1}$, where ${q}$ is some integer.

Solution : Let ${a}$ be any positive integer and ${b = 2}$. Then, by Euclid’s algorithm, ${a = 2q + r}$, for some integer ${q ≥ 0}$, and ${r = 0}$ or ${r = 1}$, because ${0 ≤ r < 2}$ . So, ${a = 2q}$ or ${2q + 1}$.
If ${a}$ is of the form ${2q}$, then ${a}$ is an even integer. Also, a positive integer can be either even or odd. Therefore, any positive odd integer is of the form ${2q + 1}$.


Example: Show that any positive odd integer is of the form ${4q + 1}$ or ${4q + 3}$, where ${q}$ is some integer.

Solution : Let us start with taking ${a}$, where ${a}$ is a positive odd integer. Apply the division algorithm with ${a}$ and ${b = 4}$.
Since ${0≤ r < 4}$ , the possible remainders are 0, 1, 2 and 3.
That is, ${a}$ can be ${4q}$, or ${4q + 1}$, or ${4q + 2}$, or ${4q + 3}$, where ${q}$ is the quotient. However, since ${a}$ is odd, ${a}$ cannot be ${4q}$ or ${4q + 2}$ (since they are both divisible by 2). Therefore, any odd integer is of the form ${4q + 1}$ or ${4q + 3}$.


Example: A sweetseller has 420 kaju barfis and 130 badam barfis. She wants to stack them in such a way that each stack has the same number, and they take up the least area of the tray. What is the number of that can be placed in each stack for this purpose?

Solution : Since, we have to distribute each of the items i.e 420 kaju barfis and 130 badam barfis in box ,such a way that each boxes contains equal numbers of barfies.
In this problem, we have to find greatest number that divides each one of the following exactly.
So, this is a problem of HCF.
Now, let us use Euclid’s algorithm to find their HCF. We have :

420 = 130 × 3 + 30

130 = 30 × 4 + 10

30 = 10 × 3 + 0

So, the HCF of 420 and 130 is 10.
Therefore, the sweetseller can make stacks of 10 for both kinds of barfi.