# Prove that $\frac{p-1}{2}$ is odd iff, $p \equiv 3 \pmod{4}$ + Intuition

Let $p$ be an odd prime. Prove that $\frac{p-1}{2}$ is odd iff, $p \equiv 3 \pmod{4}$.

I was thinking about it this way: If $(p-1)/2$ is supposed to be even, then $(p-1)$ must be divisible by $2\cdot2 = 4$, i.e. $p-1 \equiv 0 \pmod{4} \Leftrightarrow p \equiv 1 \pmod{4}$. It follows that if $\frac{p-1}{2}$ is odd, $p$ must be in any residue class other than $1$, including $3$ of course. So this was a little confusing to me; why does the theorem explicitly ask for $p$ to be congruent $3$ modulus $4$ and not, say congruent $2$? However, by experimenting i figured out that apparently all primes $p$ are either congruent to $1$ or $3$ $\pmod{4}$. My suspicion is that this is because $4$ is even and all primes $\geq 3$ are obviously odd; however, i have no intuition about numbers whatsoever and this is all a little opaque to me. A little clarification on this issue would be nice.

Now for the actual proof: Let $p$ be an odd prime and $p \equiv 3 \pmod{4}$ then $p = 4k + 3$ for a $k \in \mathbb{N}$. Now just substitute this for $p$ in in the given fraction, then $\frac{p-1}{2} = \frac{4k+2}{2} = 2k + 1$ and that's it for this direction of the the proof. How to prove the other direction? I don't know! This should be really easy, but all my attemps failed.

• why don't you try showing that for the other case ($p\equiv 1 (\text{mod 4})$) you get an even number? And your intuition is correct: the only even prime is $2$, thus no primes $\ge 3$ can be written as $4k+2 \ , \ k\in\mathbb{N}$ i.e are equal to $2 (\text{mod 4})$ – b00n heT Feb 5 '15 at 18:34
• "+ Intuition"?? Are you sure it says "intuition" in your question? – Timbuc Feb 5 '15 at 18:34
• @b00nheT this works analogously to what i already showed, but i don't see how this completes the proof. – jazzinsilhouette Feb 5 '15 at 18:38
• @Timbuc what are you getting at? – jazzinsilhouette Feb 5 '15 at 18:39

Let's think about the numbers through a $\bmod 4$ filter.

For any natural number $n$, there are exactly four possibilities:

• $n\equiv 0 \bmod 4$
• $n\equiv 1 \bmod 4$
• $n\equiv 2 \bmod 4$
• $n\equiv 3 \bmod 4$

If $n\equiv a\bmod 4$, there is some integer $k$ such that $n=4k+a$. That also means that given $a<4$, the nearest lower multiple of $4$ from $n$ is $n-a$.

Clearly if $n\equiv 0 \bmod 4, n$ is even.

If $n\equiv 2 \bmod 4, n = 4k+2 = 2(2k+1)$ and $n$ is again even.

If $n\equiv 1 \bmod 4, n = 4k+1 = 2(2k)+1, n$ is odd but $\frac{n-1}{2} = (2k)$ is even.

If $n\equiv 3 \bmod 4, n = 4k+3 = 2(2k+1)+1, n$ is odd and $\frac{n-1}{2} = (2k+1)$ is also odd.

We can also see that if $\frac{n-1}{2}$ is odd, ie. $\frac{n-1}{2} = (2k+1)$, then $n=2(2k+1)+1 = 4k+3 \equiv 3 \bmod 4$.

Note also that your assertion does not depend particularly on whether the chosen number is prime.

Hint $\,\ \ \dfrac{p-1}2\,$ odd $\iff \dfrac{p-1}2 \,\in\, 1\!+\!2\,\Bbb Z \iff p-1\,\in\, 2\!+\!4\,\Bbb Z\iff p\,\in\, 3+4\,\Bbb Z$