Show that if $n\equiv 3\pmod{4}$, then $n$ has a prime factor $p\equiv 3\pmod{4}$
My approach:
By definition any composite number can be represented as a product of primes, so let $n=p_1\cdots p_k$. $$p_1\cdots p_k \equiv 3\pmod{4}$$
If there is not such prime number then all primes are congruent to either 1 or 2 mod 4 which can't be possible hence there is no way to get $3\pmod{4}$ by multiplying something 1 or 2 $\pmod{4}$
I think this is very informal, so I am just wondering if there is a way to express my idea with a better mathematical argument
Best Answer
Suppose that $n$ does not have a prime factor $p\equiv 3\bmod 4$. By assumption then all prime factors have to be odd, and congruent $1$ modulo $4$. However, then also the product is congruent $1$ modulo $4$, a contradiction. The computation is as follows (this is where you are too informal, perhaps). If $p=4n+1$ and $q=4m+1$, then $$pq=4(4nm+n+m)+1\equiv 1 \bmod 4.$$