Euclid's division lemma — Class 10 CBSE Mathematics MCQs with Solutions
Free Class 10 CBSE Mathematics Euclid's division lemma MCQs with step-by-step solutions (8 questions). Part of Real Numbers. Practise online on Prepizo — no login needed.
▶ Practise Euclid's division lemma online (free)
Questions with solutions
Q1 — Euclid's division lemma · easy · theory
In Euclid's division lemma, for positive integers $a$ and $b$, there exist unique integers $q$ and $r$ such that $a = bq + r$. The condition satisfied by $r$ is:
A. $0 < r < b$
B. $0 \le r < b$ ✓ Correct
C. $0 \le r \le b$
D. $1 \le r < b$
Solution: Euclid's division lemma states that for positive integers $a$ and $b$ there exist unique integers $q$ and $r$ with $a = bq + r$ and $0 \le r < b$. The remainder can be zero (when $b$ divides $a$ exactly) but must always be strictly less than the divisor $b$.
Q2 — Euclid's division lemma · easy · theory
Using Euclid's division algorithm, the HCF of $135$ and $225$ is:
A. $15$
B. $5$
C. $45$ ✓ Correct
D. $90$
Solution: Apply the algorithm step by step: $225 = 135 \times 1 + 90$, then $135 = 90 \times 1 + 45$, then $90 = 45 \times 2 + 0$. Since the remainder becomes $0$ when the divisor is $45$, the HCF of $135$ and $225$ is $45$.
Q3 — Euclid's division lemma · easy · theory
By Euclid's division lemma with $b = 2$, every positive even integer is of the form (where $q$ is some integer):
A. $2q$ ✓ Correct
B. $2q + 1$
C. $q + 2$
D. None of these
Solution: Taking $b = 2$ in $a = bq + r$ with $0 \le r < 2$, every positive integer is of the form $2q$ or $2q + 1$. The form $2q$ is divisible by $2$, so every positive even integer is of the form $2q$, while $2q + 1$ gives the odd integers.
Q4 — Euclid's division lemma · medium · theory
An army contingent of $616$ members is to march behind an army band of $32$ members, with both groups marching in the same number of columns. The maximum number of columns in which they can march is:
A. $4$
B. $8$ ✓ Correct
C. $16$
D. $32$
Solution: The maximum number of columns is HCF(616, 32). By Euclid's algorithm: $616 = 32 \times 19 + 8$ and $32 = 8 \times 4 + 0$, so the HCF is $8$. Hence they can march in at most $8$ columns.
Q5 — Euclid's division lemma · medium · theory
If the HCF of $65$ and $117$ is expressible in the form $65m - 117$, then the value of $m$ is:
A. $1$
B. $4$
C. $2$ ✓ Correct
D. $3$
Solution: By Euclid's algorithm: $117 = 65 \times 1 + 52$, $65 = 52 \times 1 + 13$, $52 = 13 \times 4 + 0$, so the HCF is $13$. Setting $65m - 117 = 13$ gives $65m = 130$, so $m = 2$.
Q6 — Euclid's division lemma · medium · theory
The largest number that divides $70$ and $125$ leaving remainders $5$ and $8$ respectively is:
A. $13$ ✓ Correct
B. $65$
C. $875$
D. $1750$
Solution: The required number must divide $70 - 5 = 65$ and $125 - 8 = 117$ exactly, so it is HCF(65, 117). By Euclid's algorithm: $117 = 65 \times 1 + 52$, $65 = 52 \times 1 + 13$, $52 = 13 \times 4 + 0$, giving HCF $= 13$.
Q7 — Euclid's division lemma · hard · theory
The square of any positive integer can never be of the form (where $m$ is an integer):
A. $3m$
B. $4m$
C. $3m + 2$ ✓ Correct
D. $3m + 1$
Solution: By Euclid's lemma any integer is $3q$, $3q + 1$ or $3q + 2$. Squaring each: $(3q)^2 = 3(3q^2)$, $(3q+1)^2 = 3(3q^2 + 2q) + 1$, and $(3q+2)^2 = 3(3q^2 + 4q + 1) + 1$. So a perfect square is always of the form $3m$ or $3m + 1$, never $3m + 2$; note that $4m$ is possible, e.g. $6^2 = 36 = 4 \times 9$.
Q8 — Euclid's division lemma · hard · theory
The largest number which divides $1251$, $9377$ and $15628$ leaving remainders $1$, $2$ and $3$ respectively is:
A. $575$
B. $450$
C. $750$
D. $625$ ✓ Correct
Solution: The number must exactly divide $1251 - 1 = 1250$, $9377 - 2 = 9375$ and $15628 - 3 = 15625$. Factorising: $1250 = 2 \times 5^4$, $9375 = 3 \times 5^5$ and $15625 = 5^6$. The common part is $5^4 = 625$, so the required largest number is $625$.