# Prove that if n is odd, then n=4k+1 for some k in ZZ or n=4k+3 for some k in ZZ?

## I'm stuck! I know I need to use cases, I'm just not sure how to work them out.

Feb 18, 2017

Here's a basic outline:

Proposition: If $n$ is odd, then $n = 4 k + 1$ for some $k \in \mathbb{Z}$ or $n = 4 k + 3$ for some $k \in \mathbb{Z}$.

Proof: Let $n \in \mathbb{Z}$ where $n$ is odd. Divide $n$ by 4.

Then, by division algorithm, $R = 0 , 1 , 2 ,$ or $3$ (remainder).

Case 1: R=0. If the remainder is $0$, then $n = 4 k = 2 \left(2 k\right)$.

$\therefore n$ is even

Case 2: R=1. If the remainder is $1$, then $n = 4 k + 1$.

$\therefore n$ is odd.

Case 3: R=2. If the remainder is $2$, then $n = 4 k + 2 = 2 \left(2 k + 1\right)$.

$\therefore n$ is even.

Case 4: R=3. If the remainder is $3$, then $n = 4 k + 3$.

$\therefore n$ is odd.

$\therefore n = 4 k + 1 \mathmr{and} n = 4 k + 3$ if $n$ is odd ∎