3
$\begingroup$

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

$\endgroup$
  • 4
    $\begingroup$ Remember what the definition of the factorial is. $\endgroup$ – Qiaochu Yuan Oct 13 '10 at 10:27
  • $\begingroup$ @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$). $\endgroup$ – Jens Oct 13 '10 at 12:55
  • $\begingroup$ @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? $\endgroup$ – Maths student Oct 13 '10 at 13:27
  • $\begingroup$ @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. =) $\endgroup$ – Jens Oct 13 '10 at 14:17
  • $\begingroup$ @Jens: Ah so I got it! Thank you!!! $\endgroup$ – Maths student Oct 13 '10 at 14:33
4
$\begingroup$

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.

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

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

$\endgroup$
0
$\begingroup$

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

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

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.

$\endgroup$
  • 1
    $\begingroup$ @Noldorin: Makes sense. Thank you. $\endgroup$ – Maths student Oct 13 '10 at 13:57
  • 6
    $\begingroup$ 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) $\endgroup$ – Jens Oct 13 '10 at 14:21
  • 1
    $\begingroup$ 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. $\endgroup$ – Aryabhata Oct 14 '10 at 19:05
  • 1
    $\begingroup$ @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. $\endgroup$ – Noldorin Oct 14 '10 at 21:16
  • 1
    $\begingroup$ 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. $\endgroup$ – ShreevatsaR Oct 15 '10 at 7:10

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.