Divisibility Proofs Using Euclid's Lemma | Class 10 Maths

Quick answer: Euclid's division lemma says that for positive integers $a$ and $b$, there are unique integers $q$ and $r$ with $a = bq + r$ and $0 \le r < b$. Using it, every integer can be written in a few forms (such as $3q$, $3q + 1$, $3q + 2$), and checking each form proves results like $n^3 - n$ is divisible by $6$ and $n^2 - 1$ is divisible by $8$ for odd $n$.

When you divide one positive integer by another, you get a quotient and a remainder smaller than the divisor. This simple fact, known as Euclid's division lemma ($a = bq + r$), is useful for much more than finding the HCF. It is also a powerful tool for proving divisibility results about integers.

For example, why is $n^3 - n$ divisible by $6$ for every positive integer $n$? Why is $n^2 - 1$ always divisible by $8$ when $n$ is odd? And why can a perfect square never leave a remainder of $2$ or $3$ when divided by $5$? Euclid's division lemma answers all three.

Syllabus note: In the current rationalised NCERT textbook, Euclid's division lemma has been removed from Class 10 Chapter 1 (Real Numbers), which now focuses on the Fundamental Theorem of Arithmetic. These proofs still appear in NCERT Exemplar, older board papers and competitive exams, and they are excellent practice in logical proof writing. Check your current syllabus before your exam.

What You Will Learn

• The statement of Euclid's division lemma: $a = bq + r$, $0 \le r < b$
• How to write any integer in forms such as $2q$, $2q + 1$ or $4q + 1$, $4q + 3$
• Proof 1: $n^3 - n$ is divisible by $6$ for every positive integer $n$
• Proof 2: $n^2 - 1$ is divisible by $8$ if $n$ is an odd positive integer
• Proof 3: the square of any positive integer cannot be of the form $5q + 2$ or $5q + 3$
• How to present number theory proofs clearly in exams

1. Euclid's Division Lemma

Statement

Given positive integers $a$ and $b$, there exist unique integers $q$ and $r$ such that $a = bq + r, \quad 0 \le r < b$

Choosing a value of $b$ lets us write every integer in a small number of forms:

Useful fact: $4q$ and $4q + 2$ are even, so every odd integer is of the form $4q + 1$ or $4q + 3$.

2. Proof 1: $n^3 - n$ Is Divisible by 6

Question

Prove that $n^3 - n$ is divisible by $6$ for every positive integer $n$.

Proof

Step 1: Factorise.

$n^3 - n = n(n^2 - 1) = (n - 1)\,n\,(n + 1)$

So $n^3 - n$ is the product of three consecutive integers.

Step 2: Show it is divisible by 2. Of any two consecutive integers, one is even. Since $n - 1$ and $n$ are consecutive, one of them is divisible by $2$. So $(n - 1)n(n + 1)$ is divisible by $2$.

Step 3: Show it is divisible by 3. By Euclid's division lemma with $b = 3$, $n$ is of the form $3q$, $3q + 1$ or $3q + 2$.

• Case 1, $n = 3q$: $n$ itself is divisible by $3$.
• Case 2, $n = 3q + 1$: $n - 1 = 3q$ is divisible by $3$.
• Case 3, $n = 3q + 2$: $n + 1 = 3q + 3 = 3(q + 1)$ is divisible by $3$.

In every case, one of the three factors is divisible by $3$, so $(n - 1)n(n + 1)$ is divisible by $3$.

Step 4: Combine. Since $2$ and $3$ are co-prime ($\text{HCF}(2, 3) = 1$), a number divisible by both $2$ and $3$ is divisible by $2 \times 3 = 6$.

Hence proved: $n^3 - n$ is divisible by $6$ for every positive integer $n$.

3. Proof 2: $n^2 - 1$ Is Divisible by 8 for Odd $n$

Question

Prove that $n^2 - 1$ is divisible by $8$ if $n$ is an odd positive integer.

Proof

Step 1: Write the odd integer in the right form. By Euclid's division lemma with $b = 4$, any positive integer is of the form $4q$, $4q + 1$, $4q + 2$ or $4q + 3$. Since $n$ is odd, it cannot be $4q$ or $4q + 2$. So:

$n = 4q + 1 \quad \text{or} \quad n = 4q + 3, \quad \text{where } q \ge 0$

Step 2: Case 1, $n = 4q + 1$.

$n^2 - 1 = (4q + 1)^2 - 1 = 16q^2 + 8q + 1 - 1 = 16q^2 + 8q = 8(2q^2 + q)$

So $n^2 - 1$ is divisible by $8$.

Step 3: Case 2, $n = 4q + 3$.

$n^2 - 1 = (4q + 3)^2 - 1 = 16q^2 + 24q + 9 - 1 = 16q^2 + 24q + 8 = 8(2q^2 + 3q + 1)$

So $n^2 - 1$ is divisible by $8$.

Hence proved: $n^2 - 1$ is divisible by $8$ for every odd positive integer $n$.

Alternative method: You can also write $n = 2q + 1$. Then $n^2 - 1 = 4q(q + 1)$. Since $q$ and $q + 1$ are consecutive, $q(q + 1)$ is even, so $4q(q + 1)$ is divisible by $8$. This works too, but you must state why $q(q + 1)$ is even.

4. Proof 3: A Square Cannot Be of the Form $5q + 2$ or $5q + 3$

Question

Prove that the square of any positive integer cannot be of the form $5q + 2$ or $5q + 3$ for any integer $q$.

Proof

Step 1: By Euclid's division lemma with $b = 5$, any positive integer $a$ is of the form $5m$, $5m + 1$, $5m + 2$, $5m + 3$ or $5m + 4$.

Step 2: Square each form.

Step 3: The square of a positive integer can only be of the form $5q$, $5q + 1$ or $5q + 4$.

Hence proved: the square of any positive integer cannot be of the form $5q + 2$ or $5q + 3$.

5. Summary Table

6. Exam Tips and Common Mistakes

Exam Tip: When you state Euclid's division lemma, always include the condition $0 \le r < b$. Leaving it out can cost you a mark.

Exam Tip: Using $n = 4q + 1$ and $n = 4q + 3$ for odd numbers lets you take out the factor $8$ directly, which keeps the proof short.

Common Mistake: Concluding divisibility by $6$ without saying that $2$ and $3$ are co-prime. Divisibility by two numbers implies divisibility by their product only when the numbers are co-prime.

Remember: Any three consecutive integers contain at least one multiple of $2$ and exactly one multiple of $3$.

Frequently Asked Questions

What is Euclid's division lemma?

For any two positive integers $a$ and $b$, there exist unique integers $q$ and $r$ such that $a = bq + r$, where $0 \le r < b$.

Why is n³ − n always divisible by 6?

Because $n^3 - n = (n - 1)n(n + 1)$ is a product of three consecutive integers. It always contains a multiple of $2$ and a multiple of $3$, so it is divisible by $6$.

Why is n² − 1 divisible by 8 when n is odd?

Every odd number is of the form $4q + 1$ or $4q + 3$. In both cases, $n^2 - 1$ simplifies to $8$ times an integer.

Can a perfect square be of the form 5q + 2?

No. The square of any positive integer is of the form $5q$, $5q + 1$ or $5q + 4$, never $5q + 2$ or $5q + 3$.

Is Euclid's division lemma in the current Class 10 syllabus?

It has been removed from the rationalised NCERT Class 10 textbook, but it is still useful for NCERT Exemplar practice, older board papers and competitive exams.