Question

Use Euclid's division lemma to show that any positive odd integer is of the form $6q+1$, or $6q+3,6q+5$ where $q$ is some integers.

Answer 1

According to Euclid's division lemma, there exist integers $a,b,q$ and $r$ such that

$a=bq+r$, where $0\le r<b$

Now let us assume, $b=6$

Then we have,

$a=6q+r$, where $0\le r<6$

thus, $r$ can take values $0,1,2,3,4,5$

Consider the equation, $a=6q+r$

Case 1: When $r=0$

Thus, $a=6q$

Rewriting the above equation, we have

$a=2\left(3q\right)$

Hence $a$ is an even number

Case 2: When $r=1$

Thus, $a=6q+1$

Rewriting the above equation, we have

$a=2\times 3q+1$

$=2m+1$, where $m=3q$

Hence $a$ is an odd number

Case 3: When $r=2$

Thus, $a=6q+2$

Rewriting the above equation, we have

$a=2\times (3q+1)$

$=2m$, where $m=3q+1$

Hence $a$ is an even number

Case 4: When $r=3$

Thus, $a=6q+3$

Rewriting the above equation, we have

$a=2\times (3q+1)+1$

$=2m+1$, where $m=3q+1$

Hence $a$ is an odd number

Case 5: When $r=4$

Thus, $a=6q+4$

Rewriting the above equation, we have

$a=2\times (3q+2)$

$=2m$, where $m=3q+2$

Hence $a$ is an even number

Case 6: When $r=5$

Thus, $a=6q+5$

Rewriting the above equation, we have

$a=2\times (3q+2)+1$

$=2m+1$, where $m=3q+2$

Hence $a$ is an odd number

Therefore, any positive odd integer is of the form $6m,6m+1$ or $6m+5$, where $m$ is some integer.