2
$\begingroup$

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?

$\endgroup$
  • $\begingroup$ Do you know Euclidean division? $\endgroup$ – Watson Feb 18 '16 at 19:10
  • $\begingroup$ @Watson: no ... $\endgroup$ – John Doe Feb 18 '16 at 19:11
  • $\begingroup$ Do you know anything about modular arithmetic? That'd be a straightforward way to prove it. $\endgroup$ – DylanSp Feb 18 '16 at 19:16
  • $\begingroup$ @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. $\endgroup$ – John Doe Feb 18 '16 at 19:17
  • $\begingroup$ Maybe you could try to do it by induction then. But if you want to avoid induction… $\endgroup$ – Watson Feb 18 '16 at 19:18
2
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ Nice I like this. Thanks. $\endgroup$ – John Doe Feb 18 '16 at 19:24
0
$\begingroup$

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$.

$\endgroup$
0
$\begingroup$

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

$\endgroup$

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.