Is this a valid proof by contradiction for why there are infinitely many primes

prime numbersproof-writingsolution-verification

I would appreciate feedback on whether the specific contradiction I make is valid in my attempt to prove that there are infinitely many primes, this on a conceptual level. For context, I subsequently saw a correct proof which was very similar, but worked through this before and have some issues with my "proof" which I will describe in a bit.
This is my reasoning:

  1. First, I assume that there is a finite number of primes, in order to show how a contradiction is implicated from this. If there are a finite number of primes, there must be a greatest prime number P.
  2. Consider the integer Q, which is formed by taking the product of every prime number, including P.
  3. Q+1 cannot have a prime factor, as none of the prime factors of Q can be factors of Q+1: this is because the difference between Q and Q+1 would have to be divisible by a prime factor of Q for Q+1 to be divisible by the same factor, which is not possible.
  4. Using the fact that all natural numbers greater than one are either prime or have a prime divisor, I conclude that Q+1 is prime.
  5. Q+1 is larger than P, contradicting the fact that P is the largest prime number. Therefore, the hypothesis from which this contradiction followed (that there is a finite number of primes) is false.

I am wondering if this works or if we would need to have a direct proof if we wanted to use this reasoning, which says for every prime number P, we can construct a greater prime number. This is because I am unsure whether it is correct for us to identify a greatest prime number and then construct an even greater prime number right afterwards- this feels like it was not legitimate to even say Q+1 is greater than P, as when we assumed a greatest prime number Q+1 could have been that number. This has made me wonder if the contradiction I have built is a legitimate contradiction, as P and Q could be the exact same quantity, but due to a fallacy in reasoning I have deemed them distinct.

thanks

Best Answer

This is because I am unsure whether it is correct for us to identify a greatest prime number P and then construct an even greater prime number Q right afterwards- this feels like it was not legitimate to even say Q is greater than P, as when we assumed a greatest prime number, Q could have been that number.

I added a few labels to your above description, but it is still confusing, but I think what you are trying to say is that you feel that a particular derivation step is being illogical or disrespecting a particular premise that you have set up, because it is apparently contradicting that premise.

You needn't worry, because in your proof I only see valid inference/derivation steps (notwithstanding the typos in your points 4 and 5 where I think Q is meant to be Q+1), and that the contradiction(s) are surfacing in spite of them, not due to them.

Also, in case relevant: given a premise A, we can make separate valid arguments; if A happens to be false, then it is natural that we may obtain some true conclusions and some false conclusions.

Related Question