Show that a number is not prime?

Show that for any integer $n>1$, all the numbers $n!+2, n!+3, \ldots, n!+n$ are composite (i.e. not prime).

• Remember what the definition of the factorial is. – Qiaochu Yuan Oct 13 '10 at 10:27
• @maths student: Try to write out $n!+2, n!+3, ...$ for a small $n$ (say $n=4$). You should see it then. (Remember: $4! = 4*3*2*1$). – Jens Oct 13 '10 at 12:55
• @Jens: Well n!=n*(n-1)! and n can only be written as n*1 since we are not told that it cannot be prime, So d=1 or n. But that's not helpful as any integer is divisible by 1 and obviously n! is divisible by n. What am I not seeing? – Maths student Oct 13 '10 at 13:27
• @maths student: You're seeing everything there is to see, I think. Since $n!$ and $n$ are both divisible by $n$, so is $n!+n$, and therefore it is not prime. That's what you wanted. =) – Jens Oct 13 '10 at 14:17
• @Jens: Ah so I got it! Thank you!!! – Maths student Oct 13 '10 at 14:33

Hint: Try to show, that if for two numbers $a$ and $b$, $a$ is divisible by $d$ and $b$ is divisible by $d$, then so is their sum. Then go looking for such a common divisor in your sums.

• Thank you for the hint. Have done this, now trying to apply it to the n!+1 and n case. – Maths student Oct 13 '10 at 13:58
• @Maths student: In your question you start at $n!+2$. Your statement is false for $n!+1$, since $3!+1=7$ is prime. – Jens Oct 13 '10 at 14:16
• Sorry, a typo, I did mean n!+n =) – Maths student Oct 13 '10 at 14:38

HINT $\rm\quad k\:$ divides $\rm\: k\:m + k\:,\$ and, of course, $\rm\ k\:$ divides $\rm\: n!\$ for $\rm\:k =2,3,\:\ldots\:,n\:$.

$8! = 1\cdot 2\cdot 3\cdot 4\cdot 5\cdot 6\cdot 7\cdot 8$ so combine $k|8!$ and $k|k$ to get $k|8!+k$

Definition: $a|b :\iff \exists k, a k = b.$

Theorem: $a|m$ and $a|n$ imply that $a|m+n$. Proof: Our hypothesis says that $a k = m$ and $a h = n$, add this and use distributivity to get $a (k + h) = n + m$ which proves that $a|n+m$.

Note that if $k|b$ with ($k$ not $1$ or $b$) then $b$ has a divisor, so it is not prime.

• This may be a bit on the unclear side to the questioner! – Noldorin Oct 13 '10 at 13:26
• @Noldorin, they can ask for clarification. – anon Oct 13 '10 at 13:29
• @muad: Thank you for clarification. – Maths student Oct 13 '10 at 13:56

Take an arbitrary number $n! + k$, where $n > 1, 1 < k \leq n$.

The following is the definition of the factorial function:

$$n! = \prod_{i=1}^n i$$

Hence every i where $1 \leq i \leq n$ is a factor of $n!$. Since the range k covers is within the range of i, this is clearly true for all k.

We know that k is a factor of $n!$, so let us say $n! = qk, k \in \mathbb{Z}$. Hence $n! + k = qk + k = (q + 1)k$, which implies q + 1 and k are integral factors of $n! + k$. QED

This is a reasonably rigorous proof. When you become more familiar with the concepts of divisibility and factorials the result should be fairly apparent from first sight.

• @Noldorin: Makes sense. Thank you. – Maths student Oct 13 '10 at 13:57
• Your statement "Since k is a subset of i" is a bit unclear. Neither i nor k is a set here. Your proof would be better without that sentence, I think =) (and no, I did not vote you down) – Jens Oct 13 '10 at 14:21
• The only nonsense I see here: the statements "Since k is a subset of i, clearly the same is true for all k" and "rigourous proof" appearing close by. – Aryabhata Oct 14 '10 at 19:05
• @Arturo: Sure, though I'm not sure it derserves a down-vote. The solution (I felt) was a bit too obvious such that it would be hard to hint without being either too vague or explaining everything. Either way, he has the benefit of a full explanation from which to learn. – Noldorin Oct 14 '10 at 21:16
• You know you can edit answers, right? I haven't downvoted this either, but why do you leave the nonsense sentence up after it has been pointed out? I still have no idea what "Since loosely speaking, k is a subset of i, clearly the same is true for all k" may mean. – ShreevatsaR Oct 15 '10 at 7:10