# 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

## 3 Answers

We can show that it's exactly one.

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

Dividing an odd integer by the prime two does not always give a remainder of plus one, which is just one. Depending on the dividend, the uneven integer being divided by two, the remainder can be minus one. But there is the condition that the quotient, Q has to be an uneven integer. How is this the case ? If the definition of " remainder " is accepted as the number to be algebraically added to the product of quotient and divisor to reproduce the dividend, then remainders, r of + 1 and - 1 result quite naturally. For example, 39 = 2.19 + [+ 1], but 37 = 2.19 + [- 1] The respective remainders are + 1 and - 1. The general case is D = 2.Q + i^{1 + D} Here, D and Q are uneven numbers, considered as positive and " i " satisfies: i^{2} = - 1. Two is the divisor. The exponent: {1 + D} to which " i " is raised, is an even number that always gives a real remainder. Note that if {1 + D} is divisible by four, then the remainder is + 1, but if {1 + D] is only divisible by two, then the remainder is - 1. Rearranging the general case: Q = [D - i^{1 + D}]/2, it is apparent that the quotient, Q depends only on the dividend, D. This is not a proof that remainder upon division of an uneven integer by two, can be either - 1 or + 1, but the result is seen to be self-evident. Proof of the above. Taking D = 4.k + 1 or D = 4.k + 3 is the place where to start. [a] D = 4.k + 1 gives: 4.k + 1 = [4.k + 2] + [ - 1] = 2.[2.k + 1] + [ - 1] Here, Q = [2.k + 1] and r = - 1. [b] D = 4.k + 3 gives: 4.k + 3 = [4.k + 2] + [ + 1] = 2.[2.k + 1] + [ + 1] In this case, Q = [2.k + 1] and r = + 1. Setting i^{1 + D} gives identical results for [a] and [b].