## Congruence question

My name is George Wooding I sat your algebra 3 course last term.

I have a question. I do not understand why all numbers that are congruent to 3 mod 4 must have one of their prime number factors be congruent to 3 mod 4.

Any help would be great thanks,

George Wooding

Firstly, if $n\equiv 3 \ mod \ 4$, then $n$ is not even so all prime factors are congruent to 1 or 3 mod 4. Now here is the point: because congruence classes are compatible with ordinary arithmetic, the product of any collection of numbers that are congruent to 1 mod 4 is still congruent to 1 mod 4. Now do you see the reason? In fact, you might be able to see that the number of prime factors $\equiv 3 \ mod \ 4$ is *odd*.