# The integer $m$ is odd if and only if there exists $q \in \mathbb{Z}$ such that $m = 2q + 1$

The integer $m$ is odd if and only if there exists $q \in \mathbb{Z}$ such that $m = 2q + 1$.

Proof.

We have to prove both ways.

Suppose $m$ is odd, then by definition of odd number, $m = 2q+1$ for some $q \in \mathbb{Z}$.

Suppose $m = 2q + 1$, then $m$ is not divisible by $2$ so it's odd.

This is the way I proved it but not sure if I did it right. Any help please?

• Sadly, I don't think that's what your instructor wants. – Jorge Fernández Hidalgo Apr 6 '16 at 1:55
• This is basically a particular case of the uniqueness of the euclidean algorithm. – Jorge Fernández Hidalgo Apr 6 '16 at 1:56
• Is that actually the definition of odd number? It could be but I doubt it is. An odd number is one that isn't divisible by 2. BTW how do you know 2q+1 isn't divisible by 2? (And if a number isn't divisible by 2 how do you know it is expressible as 2q+1?) – fleablood Apr 6 '16 at 1:59

It seems to me that you are assuming what you want to prove.

Definition. An integer $n$ is said to be even if there exists an integer $k$ such that $n = 2k$. An integer that is not even is said to be odd.

Division Algorithm. Let $n, d \in \mathbb{Z}$, with $d \neq 0$. Then there exist integers $q$ (the quotient) and $r$ (the remainder) such that $n = dq + r$, where $0 \leq r < |d|$.

Assume $m$ is odd. By the Division Algorithm, there exist integers $q$ and $r$, with $0 \leq r < 2$ such that $m = 2q + r$. There are only two non-negative integers less than $2$. They are $0$ and $1$. If $r = 0$, then $m = 2q$, so $m$ is even, contrary to our hypothesis that $m$ is odd. Hence, $r = 1$. Therefore, $m = 2q + 1$.

Assume there exists $q \in \mathbb{Z}$ such that $m = 2q + 1$. Since the integers are closed under multiplication, $2q$ is an integer. Since the integers are closed under addition, $m = 2q + 1$ is an integer. Observe that $$m = 2\left(q + \frac{1}{2}\right)$$ Since $q$ is an integer, $q + 1/2$ is not an integer. Thus, $m \neq 2k$ for some integer $k$. Hence, $m$ is not even, so it is odd.