Odd Integer Modulo 4

Theorem

Let $n$ be an odd integer.

Then $n$ can be expressed either as:

$n = 4 k + 1$

or as:

$n = 4 k + 3$

Proof

By the Division Theorem, $n$ can be expressed as:

$n = 4 k + r$

where:

$k, r \in \Z$

$0 \le r < 4$

That is, one of the following holds:

\(\ds n\)

\(=\)

\(\ds 4 k\)

\(\ds n\)

\(=\)

\(\ds 4 k + 1\)

\(\ds n\)

\(=\)

\(\ds 4 k + 2\)

\(\ds n\)

\(=\)

\(\ds 4 k + 3\)

Of these:

\(\ds n\)

\(=\)

\(\ds 4 k\)

\(\ds \)

\(=\)

\(\ds 2 \paren {2 k}\)

and:

\(\ds n\)

\(=\)

\(\ds 4 k + 2\)

\(\ds \)

\(=\)

\(\ds 2 \paren {2 k + 1}\)

and so are even by definition.

Then:

\(\ds n\)

\(=\)

\(\ds 4 k + 1\)

\(\ds \)

\(=\)

\(\ds 2 \paren {2 k} + 1\)

and:

\(\ds n\)

\(=\)

\(\ds 4 k + 3\)

\(\ds \)

\(=\)

\(\ds 2 \paren {2 k + 1} + 1\)

and so are odd by definition.

$\blacksquare$

Sources

• 1980: David M. Burton: Elementary Number Theory (revised ed.) ... (previous) ... (next): Chapter $2$: Divisibility Theory in the Integers: $2.1$ The Division Algorithm: Problems $2.1$: $3 \ \text{(a)}$