I was doing some basic Number Theory problems and came across this problem :
Show that the integer : $Q_{n} = n ! + 1$, where $n$ is a positive integer, has a prime divisor greater than $n$.
Conclude that there are infinitely many primes.
My Solution (partial)
- We know that as $Q_{n}$ is $\gt$ $1$ $\Rightarrow$ $Q_{n}$ has a prime divisor $p$
- Let us assume , that $p$ $\le$ $n$
- If $p \le n$ then $ p \mid n! $
- So , in the equality ; $Q_{n} – n ! = 1$ , $p$ divides the LHS $\Rightarrow$ it also divides $1$
- But that is not possible as no prime divides $1$
- Hence , we have achieved a contradiction and there exists a prime divisor $>n$
My Question :
I am not able to prove the infinitude of primes from this result , how can I do that ?
Best Answer
The proof implies that given any prime $\,\color{#c00}p\,$ there exists a larger prime (dividing $\,Q_{\large\color{#c00}p}$), therefore the set of primes is infinite.
Remark $\ $ Because this way of proof is not by contradiction, it yields constructive information: iterating the above yields an algorithm to generate an infinite sequence of primes, viz.
$$\begin{align} &Q_1 = 1!+1 = 2\quad\ \text{has prime factor}\ \ \ \, 2 > 1\\ &Q_2 = 2!+1 = 3\quad\ \text{has prime factor}\ \ \ \, 3 > 2\\ &Q_3 = 3!+1 = 7\quad\ \text{has prime factor}\ \ \ \, 7 > 3\\ &Q_7 = 7!+1 = 71^2\ \text{has prime factor}\ \ 71 > 7\\ &\quad\ \ \ \vdots\qquad \qquad \qquad\qquad\ \ \vdots \end{align}\qquad $$ This proof is a minor variation on Euclid's classical proof (which also was not by contradiction, despite many inaccurate historical claims to the contrary).