# Help with easy proof

My name is Dennis and I need help solving.

Show that if $n\in\mathbb Z$ is odd, then $n$ is of the form $4q+1$ or $4q+3$ for some $q\in\mathbb Z$.

Now I know this is true so can't use a proof by contradiction.

However I believe I can proof this by proving that $4q+1$ or $4q+3$ is not even thus it must be odd.

Below is my work it will not be the greatest for I have been away from math for some years.

Suppose to the contrary that $n$ is even. consider $n$ to be even and we know an even integer is of the form $n=2k$ let $k=2q$ and we assume that $n=2(2q)+1$ or if rewritten $n=2k+1$ therefore $n=2k+1\neq n4q+1$ and $4q+1$ and $4q+3$ are odd.

-
You are proving that if $n$ is of that form then $n$ is odd. You're supposed to be proving that if $n$ is odd then it is of that form. – Gerry Myerson Sep 6 '11 at 13:11
so I need to prove that all odd numbers of Z are in this form. How would I do that, I would think that I would prove all even numbers or not of this form. – Dennis Hayden Sep 6 '11 at 13:21
"Now I know this is true so can't use a proof by contradiction." A proof by contradiction doesn't usually prove false statements :). – Srivatsan Sep 6 '11 at 14:38
O I seem to have misunderstood stood the use of that way of doing a proof. – Dennis Hayden Sep 6 '11 at 14:44

Let $n$ be an arbitrary odd number; we want to show that $n$ has the form $4q+1$ or $4q+3$.

But what does an "odd number" mean? It means something of the form $2m+1$ (for a whole number $m$), so the assumption is really $$n=2m+1$$

Now, $m$ itself is either even or odd. If we can show that no matter whether $m$ even or od then $n$ has one of the required forms, we will be through. If $m$ is even then $m=2k$ for some $k$, so $$n=2m+1=2(2k)+1=4k+1$$ Then $k$ works as the $q$ we were looking for, which completes this case of the proof.

On the other hand, if $m$ is odd, that means $m=2k+1$ for some $k$, and then $$n=2m+1=2(2k+1)+1=4k+2+1=4k+3$$ Then again $k$ works as $q$, and the proof is finished.

Alternative proof. We can also show the required implication in "contrapositive" form:

If $n$ does not have one of the forms $4q+1$ or $4q+3$, then $n$ is even.

We can always divide $n$ by 4 and get an integral quotient and remainder instead of continuing into decimans. This allows us to express any $n$ as $$n=4q+r$$ where $r$ is either zero or a positive number less than $4$, that is, one of the numbers 0, 1, 2, or 3. By assumption $r=1$ and $r=3$ cannot be the case, so we have either $n=4q+0$ or $n=4q+2$. In either case $n$ is the sum of two even numbers ($4q$ is always even, and 0 and 2 are also even), and that means that $n$ is even too.

-
And, if needed, we can prove that the sum of two even numbers is even...(+1) ;) – The Chaz 2.0 Sep 6 '11 at 14:16

We can either $n$ divide by $4$.

That is, write $n=4q+r$, where $r,q\in\mathbb N$ and $r<4$. We have four options:

• $r=0$, then $n$ is divisible by $4$, which makes it even.
• $r=1$, then $n$ is indeed of the form $4q+1$.
• $r=2$, then $n=4q+2$ which is the sum of two even numbers ($4q$ is even).
• $r=3$, then $n=4q+3$.

Since $n$ is odd we have that either $r=1$ or $r=3$, and we are done.

-

If the remainder x when dividing by 4 was 4 or greater, 4 could be subtracted from x and 1 added to q until a remainder <4 is obtained. The possibilites for n are then 4q, 4q+1,4q+2 and 4q+3. 4q=2(2q) and 4q+2=2(2q+1), therefore n is even if n is not of the form 4q+1 or 4q+3.

-
So I should be using the division algorithm? to prove that for when n is odd the "remainder is odd as well?" – Dennis Hayden Sep 6 '11 at 13:48

You can use proof by contradiction. Namely, suppose for contradiction that $\rm\:n\:$ is odd and not of the form $\rm\:4\:k+1\:$ or $\rm\:4\:k+3\:.\:$ By the Division algorithm we may write $\rm\: n = 4\ q + r\$ for $\rm\ 0 \le r \le 3\:.\:$ By hypothesis $\rm\: r \ne 1,3\:$ so $\rm\:r = 0\ or\ 2\:$ is even, so $\rm\:n = 4\ q + r\:$ is even, contra hypothesis. $\$ QED

More generally one can show that if $\rm\:m\:$ is even then $\rm\:m\ q+r\:$ is odd $\:$ iff $\rm\ r\:$ is odd, simply because even + r = odd iff r is odd. This implies that the sense of "parity" descends from integers to integers modulo $\rm\:m\:,\:$ i.e. they have well-defined parity since it depends only on the remainder $\rm\:r\:,\:$ not on the quotient $\rm\:q\:.\:$ Further, all the usual rules of parity arithmetic also descend to the ring of integers modulo $\rm\:m\:,\:$ for example: $\:$ odd + even = odd, $\:$ odd^2 = odd,$\:$ etc - just as for integers. In fact there are many rings which similarly have a sense of parity, e.g. the Gaussian integers $\:\mathbb Z[i]\:$ where $\: a + b\ i\$ is even iff both $\:a\:$ and $\:b\:$ have the same parity. See this post for further discussion. Many of these matters will become clearer if one studies abstract algebra, esp. the concept of quotient rings, which generalizes the "modular" construction of the ring of integers modulo $\rm\:m\:.$

-
This is a very good post and helps me see I am clearly missing some basic understanding. My ability to write proofs is very weak. I believe I better start working on this if I aim to do well in this abstract algebra class. – Dennis Hayden Sep 6 '11 at 15:21