Question

Use division algorithm to show that any odd positive integer is of the form \[6q + 1\] or \[6q + 3\]or \[6q + 5\], where \[q\] is some integer.

Answer 1

Hint: We can prove this Euclid’s division lemma. According to Euclid’s division lemma if we have two positive integers a and b, then there exist unique integers a and b, then there exist unique integers q and r which satisfies the condition \[a = bq + r\] where \[0 \leqslant r \leqslant b\].

Complete step by step solution:
Let a be the positive odd integer which when divided by 6 gives q as quotient and r as remainder.
According to Euclid’s division lemma we can write \[a = bq + r\] where \[0 \leqslant r \leqslant b\].
Now comparing the coefficient of\[q\]in the algorithm and in the given problem we get \[b = 6\]
\[\therefore a = 6q + r - - - - \left( 1 \right)\]
Where, \[(0 \leqslant r < 6)\]
So, r can be either 0, 1, 2, 3, 4 and 5.
Case (1): if \[r = 1\] then equation \[\left( 1 \right)\] becomes
\[a = 6q + 1\]
The above equation will always be an odd integer.
Case (2): If \[r = 3\], then equation \[\left( 1 \right)\] becomes
\[a = 6q + 3\]
The above equation will always be an odd integer.
Case (3): If \[r = 5\], then equation \[\left( 1 \right)\]becomes
\[a = 6q + 5\]
The above equation will always be an odd integer.
Therefore, any odd integer is of the form \[6q + 1\] or \[6q + 3\]or \[6q + 5\], where \[q\]is some integer.
Hence proved.
So, the correct answer is “Option B”.

Note: The difference between Euclid’s division lemma and Euclid’s division algorithm is that Euclid’s division lemma is a proven statement used for proving another statement while an algorithm is a series of well-defined steps that give a procedure for solving a type of problem.