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.

  • $\begingroup$ 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})$ $\endgroup$ – b00n heT Feb 5 '15 at 18:34
  • $\begingroup$ "+ Intuition"?? Are you sure it says "intuition" in your question? $\endgroup$ – Timbuc Feb 5 '15 at 18:34
  • $\begingroup$ @b00nheT this works analogously to what i already showed, but i don't see how this completes the proof. $\endgroup$ – jazzinsilhouette Feb 5 '15 at 18:38
  • 1
    $\begingroup$ @Timbuc what are you getting at? $\endgroup$ – 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$


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.