# Prove: Dividing an odd number by 2 always produces a remainder of 1

How would I go about proving that for all n belonging to the natural numbers, if any given odd number n is divided by 2, then the remainder is at least 1?

I got a hint: Try to reduce the number of n, but I have no idea how that would help.

I was thinking along the lines of induction, but what would be the best approach to this? I just want hints, please. I want to solve this myself, just need a heads up on where to get started.

• Do you mean odd number? – Hovercouch Oct 23 '13 at 0:30
• Yeah, I do actually. Sorry about that, I corrected it @Hovercouch – Daniel Cook Oct 23 '13 at 0:31
• How are you defining "odd number"? – Dan Oct 23 '13 at 0:33
• Usually the following is taken as the definition of an odd number, so I'm not sure if this qualifies as a 'hint', but here goes: an odd number is one of the form $2k + 1$ for some integer $k$. – tylerc0816 Oct 23 '13 at 0:37

Let $n$ be our number, such that $n = 2m + r$, m and r whole numbers. If $r < 1$, then it has to be zero. In which case we just have $n = 2m$ and n isn't odd any more. If $r>1$, then if it's even r is divisible by two so $2|(2m+r)$, meaning n isn't odd anymore. If r is odd, then we can write it as $s+1$, s is even, and $n = 2(m + s/2) + 1$, meaning 1 is the new remainder.
The division algorithm says that for any $m$ and positive $n$ in the integers, there are integers $q$ and $0\le r\lt n$ so that $$m=qn+r$$ For $n=2$, there are two remainders ($0\le r\lt2$): $0$ and $1$.
$m$ is odd if it is not divisible by $2$ (the remainder when dividing by $2$ is not $0$). Since there is only one non-zero remainder, the remainder when dividing $m$ by $2$ must be $1$.