1

Show that the integer $Q_n=n!+1$, where n is a positive integer, has a prime divisor greather han n. Conclude that there are infinity many primes.

Answer is given by: enter image description here

Why is the following true:

1) $p|n!\Rightarrow p|(Q_n-n!)$

2) We came true a contradiction, but why is $p_1$ a prime divisor of $Q_1$ and $p_2$ a prime divisor of $Q_{p_1}$?

WinstonCherf
  • 1,022
  • 1
    If $p$ divides $a$ and $p$ divides $b$ then $p$ divides $a+b$ and $a-b$. If $p$ divides $a$ then there exists an integer $k$ such that $pk=a$ and if $p$ divides $b$ then there exists an integer $l$ such that $pl=b$... you should be able to get the rest from there. Use this fact to answer your first question. – user328442 Dec 13 '17 at 14:54
  • @BrightChancellor How so? The proof first assumes that $p$ divides $Q_n$. Therefore, the result follows and leads to the desired contradiction. – user328442 Dec 13 '17 at 14:59
  • 1
    @user328442 Sorry, I read the question with weird thoughts in my head, thanks for mentioning. –  Dec 13 '17 at 15:04

2 Answers2

2

If $p\le n$ we have that $p$ appears among $n$, $n-1$, $n-2$ and so on, so clearly $p\mid n!$.

If an integer $k$ divides the integers $a$ and $b$, then it divides $a-b$. Indeed, if $a=kx$ and $b=ky$, then $a-b=k(x-y)$.

This should explain the part in green: if $p\mid Q_n$ and $p\le n$, then $p\mid n!$ and so $p\mid(Q_n-n!)$. But $Q_n-n!=1$, so this is impossible. Hence $p>n$.

The argument shows that, given an integer $n$, a prime divisor of $Q_n$ is greater than $n$. Since $p_2$ is a prime divisor of $Q_{p_1}$, we have $p_2>p_1$. In general, $p_{k+1}$ is a prime divisor of $Q_{p_k}$, so $p_{k+1}>p_k$.

However, there's a better explanation: the set of prime numbers is unbounded (no $n$ can be an upper bound), hence it is infinite.

egreg
  • 238,574
1

Because $n! = n\cdot (n-1) \cdot \ldots \cdot 1$ every integer which is less or equal to $n$ must divide $n!$. Since $Q_n = n!+1 > 1$ it has a prime divisor $p$. Now if $p \leq n$ then $p | n!$ and because also $p | Q_n$ (as it was a prime divisor of it) it must divide the difference $Q_n -n! = (n!+1)-n! =1$. But this can't be the case as $p>1$.

The second is true by construction as the prime divisors of $Q_n$ are greater than $n$ by the argument above.

Harto Saarinen
  • 1,445