Misconception of infinite prime numbers proof by contradiction? I'm using the proof on this page, except with $q$ instead of $p$ on the left side. The misconception of the proof is that $q$ has to be a prime number. I found this using $n = 6$, which gets me $q = 1 + (2 \cdot 3 \cdot 5 \cdot 7 \cdot 11 \cdot 13)$, which results in 30,031, which is not prime. Why doesn't $q$ have to be prime for the proof to work?
 A: The page is wrong in attributing this proof by contradiction to Euclid.
However, let's look at that proof rather than Euclid's.
The conclusion that $p_1 \cdots p_n + 1$ is prime was reached under the initial assumption, which was ultimately proved false.  Therefore, it was not validly proved.
Euclid's actual proof was not by contradiction, although a small part of his argument was.  He did not assume that $p_1,\ldots,p_n$ are the only primes that exist, nor that they are the smallest primes.  They could, for example, but $5, 23,97$, and $191$.  He proved that either $p_1\cdots p_n+1$ is prime or it is divisible only by primes not among the original list $p_1,\ldots,p_n$.  For example $(5\times23\times97\times191)+1$ either is prime or is divisible only by other primes not included among $5,23,97,191$.  Therefore the original list can always be extended to a larger list of primes.
(The part that Euclid did prove by contradiction was that two consecutive numbers cannot share a prime factor in common.)
Dirichlet's posthumous book on number theory published in 1861 falsely attributed the proof by contradiction to Euclid, and many eminent mathematicians have stupidly or ignorantly made the same mistke since then.  Catherine Woodgold and I published a joint paper demolishing the error and showing that Euclid's actual proof is better than this proof by contradiction falsely attributed to him.  It's in the Fall 2009 volume of The Mathematical Intelligencer.
BTW, it is an error to write "infinite prime numbers" if you mean "infinitely many prime numbers".  The phrase "infinite prime numbers" means "numbers, each one of which, by itself, is infinite."  Thus if $A$ is an infinite prime number (what is that?) and so is $B$, then $A$ and $B$ are infinite prime numbers, but they are not infinitely many prime numbers, since there are only two of them.
PS: I quote from our paper:

Only the premise that a set contains all prime numbers could make one conclude that if a number is not divisible by any primes in that set, then it is not divisible by any primes.
Only the statement that $p_1\cdots p_n + 1$ is not divisible by any primes makes anyone conclude that that number ‘‘is therefore itself prime’’, to quote no less a number-theorist than G. H. Hardy in [55], where he actually attributed that conclusion to Euclid! (Euclid’s statement ‘‘Certainly [that number] is prime, or not’’, to be examined at greater length below, clearly shows that Euclid’s reasoning did not follow that path.)
The mistake of thinking that $p_1\cdots p_n + 1$ has been proved to be prime is made all the more tempting by the very obvious fact that that would entail the result to be proved.
The proposal to prove the twin prime conjecture by saying that $p_1\cdots p_n + 1$ and $p_1\cdots p_n - 1$ are both prime came from a student with whom one of us (M. Hardy) spoke, who a few months later entered a graduate program in mathematics.
The seemingly trivial rearrangement of the proof into a reductio ad absurdum has thus led us quickly into territory that the straightforward proof could not have hinted at, wherein lie substantial mathematical errors that would not have been approached otherwise.
In any proof by contradiction, once the contradiction is reached, one can wonder which of the statements asserted to have been proved along the way can really be proved in just the manner given (since the argument supporting them
does not rely on the initial assumption later proved false), which ones are correct but must be proved in some other way (since the argument supporting them does rely on the initial assumption), and which ones are false. It is easy to neglect that task. One’s consequent ignorance of the answers to those questions can lead to confusion: after all, when one remembers reading a proof of a proposition, might one not think the proposition has been proved and is
therefore known to be true? G. H. Hardy probably was aware that because the conclusion that $p_1\cdots p_n+1$ ‘‘is therefore itself prime’’ was contingent on a hypothesis later proved false, it could not be taken to be proved. But he did not say that explicitly. It seems hard to justify a similar confidence that all of his readers avoided the error into which he inadvertently invited them. Euclid’s proof as presented by Øystein Ore [above] spares us that task by limiting the use of proof by contradiction to the narrowest possible scope.

To this I would add that making it into a proof by contradiction adds an extra complication that serves no purpose and only makes the proof appear more complicated than it really is.
A: You see that $q$ doesn't have to be prime because you've found an example where it isn't. You've probably proved that every integer has a unique prime factorization, but the proof shows that $q$ isn't divisible by any of the primes $p_1, ..., p_n$, so it has to be divisible by some prime not in that list. 
A: In this case there are two primes not among the initial list, as
$$ 30031 = 59 \cdot 509  $$ 
and the initial list was just the primes up to $13.$ 
A: This proof uses the following fact: every composite number has at least one prime factor.
So we have $q$ and we know that $q$ is either prime or composite. If it is prime then we are done. If it is composite then one of the $p_i$ divides $q$. But this leads to a contradiction. However, this doesn't mean that $q$ is prime — it could mean that the original list of $p_i$ is incomplete.
More generally, this proof uses contradiction. We say "suppose there are finite primes" and go from there. Thus, when we find a contradiction, all we can say is that our first assumption was not true — there must be infinite primes
