Modular Congruence with prime factorization! Show that if $n$ is a natural number and $n$ is congruent to $3 \pmod 4$ then one of the prime factors of $n$ must also be congruent to $3 \pmod 4$.
I honestly don't know where to begin with this problem. It doesn't intuitively make sense to me. Why would one of its prime factors also be congruent to $3 \pmod 4$? This problem right now tells me $4 \mid n - 3$ and I need to somehow manipulate it into looking like $4 \mid P^e - 3$ for some $P^e$ in the domain of prime numbers. Help appreciated!
 A: The most direct answer is that the integers are mapped via a ring homomorphism to the residues mod 4, and that a product of 1's maps to 1 (so if all the primes are 1 mod 4, their product can be taken mod 4, and a product of all 1's is itself 1).
This can also be seen explicitly. Let $n=p_1*\cdots*p_k$ be a product of odd primes (a factor of 2 implies a product not congruent to 3 mod 4). Then, assuming these are all 1 mod 4, $n=(4m_1+1)*\cdots*(4m_k+1)$. It is easy to see when expanding this product, that only one term does not have 4 as a factor, and this term is 1. So we have 1 plus a multiple of 4, which is 1 mod 4.
A: Best possible way is Method of Contradiction.
Suppose that all the factors of $n$ are of the form $$0\mod 4$$ or $$1\mod 4$$ or $$2\mod 4.$$ Then it can be easily show that $n$ is also of one of the above form. 
A: For intuition maybe it's best to go back to the numbers.
n can be 3, 7, 11, 15, 19, 23, 27, 31, 35.....etc, 3 more than multiples of 4.
The primes in the list are clearly 4m + 3, so they're OK.
Of the rest, 15 has prime factor 3, 27 has 3, 35 has 7. So they're OK.
Composites have to have a 4m + 3 factor. If they didn't, they'd all have to be 4m + 1 types. But you can product up 4m + 1 types until you're blue in the face and never get a 4m + 3 type.
