Prove that an odd integer is always of the form $2m+1$ 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?
 A: 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.
A: 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$.
A: 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
