Prove that an odd integer is always of the form $2m+1$

Question

I have that by definition an integer $n$ is even if $n = 2m$ for some integer $m$. By definition an integer is odd if it is not even. I would like to prove that if $n$ is odd, then $n = 2m + 1$ for some $m$.

I am supposed to show this using at little as possible about the properties of the integers. I don't, for example, know anything about division algorithms like Euclidean division.

I can show that all numbers of the form $2m + 1$ are odd, but how can I show that all integers that are odd are indeed of this form?

Do you know anything about modular arithmetic? That'd be a straightforward way to prove it. — DylanSp, Feb 18 '16 at 19:16
@DylanSp: I would also like to try an avoid this. But I am guessing that it ends up looking a lot like this anyway. I would like a proof that doesn't make references to modular arithmetic or division. — John Doe, Feb 18 '16 at 19:17
Maybe you could try to do it by induction then. But if you want to avoid induction… — Watson, Feb 18 '16 at 19:18
This is similar to this question of mine: Prove that no positive integer is both even and odd, and that all positive integers are either even or odd. https://math.stackexchange.com/questions/476184/prove-that-no-positive-integer-is-both-even-and-odd-and-that-all-positive-integ — marty cohen, Feb 18 '16 at 21:00

score 3 · Accepted Answer · answered Feb 18 '16 at 19:19

Let $n$ be odd, i.e. an integer that is not even. Let $k$ be the largest even integer less than or equal to $n$. Since $k$ is even there is some integer $m$ with $k=2m$. Consider $n-k$, an integer (because it is the difference of two integers). It is nonnegative, because $k\le n$. It is not zero, since otherwise $k=n$ and then $n$ would be even. If $n-k\ge 2$, then $n\ge k+2$ and hence $k+2$ would be larger than $k$, less than or equal to $n$, and even. [Proof: $k+2=2m+2=2(m+1)$.] This contradicts the choice of $k$, so is impossible.

The only integer that is greater than zero and less than two is one. Hence $n-k=1$, so $n=k+1=2m+1$ for some integer $m$, as desired.

score 1 · Answer 2 · answered Feb 18 '16 at 19:35

If you know the division algorithm (theorem), then every integer can be written in the form $2m+r$ where $m,r$ are integers and $0\le r<2$. I.e. as $2m$ or as $2m+1$. By this result, the integers that are odd are not of the form $2m$ and hence of the form $2m+1$.

miniparser · Answer 3 · 2016-02-18T20:29:27.120

0

induction on odd integers

prove
$n\in Z$ is odd $\Rightarrow\exists_{m\in Z}{n=2m+1}$

base case of $n=1:1=2(0)+1$. assume true for all n: $n=2m+1$. next odd number is $n+2=2m+1+2=2(m+1)+1$

it holds for all $0 \le n$ odd $\in Z$ by induction

edited Feb 18 '16 at 20:29

answered Feb 18 '16 at 20:03

miniparser

1,197

Prove that an odd integer is always of the form $2m+1$

3 Answers3