11
$\begingroup$

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 ?

$\endgroup$
12
$\begingroup$

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

$\endgroup$
5
$\begingroup$

HINT: If there were only finitely many primes, there would be a largest prime; call it $q$. Now consider what you know about $Q_q$.

$\endgroup$
  • $\begingroup$ Hi , @BrianMScott - I am not able to follow , exactly , would be grateful if you can expand upon your answer :) $\endgroup$ – pranav Feb 19 '15 at 2:25
  • 1
    $\begingroup$ @Michael: It’s correct, therefore it’s not flawed. Whether it’s needlessly complicated is a matter of opinion and taste; since I saw it before I saw the one that I suspect that you have in mind, I can’t really agree that it’s all that complicated. $\endgroup$ – Brian M. Scott Feb 19 '15 at 2:26
  • $\begingroup$ @pranav: You’ve proved that $Q_q$ must have a prime divisor larger than $q$, but by hypothesis $q$ is the largest prime ... $\endgroup$ – Brian M. Scott Feb 19 '15 at 2:27
  • $\begingroup$ But , @BrianMScott , in $Q_{n}$ -- n is not given to be prime -- why do you say that "by hypothesis $q$ is the largest prime" ? $\endgroup$ – pranav Feb 19 '15 at 2:29
  • 3
    $\begingroup$ @pranav: Whew! :-) You’re welcome. $\endgroup$ – Brian M. Scott Feb 19 '15 at 2:33
5
$\begingroup$

Let $P_n$ be a prime dividing $Q_n$. You've proved that $P_n>n$. The following is an infinite sequence of distinct primes: $$\left\{2,P_2,P_{P_2},P_{P_{P_2}},P_{P_{P_{P_2}}},P_{P_{P_{P_{P_{2}}}}},\ldots\right\}.$$ Therefore, there are infinitely many primes.

$\endgroup$
3
$\begingroup$

Hint: Suppose that there were finitely many primes. Let $n$ be the largest prime. Obtain a contradiction.

$\endgroup$
0
$\begingroup$

I'll not beat around the bush. For any given prime $p$ you can certainly find a positive integer $n$ such that $p$ is not greater than$~n$. So there cannot be a largest prime.

$\endgroup$

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.