3
$\begingroup$

The exercise is to prove this proposition using the following lemmas:

1) Prove Lemma A: every prime ≠ 2 is either of the form $4n + 1$ or $4n + 3$

2) Prove Lemma B: the product of numbers of the form $4n + 1$ is of the form $4n + 1$.

I'll omit the proofs of the lemmas, since I'm not doubtful about their demonstrations. Again I ask if there is any flaw on the following proof.

Proof:

Suppose, by contradiction, that there are finitely many primes of the form $4n + 3$, say, $p_1, p_2, ..., p_k.$ Define $N = 4p_1...p_k - 1 = 4(p_1...p_k - 1) + 3.$ $N$ > $p_k$ and is of the form $4n + 3$, therefore is not prime. So $N$ must be divisible by some prime. Since $N$ is not divisible by any $p_i$ or 2, this prime divisor must be > $p_k$ and consequently, due to lemma A, of the form $4n + 1$. Now, the fundamental theorem of arithmetic states that any non-prime number must be factorable in prime numbers. Since $N$ is not divisible by any $p_i$, there must be primes $f_1, ..., f_l$ on which $N$ is factorable. From the hypothesis and from lemma A follows that these primes must be of the form $4n + 1$ and, by lemma B, so must be $N$, a contradiction.

|cite|improve this question
$\endgroup$
  • $\begingroup$ Your proof looks good, however you may be interested in the following strategy: Define N as you did, and show that it must be divisible by a prime of the form 4n + 3 or be a prime itself, a contradiction. It is essentially what you have there but in one fewer step. $\endgroup$ – Yushwuth Aug 2 '16 at 2:11
  • $\begingroup$ I don't see why it should be divisible by a prime of the form 4n + 3. It surely should be divisible by a prime or be a prime itself, but how can you justify the restriction about the form? $\endgroup$ – izzorts Aug 2 '16 at 2:15
  • $\begingroup$ A prime number must either be of the form 4n + 3, or 4n+1, because otherwise it is divisible by two. Because you have constructed a number of the form 4n + 3, it is either a prime number itself, or divisible by some other prime numbers. But if these other prime numbers were all of the form 4n+1, this is a contradiction since the product of such numbers must be of the form 4n+1. Thus the number has a prime factor less than it of the form 4n + 3, a contradiction since the finitely many primes listed do not divide it. $\endgroup$ – Yushwuth Aug 2 '16 at 2:17
3
$\begingroup$

Your proof is good, however consider the following(slightly shorter) version:

Suppose there are finitely many primes of the form $4n + 3$, call them $p_1, p_2, \dots p_k$. Then consider $$N = 4(p_1p_2\dots p_k) - 1$$ This is still of the form $4n + 3$ since it is congruent to $-1 \equiv 3(\mod 4)$. Note also that none of the $p_i$ divide $N$. Thus, $N$ is either prime or composite. If $N$ is prime, we reach a contradiction since it is a new prime of the desired form. Suppose $N$ is composite, then there must be a prime of the form $4n+3$ dividing it by your lemma, also a contradiction since none of the $p_i$ divide $N$.

This proof is nearly identical to yours, however the thing to note is that you can just leave it in the form $4k - 1$ since this is equivalent to $4(k-1) + 3$.

|cite|improve this answer
$\endgroup$
1
$\begingroup$

The proof is sound, depending on the course you may be asked (at the very least should be readily able to) justify the statement

"N is not divisible by any $p_i$, or 2.

Otherwise looks good.

|cite|improve this answer
$\endgroup$
  • $\begingroup$ Indeed. By the way, since it was a guided proof, it was to be taken for granted that it was the case (and intuitively it seems true). So I gave it a thought and find that it's not divisible by 2 because it's odd (which is quite immediate), and not divisible by any $p_i$ (which is not that obviously justifiable) because if you divide $N = 4p_1...p_k - 1$ by any $p_i$ you will necessarily come to a rational. $\endgroup$ – izzorts Aug 2 '16 at 2:25

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.