I have this question in one of my assignments of a course(MIT 6042) that I am pursuing online. Question is as follows:
Problem 6. [20 points] In this problem you will prove that there are an infinite number of
primes!(a) [6 pts] As a warm-up, prove that there are an infinite number of prime numbers. (Hint: Suppose that the set F of all prime numbers is finite, that is $F = \{p_1, p_2, \ldots , p_k\}$ and define $n = p_1p_2 \cdots p_k + 1$)
(b) [2 pts] Prove that if $p$ is an odd prime, then
$p \equiv 1 \pmod 4$ or $p \equiv 3 \pmod 4$.(c) [6 pts] Prove that if $n \equiv 3 \pmod 4$, then $n$ has a prime factor $p \equiv 3 \pmod 4$. Problem Set 3 3
(d) [8
pts] Let $F$ be the set of all primes $p$ such that $p \equiv 3 \pmod 4$. Prove by contradiction that $F$ has an infinte number of primes. (Hint:
Suppose that $F$ is finite, that is $F = \{p_1, p_2, \ldots , p_k\}$ and define $n = 4p_1p_2\cdots p_k − 1$. Prove that there exists a prime $p_i \in F$ such that $p_i\mid n$.)
I have thought about the problem, and I am near to the solution but I can't figure out how to write it down in a proper way.
Part(a): I followed the hint and assumed $n = p_1p_2 \cdots p_k + 1$. As the smallest prime number is $2$ and $n$ is $1$ more than a multiple of $p_1$ or $p_2$ or… $p_k$, $n$ is not divisible by any $p_i \in F$. Thus $n$ is itself a prime, contradicting our assumption.
Part(b): For this part, I assumed if $n$ is odd then $n \equiv 1 \pmod 4$ or $n \equiv 3 \pmod 4$ as an axiom. And then I proved the theorem rather trivially.
Part(c): For this I know that if $n \equiv 3 \pmod 4$ then $n$ has an odd number of prime factors $p_i$ such that $p \equiv 3 \pmod 4$. I know the logic behind this but I am having trouble writing it down. But if this statement is wrong then please let me know.
Part(d): I followed the hint in this part as well and I assumed $n = 4p_1p_2\cdots p_k − 1$. Now $n \equiv 3 \pmod 4$, intuitively, thus from part (c) $n$ has a prime factor $p$ such that $p \equiv 3 \pmod 4$ and such $p$ must belong to $F$ by our assumption. However smallest prime in $F$ is $3$ and $n$ is just $1$ (not $3$ or more) less than a multiple of any $p_i \in F$, thus none of the $p_i \in F$ divides $n$, which contradicts our assumption.
Can anyone tell me if there is anything wrong with any of my proofs and how to write them down properly.
Thanks.
Best Answer
You're correct, by and large. Some of your wording is a bit odd.
Part a) has generated a bit of controversy because your phrasing could mean several slightly different things. "Thus $n$ itself is prime" should probably read "Thus $n$ is not divisible by any prime", and that contradicts (the easy half of) the Fundamental Theorem of Arithmetic.
Part b): you don't "assume $n \equiv 1$ or $n \equiv 3 \pmod 4$ as an axiom". You deduce it as a fact, since things $0$ or $2 \pmod{4}$ are even.
Part c): The thing to note here is that if you multiply two things which are $3 \pmod{4}$ together, you get something $1 \pmod{4}$. Therefore multiplying any even number of things $3 \pmod{4}$ together will yield something $1 \pmod{4}$.
Part d): don't use the word "intuitively" when you're proving something. When you're explaining a proof, great, intuition is always good. But when you're trying to convince someone that you know why something is formally true, "intuitively" is a big warning sign that actually you don't.
Otherwise you're correct.