Euclid's division lemma and its applications

The lemma itself. For any two positive integers $a$ and $b$, there exist unique whole numbers $q$ and $r$ such that

where: $a$ is the dividend, $b$ is the divisor, $q$ is the quotient, and $r$ is the remainder. The word "unique" matters — for a given pair $(a,b)$ there is exactly one $q$ and one $r$ satisfying the equation, which is why long division always gives one definite answer, never several.

Reading the inequality. The condition $0 \le r < b$ is doing real work: the remainder can be $0$ (division comes out exact) but it can never reach or exceed the divisor — if it did, you could divide once more, so $q$ would not be the largest possible quotient. This is the single most tested detail of the whole topic.

From lemma to algorithm. Apply the lemma once and you get one quotient-remainder pair. Apply it repeatedly, each time dividing the previous divisor by the previous remainder, and you get Euclid's Division Algorithm — a step-by-step machine for computing $\text{HCF}(a,b)$ for $a > b$. The chain looks like $a = bq_1 + r_1$, then $b = r_1q_2 + r_2$, then $r_1 = r_2q_3 + r_3$, and so on, until some remainder is exactly $0$. The last divisor used at that final exact step — equivalently, the last non-zero remainder in the chain — is the HCF.

Why it terminates. Because $0 \le r < b$ forces every new remainder to be strictly smaller than the divisor it came from, the sequence of remainders $r_1 > r_2 > r_3 > \cdots$ is a strictly decreasing sequence of whole numbers bounded below by $0$. A strictly decreasing sequence of whole numbers cannot go on forever, so a remainder of $0$ must eventually appear — the algorithm is guaranteed to stop.

Show that any positive odd integer is of the form $6q+1$, $6q+3$, or $6q+5$ for some whole number $q$, and use it to classify $1001$.

Step 1. Let $a$ be any positive integer and divide it by $6$. By Euclid's Division Lemma, $a = 6q + r$ with $0 \le r < 6$, so $r \in \{0,1,2,3,4,5\}$ — there are exactly six possible remainders on division by $6$, giving the six forms $6q,\ 6q+1,\ 6q+2,\ 6q+3,\ 6q+4,\ 6q+5$.

Step 2. Sort these six forms by parity. $6q$ is even (a multiple of $6$), $6q+2 = 2(3q+1)$ is even, and $6q+4 = 2(3q+2)$ is even — each is a multiple of $2$. The remaining three forms are each an even number plus an odd number: $6q+1$, $6q+3$, $6q+5$ are odd.

Step 3. Conclude the general result: since every positive integer falls into exactly one of the six forms, and only three of them are odd, every positive odd integer must be of the form $6q+1$, $6q+3$, or $6q+5$.

Step 4. Apply it to $1001$. Divide: $1001 = 6 \times 166 + 5$, so $q = 166$ and $r = 5$. Since $1001$ is odd and matches the form $6q+5$, the classification is consistent — a quick check like this is exactly how the algorithm gets used on unseen numbers in an exam.

$1001$ is of the form $6q+5$ with $q = 166$, confirming it is odd.

Competitive stretch

The same idea, run with divisor $3$ instead of $6$, proves a fact used constantly in number theory: every perfect square is of the form $3m$ or $3m+1$, never $3m+2$. Divide any integer $a$ by $3$: $a = 3q+r$ with $r \in \{0,1,2\}$, so $a^2$ becomes $(3q)^2 = 3(3q^2)$, $(3q+1)^2 = 3(3q^2+2q)+1$, or $(3q+2)^2 = 3(3q^2+4q+1)+1$ — every case lands on remainder $0$ or $1$, never $2$. The lemma is the engine behind this and every similar "square is of the form..." result.

• Writing the inequality as $0 \le r \le b$ instead of $0 \le r < b$ — the remainder can equal $0$ but must be strictly less than the divisor, never equal to it.
• Dividing in the wrong order at a later step of the algorithm — at each stage you divide the previous divisor by the previous remainder, not the other way around.
• Stopping one step too early and reporting a quotient, or a still-nonzero remainder, as the HCF — the answer is the last non-zero remainder, found only once some remainder is exactly $0$.
• Mixing up Euclid's Division Lemma for integers with the division algorithm for polynomials — same name pattern, unrelated chapters; only the integer version belongs here.

Ask the tutor: Want to try the algorithm on a fresh pair of numbers, or see the $3m$/$3m+1$ square-classification proof worked out in full? Ask the AI tutor to walk through one with you.