# Show that if $m \equiv 3 \mod 4$, then $m$ has a prime factor $p \equiv 3 \mod 4$.

So the question goes as follows:

(1) Show that a natural number that is congruent to 3 mod 4, has a prime factor that is congruent to 3 mod 4.

(2) Show that there are infinitely many prime numbers that fulfill $p \equiv 3 \mod 4$.

I have already tried to answer them, but would like to know if what I've done is correct:

(1) Since $m \equiv 3 \mod 4$ we have that all prime factors of $m$ are odd. Now suppose for contradiction that all the prime factors of $m$ are congruent to 1 mod 4. To get to a contradiction we have to prove that $m$ is also congruent to 1 mod 4. Let $p = 4a + 1$ and $q = 4b + 1$. Then we have that $pq = (4a + 1)(4b + 1) = 4(4ab + a + b) + 1 \equiv 1 \mod 4$. We now have our contradiction and can say that has a $m$ prime factor $p \equiv 3 \mod 4$.

(2) Suppose for contradiction that there is a finite amount of prime numbers $(\{p_1, p_2, \ldots, p_n\})$ that are congruent to 3 mod 4.

Consider the number $q = -1 + 4(p_1 p_2 \ldots p_n)$. Since $p_m$, $m = 1, 2, \ldots, n,$ divides $4(p_1 p_2 \ldots p_n)$, then none of them divides $q$.

We also have that $q mod 4 = 4(p_1 p_2 \ldots p_n) -1 \equiv -1 \mod 4 \equiv 3 \mod 4$.

So pr. (1) we have that q has a primefactor that is congruent to 3 mod 4. Since none of the prime numbers {p1,p2,…,pn} are factors in q we have that q itself is a prime number that is congruent to 3 mod 4, which is a contradiction since we stated that we had already listed all of the prime numbers that are congruent to 3 mod 4.

Are these proofs valid enough?

• Welcome to MSE. For some basic information about writing mathematics at this site see, e.g., basic help on mathjax notation, mathjax tutorial and quick reference, main meta site math tutorial and equation editing how-to. Sep 18, 2018 at 10:00
• "we have that q itself is a prime number that is congruent to 3 mod 4" this doesn't have to be true, the claim is too strong, we claim that there exists a prime that divides $q$, that is congruent to $1$ modulo $4$, but it can't be any of the primes from our set, this is the contradiction Sep 18, 2018 at 10:04
• @Rumpelstiltskin, Just saw the edit :). Also thank you that makes sense! Sep 18, 2018 at 10:08
• I just wrote you the claim :) But I had a mistake, I meant that the prime is congruent to $3$ modulo $4$ of course. Now it's too late to edit it Sep 18, 2018 at 10:09

Your proof of the first statement is incomplete, since you only deal with numbers which can be written as the product of two prime numbers. The idea is fine, though. It is easy to prove by induction that the product of any number of numbers congruent to $$1$$ modulo $$4$$ is again congruent to $$1$$ modulo $$4$$.