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?
Best Answer
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$.
The other proof is fine.