Show that any positive odd integer is of the form 6q + 1, or 6q + 3, or 6q + 5, where q is some integer.

Let a be any positive integer and b = 6. Then, by Euclid’s algorithm,

a = 6q + rfor some integer q ≥ 0, and r = 0, 1, 2, 3, 4, 5 because 0 ≤ r < 6.

Therefore, a = 6q or 6q + 1 or 6q + 2 or 6q + 3 or 6q + 4 or 6q + 5

Also, 6q + 1 = 2 × 3q + 1 = 2k₁ + 1, where k₁ is a positive integer

6q + 3 = (6q + 2) + 1 = 2 (3q + 1) + 1 = 2k₂ + 1, where k₂ is an integer

6q + 5 = (6q + 4) + 1 = 2 (3q + 2) + 1 = 2k₃ + 1, where k₃ is an integer

Clearly, 6q + 1, 6q + 3, 6q + 5 are of the form 2k + 1, where k is an integer.

Therefore, 6q + 1, 6q + 3, 6q + 5 are not exactly divisible by 2. Hence, these expressions of numbers are odd numbers.

And therefore, any odd integer can be expressed in the form 6q + 1, or 6q + 3,

or 6q + 5

Let  'a' be any +ve integer.

Also suppose there exists two +ve integers q and r as quotient and remainder respectively when 'a' is divided by 6. 

Then , 

By using Euclid's Division lemma, we get 

        a = 6q + r .................( A ) , where  0 ≤ r < 6.

Obviously,  r = 0 or 1 or 2 or 3 or 4 or 5.

Case-(i) When r = 0 , then from ( A ) we have 

a = 6q + 0 

=> a = 6q = 2×3q = 2m ^{_{= Even number , where}}  m ^{_{= 3q}}

Case-(ii) When r = 1 , then 

a = 6q + 1 = 2(3q) + 1 = 2m + 1 = odd number, where m = 3q.

Case-(iii) When r = 2 then 

a = 6q + 2 = 2(3q + 1) = 2m_{1 ^{= Even}} , where m1 ^{= 3q + 1.} 

Case-(iv) When r = 3 then 

a = 6q + 3 = 2(3q + 1) + 1 = 2m₁ + 1= odd number, where m₁ = 3q + 1

Case-(v) When r= 4 then

a = 6q + 4 = 2(3q + 2) = 2m₂ = Even , where m_{2 = 3q +2 .}

Case -(vi) When r = 5 then 

a = 6q + 5 = 2(3q + 2) + 1 = 2m₂ + 1 = odd number, where m_{2 ^{= 3q + 2.}}

Clearly from above cases ( ii ) , ( iv ) and ( vi ) we conclude that any +ve odd integer is of the form 6q + 1 or 6q + 3 or 6q + 5.