# Proving prime p exists within $n+1\le p \le n!+1$

The title is another homework problem I got from graduate number theory. My friend gave me this hint:

Since any two consecutive integers are relatively prime and n! and n!+1 are integers, n! and n!+1 are relatively prime. Therefore, there is at least one prime that divides n!, so there is a prime p where p < n!. Moreover, if p ≤ n, p would divide n!, which is a contradiction. Therefore, n < p ≤ n! or n+1 ≤ p ≤ n!+1.

But I am still lost. Any help would be appreciated and thanks in advance for all your time.

• The "hint" is a full proof (with a typo writing $n!$ instead of $n!+1$), and Hagen's answer has already corrected it; what part are you still having difficulty with? – ShreevatsaR Feb 13 '14 at 17:57
• @ShreevatsaR: I am OK now, thank you very much for your offer of help! – Amanda.M Feb 14 '14 at 15:32

There are some problems with the given argument or you miscopied something. Let $p$ be a prime dividing $n!+1$ (which exists because $n!+1>1$). Then clearly $p\le n!+1$. If we had $p<n+1$ then $p\mid n!$, and hence $p\mid (n!+1)-n!=1$, contradiction. Hence $n+1\le p\le n!+1$.
The argument is a special case of the idea used in Euclid's classical proof that there are infinitely many primes. Namely, note that $\,m = 1+a_1\cdots a_n\,$ is coprime to $\,k = a_1\cdots a_n\,$ since any common factor divides their difference $\,m-k= 1.\,$ Therefore $\,m\,$ and $\,k\,$ have no common prime factors. In particular, if $\,a_i = i,\,$ so $\, k = n!,\,$ the prime factors of $\,1+n!\,$ are $> n,\,$ by prime $\,p \le n\,\Rightarrow\,p\mid n!.$