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


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?

  • 1
    $\begingroup$ Sadly, I don't think that's what your instructor wants. $\endgroup$ – Jorge Fernández Hidalgo Apr 6 '16 at 1:55
  • 1
    $\begingroup$ This is basically a particular case of the uniqueness of the euclidean algorithm. $\endgroup$ – Jorge Fernández Hidalgo Apr 6 '16 at 1:56
  • 5
    $\begingroup$ 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?) $\endgroup$ – 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.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.