If $n \equiv 3 \pmod{4}$ then there is a prime $p$ such that $p \equiv 3 \pmod{4}$ and $p \mid n$.

Question

Let $n \in \mathbb{N}$ such that $n \equiv 3 \pmod{4}$. Prove that there exists a prime $p$ such that $p \equiv 3 \pmod{4}$ and $p \mid n$.

I'm seriously confused on this problem. Wouldn't $p$ have to be equal to $n$? Any suggestions on how to approach this would be great

Answer 1

Try the contrapositive:

If for all primes factors $p$ of $n$ we have $p\equiv 1 \bmod 4$, then $n\equiv 1 \bmod 4$.

This follows directly from

If $x,y \equiv 1 \bmod 4$, then $xy \equiv 1 \bmod 4$

which is easy to prove.

A final detail is that if $p=2$ is a factor of $n$, then we can't have $n\equiv 3 \bmod 4$.

Answer 2

Assume to the contrary that all prime divisors of $n$ is of the form $4k+1$ ( we can eliminate the cases $p = 4k, 4k+2$ since both forms yield composite $p$. Thus taking product we have: $n = p_1^{n_1}\cdot p_2^{n_2}\cdots p_k^{n_k}=(4s_1+1)^{n_1}\cdots (4s_k+1)^{n_k}= 1\pmod 4$, contradiction. Thus the result follows.