# Problem #4

**Question**: prove that every odd natural number is of one of the forms $4n+1$ or $4n+3$, where $n$ is an integer.

**Claim**: every odd natural number is of one of the forms $4n+1$ or $4n+3$, where $n$ is an integer.

**Proof**: by the General Division Theorem, all integer numbers can be presented as $bn+r$, where $b \neq 0$ and $0 \leq r < |b|$. Let's take $b=4$, then $0 \leq r < 4$ and we will get that all integer numbers can be in one of those forms:

$$\begin{equation} 4n+0 \end{equation} $$

$$\begin{equation} 4n+1 \end{equation} $$

$$\begin{equation} 4n+2 \end{equation} $$

$$\begin{equation} 4n+3 \end{equation} $$

By the definition of odd number, we can conclude that all odd integers can be in one of the forms:

$$\begin{equation} 4n+1 \end{equation} $$

$$\begin{equation} 4n+3 \end{equation} $$

And because this works for odd integers, it works for odd natural numbers as well, as natural numbers is the subset of integers, so every odd natural number is of one of the forms $4n+1$ or $4n+3$, where $n$ is an integer. $\blacksquare$