1
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ 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? $\endgroup$ – ShreevatsaR Feb 13 '14 at 17:57
  • $\begingroup$ @ShreevatsaR: I am OK now, thank you very much for your offer of help! $\endgroup$ – Amanda.M Feb 14 '14 at 15:32
1
$\begingroup$

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

$\endgroup$
  • $\begingroup$ Thanks! I copied it exactly from friend's email and I agree that there is typo and therefor I am lost. Thanks again for your quick response! $\endgroup$ – Amanda.M Feb 13 '14 at 16:12
1
$\begingroup$

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!.$

$\endgroup$
  • $\begingroup$ Thanks! Looks like this proof is as classical as the proof of irrationality of square root of 2. Thanks again. $\endgroup$ – Amanda.M Feb 14 '14 at 14:16

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.