Prove that all values $n$ which are odd can be written in one of two forms: $4q+1$, $4q+3$ with a non-negative integer $q$? How can I prove that all values $n$ which are odd can be written in one of the following two forms: $4q+1$, $4q+3$ with a non-negative integer $q$?
 A: Hint: Take $n$ to be an odd number and look at the remainder when you divide by $4$.
A: 
$4q+1=2(2q)+1,~$ and $~4q+3=2(2q+1)+1$.


Basically, all odds are of the form $2n+1$, and all numbers $($like n, for instance$)$, are either even or odd. So just take $n=2q$, and $n=2q+1$, and see what happens in each case.
A: Any number $n$ is of the form $4k$, $4k + 1$, $4k + 2$ or $4k + 3$, but $4k = 2(2k)$ and $4k + 2 = 2(2k + 1)$ are even, so any odd number is of the form $4k + 1$ or $4k + 3$. It is not hard to see by the same reasoning that if $n$ is prime, then it must be of the form $6k + 1$ or $6k + 5$.
A: Not all values of $n$ which are odd can be written in one of those two forms if you insist that $q$ be non-negative. For example, $n = -7$ is certainly odd, but to represent it as $4q + 1$ requires $q = -2$. Or maybe you meant that all positive odd $n$ can be represented in one of those two forms with a non-negative $q$.
Each integer $n$ can be represented in the form $4q + r$ where $q$ and $r$ are also integers and $0 \leq r < 4$. There are only four possible values for $r$.
Clearly $4q + 0$ and $4q + 2$ are even. That leaves $4q + 1$ and $4q + 3$ for the odd $n$. To find what $q$ is, just see whether $$\frac{n - 1}{4}$$ or $$\frac{n - 3}{4}$$ is an integer.
