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

Euclid's division lemma states that if we divide an integer by another integer (non-zero integer), we will get a unique integer as quotient and a unique integer as remainder.

## Answer: Euclid’s division lemma is used to show that any positive odd integer is of the form (6q + 1) or (6q + 3) or (6q + 5) where q is some integer.

Let's look into the solution below.

**Explanation:**

Euclid’s division lemma states that for two positive integers, a and b, there exists two unique integers, q, and r, such that:

a = bq + r, where 0 ⩽ r < b.

Let the positive integers be 'a' and 'b' and let b = 6.

Thus according to Euclid’s division lemma,

a = 6q + r, where 0 ⩽ r < 6 --------------- (1)

Thus, 'r' can take the values 0, 1, 2, 3, 4, 5.

Let's analyze the cases shown below for r = 1, r = 3 and r = 5.

(a) Substituting r = 1 in (1) we get,

a = 6q + 1

Since, 6q is always an even number, adding 1 to it will result in an odd number.

Hence, 6q + 1 will always be an odd number.

(b) Substituting r = 3 in (1) we get,

a = 6q + 3

Since, 6q is always an even number, adding 3 to it will result in an odd number.

Hence, 6q + 3 will always be an odd number.

(c) Substituting r = 5 in (1) we get,

a = 6q + 5

Since, 6q is always an even number, adding 5 to it will result in an odd number.

Hence, 6q + 5 will always be an odd number.