3
$\begingroup$

Basically I had to proves that there are infinite many primes congruent to $3$ modulo $4$, and the professor said "look at Euclid's proof for infinitude of primes"

So basically I did the following. Assume otherwise and assume there are finite many. Define $S={p_0,p_1,...,p_k}$With $p_0=3$. Then consider $x=4p_1...p_k+3.$ Since $x$ is congruent to $3$ modulo $4$ it suffices to show it would be a prime number, contradicting the fact that $S$ contained all such numbers. Note that no member of $S$ divides $x$, and that $2$ does not divide $x$. Note that $x$ is not a product of primes congruent to $1$ modulo $4$, because the product of such primes gives a number congruent to $1$ modulo $4$. Thus, $x$ is not divisible by any primes, so it should be prime. Contradiction because clearly $x\notin S$.

Now my problem is that I did not get credit for this proof because of the following: I wrote the sentence "$x$ is a prime", and they grader argued that $x$ is rarely going to be a prime, but my point is that if $S$ indeed contained all the primes, then we could construct another prime.

I did not get the points back, but I just want to know whether my proof is faulty. If so, why?

  • 1
    @Aryabhata: Presentation problem there certainly is. But I have taught Elementary Number Theory many times, and it certainly *looks* like conceptual problems I have seen students have. In any case, there is only very casually written text to go on, which could differ in important ways from what was written in the test or homework.2012-04-06

2 Answers 2

2

The way I see your argument:

If the set $S$ of primes of the form $4m+3$ is finite, say $S = \{3, p_1, p_2, \dots, p_k\}$ then $x = 4p_1p_2 \dots p_k + 3$ must be a prime. Since $x$ is of the form $4m+3$ and $x \notin S$ we have a contradiction.

Your presentation could have been better (for instance, Zev has interpreted it differently), but logically your proof seems reasonable. Of course, if we could see your proof verbatim (as you presented it to your professor), we could answer your query with more confidence.

People seem to have problems with the statement:

"Since no prime divides $x$, $x$ must be prime".

This statement is logically true, even though it might seem nonsensical.

This is because logically, any false statement implies any true statement.

You could have actually stopped at, "Since no prime divides $x$, we have a contradiction with the fact that $x$ is an integer $\gt 1$ and must have some prime factor".

So Zev's interpretation reads as "Assume P, therefore Q (which is actually false). Q implies R, which gives rise to a contradiction".

Even though Q implies R might seem nonsensical, it is actually logically correct (since Q is false), it is also redundant and again points to problems in the presentation: for instance, under that interpretation, the fact that Q is false and implies R hasn't been clarified. Of course, the same statement, I interpreted (and presume what you have intended) is

"Since no prime other than $x$ divides $x$ (and $x \gt 1$) , $x$ must be prime".

In which case, this seems reasonable without need for more clarification.

So in conclusion, I think your proof is essentially correct, but you could lose points for presentation.

I would definitely not call it ridiculous. I am guessing the professor has misread your proof, and is under the impression you are claiming that $x$ is always prime, irrespective of the finiteness of $S$ (which I believe is a common mistake students make). Or maybe he is just a follower of constructivism.

  • 0
    I already finished the class last week and I got an A, I was just hurt at the way he expressed his thoughts about my proof :-P2012-04-06
8

Apologies, I made the same error as your grader in understanding your argument.

However, I would say that your proof is still slightly incorrect: you did not conclude that "$x$ is a prime that is congruent to $3$ mod $4$". Instead, what you demonstrated was that, in the hypothetical world we set up for the purposes of the argument by contradiction, $x$ is divisible by no primes. Your statement that "$x$ is not divisible by any primes, so it should be prime" makes no sense, even in a proof by contradiction.

The way you have it set up currently, I would say that the known fact that which your proof reaches a contradiction with is that any integer has a prime factorization, not the assumption that $S$ contains all primes that are congruent to $3$ mod $4$.

  • 0
    @DanielMontealegre: I have added an answer.2012-04-06