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?
