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
    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.2012-04-06
  • 2
    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.2012-04-06
  • 0
    Well the fact that a prime is divisible but itself requires no comment I believe. Why is there a need to specify the other primes? Assuming that $S$ contains all the primes congruent to $3$ modulo $4$, we showed that no prime (other than possibly $x$) divides $x$, hence $x$ ought to be a prime, but it failed to be in $S$, a contradiction. I still dont see what is wrong with the proof.2012-04-06
  • 1
    $$x=4 p_0 p_1...p_k - 1$$ is a little prettier.2012-04-06
  • 1
    @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.2012-04-06
  • 0
    x as constructed would be divisible by 3 since p_1 = 3 hence x is never prime.2012-04-06
  • 1
    No. $p_0 = 3$, not $p_1$.2012-04-06
  • 0
    @AndréNicolas: Many times statements in proofs are written keeping assumptions/other truths implicit, and not mentioning them explicitly. For instance, $x \gt 1$ is implicit, especially when you consider that the conclusion is that $x$ is prime. To me this looks more of a presentation problem than a logical problem. btw, I don't see how one can _impose_ that a conclusion must be so and so, especially so if you are trying to derive a contradiction. For instance, one could also say that $x$ must not be an integer (keeping $x \gt 1$ implicit)!2012-04-06
  • 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 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 :-P2012-04-06
  • 0
    @DanielMontealegre: I presume you are going to go back to your professor? :-) Do let us know of the result, if you do :-)2012-04-06
  • 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
    But assuming that $S$ contains all the primes congruent to $3$ modulo $4$, wouldnt this be correct?2012-04-06
  • 0
    No, the statement that the prime factorization of $x$ contains at least one prime that is not in $S$ is not the same as, nor does it imply, that $x$ is itself a prime number that is not in $S$.2012-04-06
  • 0
    @Zev: I'm not sure why you are saying that Daniel's proof is wrong. If you approach the proof constructively, you certainly need to consider the case that there is another prime dividing $x$ that is congruent to $3$ mod $4$, and is not in $S$. However, Daniel's proof is by contradiction, so that case need not be considered. It is not surprising that Daniel's "algorithm" does not actually work: by constructing a proof by contradiction, he is in fact working with an expanded, inconsistent theory. It is in this theory that the algorithm "works."2012-04-06
  • 0
    @Isaac: Ah, I see your point. Thanks for correcting my mistake. I've edited my answer; do you agree with my revised assessment?2012-04-06
  • 0
    @Zev: I'm still confused by your answer. We have yet to prove that $x$ is not divisible by any primes, as we have not proven that $x$ itself is not a prime. If anything, the fact that any integer has a prime factorization then forces $x$ to be prime, no?2012-04-06
  • 0
    @Isaac: By our assumption about $S$, we can state that $x$ isn't divisible by any primes that are $3$ mod $4$ (and, in particular, because $x$ is congruent to $3$ mod $4$ and isn't in $S$, it can't be prime); so the only primes that can occur in its factorization are $2$ and primes that are $1$ mod $4$. But $x$ clearly isn't divisible by $2$, so its prime factorization must be all primes that are $1$ mod $4$; but we know that's not the case either.2012-04-06
  • 1
    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.2012-04-06
  • 1
    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".2012-04-06
  • 1
    @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.2012-04-06
  • 2
    @ZevChonoles: Yes and since $x$ _must_ be prime, assuming finiteness of $S$, the proof is correct!2012-04-06
  • 0
    Hmm...I'm actually now inclined to agree with Aryabhata. In this theory we have built, we have proven that (1) $x$ is not divisible by primes less than it, and hence must be prime and in $S$, (2) $x$ cannot be prime, and (3) $x$ is not in $S$. We have two contradictions here: (1) contradicts (2) and (1) contradicts (3). It is a bit wasteful to use the second contradiction, but it is still valid.2012-04-06
  • 0
    @Aryabhata: I now see how you're reading Daniel's argument, with the implied "other". I agree, if Daniel had said "$x$ is divisible by no other prime, and therefore must be prime itself" I think everything would be perfectly correct. However, I would still contend that, because "$x$ is divisible by no prime" is actually also part of one possible, valid argument, but can't logically be followed by "therefore $x$ is prime", the missing word "other" is quite critical to intelligibility. I might still take points off, if I were the grader.2012-04-06
  • 0
    But perhaps it'd be best if you posted a separate answer explaining in more detail how you see the argument.2012-04-06
  • 0
    @Aryabhata Please elaborate on that. My professor said my proof was ridiculous and the fact that I still fail to see why it is incorrect has driven me to frustration.2012-04-06
  • 0
    @ZevChonoles Oh got it!! The contradiction is that then $x$ would not be able to be broken into primes. I still think that not giving me credit for the above and calling it ridiculous was harsh.2012-04-06
  • 0
    @DanielMontealegre: I have added an answer.2012-04-06