Question

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.

Answer 1

Here's a basic outline:

Proposition: If `n` is odd, then `n=4k+1` for some `k in ZZ` or `n=4k+3` for some `k in ZZ`.

Proof: Let `n in ZZ` 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=4k=2(2k)`.

`:. n` is even

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

`:. n` is odd.

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

`:. n` is even.

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

`:. n` is odd.

`:. n=4k+1 or n=4k+3` if `n` is odd ∎