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

-
3 is greater than 2. Anyway, remember what the definition of the factorial is. –  Qiaochu Yuan Oct 13 '10 at 10:27
@Qiaochu: I dont get u –  anonymous Oct 13 '10 at 10:28
@Chandru1: the first comment is directed to you and the second is to the OP. –  Qiaochu Yuan Oct 13 '10 at 10:37
@qIAOCHU: by the way i don't get what u want to say.please elaborate –  anonymous Oct 13 '10 at 10:40
@Chandru1: the numbers are of the form n!+n so the case 2!+3=5 is not included here. –  Maths student Oct 13 '10 at 10:41

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