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

  • 4
    Remember what the definition of the factorial is.2010-10-13
  • 0
    @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$).2010-10-13
  • 0
    @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?2010-10-13
  • 0
    @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. =)2010-10-13
  • 0
    @Jens: Ah so I got it! Thank you!!!2010-10-13

4 Answers 4

4

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.

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

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

0

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

  • 0
    This may be a bit on the unclear side to the questioner!2010-10-13
  • 0
    @Noldorin, they can ask for clarification.2010-10-13
  • 0
    @muad: Thank you for clarification.2010-10-13
-3

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.

  • 1
    @Noldorin: Makes sense. Thank you.2010-10-13
  • 6
    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)2010-10-13
  • 0
    @Noldorin: It wasn't me who voted your answer down, and I would vote it up but I'm new to the website and so not yet allowed to vote. And I agree with Jens about the subset statement - I didn't quite understand how the subsets came into this. If you could explain please, I would be very grateful.2010-10-13
  • 0
    Oh, I didn't suspect either of you had down-voted...2010-10-13
  • 0
    @Jens: Actually, both i and k can be thought of as finite sets here! I would hope it is fairly plain. Sure, they are variables two, but can also loosely be thought of as representing elements within sets.2010-10-13
  • 0
    @Maths student: No worries. :) It's hard to explain without a self-evident argument, but maybe the above comment helps slightly.2010-10-13
  • 1
    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.2010-10-14
  • 0
    @Moron: Ok, I give you that! :)2010-10-14
  • 0
    @Noldorin: I did not vote on your answer; but have you considered the possibility that some might object to you working out the solution so completely to someone else's homework?2010-10-14
  • 1
    @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.2010-10-14
  • 0
    @Noldorin: personally, I do not downvote for that reason alone (though I often shake my head in disappointment... (-;)2010-10-14
  • 1
    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.2010-10-15
  • 0
    @ShreevatsaR: In that case, I suggest you pick up a book on basic set theory.2010-10-15
  • 0
    @Moron: Well I'm glad you think the current answer makes sense. The suggestion about reading up on set theory was a matter-of-fact one. I'll clarify what I mean a final time. Consider a variable x that is restricted to the range of integers between 1 and k. We can say that i represents an arbitrary member of the set (1, 2, ..., k). This is what I was saying from the start, does my current explanation make more sense?2010-10-15
  • 0
    @Noldorin: The current version of the answer makes more sense than your comment! Anyway end of discussion for me.2010-10-15