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
    $\begingroup$ Your argument doesn't work for Euclid's proof either, and for the same reason. Say $p_1\ldots p_k$ are some set of primes, maybe even the first $k$ primes. Then let $x=p_1p_2\cdots p_k + 1$. Can you conclude that "$x$ is a prime"? No, sorry, you cannot. For example, $2\cdot3\cdot5\cdot7\cdot11\cdot13+1$ is not a prime; it is $59\cdot509$. All you can conclude is that $x$ is divisible by a prime that is not one of the $p_i$ in the set. $\endgroup$ – MJD Apr 6 '12 at 4:08
  • 2
    $\begingroup$ There are imprecisions. For example, recall that every prime is divisible by a prime, namely itself. Also, you did not say what the primes $p_1$ to $p_k$ are, apart from specifying that $p_1=3$. Also, there was enough vagueness to allow the grader to believe that you thought that $4p_1p_2\cdots p_k +3$ is necessarily prime. $\endgroup$ – André Nicolas Apr 6 '12 at 5:35
  • 1
    $\begingroup$ $$x=4 p_0 p_1...p_k - 1$$ is a little prettier. $\endgroup$ – Will Jagy Apr 6 '12 at 6:58
  • 1
    $\begingroup$ No. $p_0 = 3$, not $p_1$. $\endgroup$ – Aryabhata Apr 6 '12 at 7:47
  • 1
    $\begingroup$ @DanielMontealegre: The set $S$ is not defined. The hypothesis that $\{p_1,\dots, p_k\}$ includes all the primes of form $4t+3$ is not mentioned. From "$x$ is not divisible by any prime" you conclude that "$x$ should be prime." Actually from "$x$ is not divisible by any prime" the conclusion would be that $x=1$. Naturally, I am going by the exact words I see in the post. The sequence of words may have been different in the original. Certainly some variants of what is written would be a valid proof. $\endgroup$ – André Nicolas Apr 6 '12 at 11:18

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.

  • $\begingroup$ I wrote on the paper the same thing I wrote here. Yeah my guess is that he thought that I thought that multiplying the first integers congruent to $3$ mod $4$ we could get a bigger one, which is some sense worries me because I thought he knew I would not make such a rookie mistake :-P $\endgroup$ – Daniel Montealegre Apr 6 '12 at 6:37
  • $\begingroup$ @DanielMontealegre: I presume you are going to go back to your professor? :-) Do let us know of the result, if you do :-) $\endgroup$ – Aryabhata Apr 6 '12 at 7:19
  • $\begingroup$ 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 :-P $\endgroup$ – Daniel Montealegre Apr 6 '12 at 8:12

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$.

  • $\begingroup$ But assuming that $S$ contains all the primes congruent to $3$ modulo $4$, wouldnt this be correct? $\endgroup$ – Daniel Montealegre Apr 6 '12 at 3:45
  • 1
    $\begingroup$ What I should really say is that the main problem I have with Daniel's argument is the sentence "$x$ is not divisible by any primes, so it should be prime". I'm sure the argument can be reorganized so that the ultimate contradiction reached is with the assumption about $S$, but that sentence is simply invalid reasoning. $\endgroup$ – Zev Chonoles Apr 6 '12 at 4:16
  • 1
    $\begingroup$ Many proofs by contradiction reach contradictions with known truths. So why is it a problem here? The proof becomes perfectly fine (and IMO is actually implicit there) by adding the word "other": "x is not divisible by any prime other than $x$ and so $x$ should be a prime itself". $\endgroup$ – Aryabhata Apr 6 '12 at 4:30
  • 1
    $\begingroup$ @Aryabhata: I have no issue with a proof by contradiction reaching the contradiction with a known truth. However, in the hypothetical world, the only primes are: $2$, primes that are congruent to $1$ mod $4$, and the primes in $S$. We've demonstrated that $x$'s prime factorization can consist of none of these options. $\endgroup$ – Zev Chonoles Apr 6 '12 at 4:32
  • 2
    $\begingroup$ @ZevChonoles: Yes and since $x$ must be prime, assuming finiteness of $S$, the proof is correct! $\endgroup$ – Aryabhata Apr 6 '12 at 4:34

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.