# Solution

Show that the product of two integers of the form $4k+1$ is again of this form, while the product of two integers of the form $4k+3$ is of the form $4k+1$.

Part I.
Suppose $a = 4k_1+1$ and $b=4k_2+1$ for some integers $k_1$ and $k_2$. Consider their product: \begin{align}ab &= (4k_1+1)(4k_2+1)\\ &= 16k_1 k_2 + 4k_1 + 4k_2 + 1\\ &= 4(4k_1 k_2 + k_1 + k_2) + 1\end{align} We know that $(4k_1 k_2 + k_1 + k_2)$ must be an integer due to the closure of the integers under addition and multiplication. So defining $k_3 = (4k_1 k_2 + k_1 + k_2)$, we see that the product $ab$ can be written as $4k_3 + 1$ for some integer $k_3$. Thus, the product of two integers of the form $4k+1$ is again of this form.

Part II.
Suppose $a = 4k_1+3$ and $b=4k_2+3$ for some integers $k_1$ and $k_2$. Consider their product: \begin{align}ab &= (4k_1+3)(4k_2+3)\\ &= 16k_1 k_2 + 12k_1 + 12k_2 + 9\\ &= 16k_1 k_2 + 12k_1 + 12k_2 + 8 + 1\\ &= 4(4k_1 k_2 + 3k_1 + 3k_2 + 2) + 1\end{align} We know that $(4k_1 k_2 + 3k_1 + 3k_2 + 2)$ must be an integer due to the closure of the integers under addition and multiplication. So defining $k_3 = 4k_1 k_2 + 3k_1 + 3k_2 + 2$, we see that the product $ab$ can be written as $4k_3+1$ for some integer $k_3$. Thus, the product of two integers of the form $4k+3$ is of the form $4k+1$.