0
$\begingroup$

Thanks for your attention to this question, here is the problem:

Compute the number of positive integers $x$ less than or equal to $1000$ that satisfy the following condition: $$x! \text{ is divisible by } 1+2+3+...+x$$

  • 0
    Do you recall a formula for $1 + 2 + \dots + x$?2011-12-08
  • 0
    @JavaMan- of course i know it.2011-12-08
  • 0
    Do you you see a way to use it?2011-12-08
  • 1
    @Victor: If you know the formula, you can simplify it to get an equivalent version of your question which is $x$ such that $(x+1)| (2 \times (x-1)!)$. Can you now proceed from here and argue out what $x$ should be?2011-12-08
  • 0
    @JavaMan - no, i don't see it2011-12-08
  • 0
    @SivaramAmbikasaran - i don't know how to get to there...2011-12-08
  • 0
    @Victor: What is the formula for $1 + 2 + 3 + \cdots + x$?2011-12-08
  • 0
    @SivaramAmbikasaran - it is x(x+1)/22011-12-08
  • 0
    So you need $\frac{x!}{x(x+1)/2} = k \in \mathbb{Z}^+$. Rearrange to get what I have written earlier. Can you then take it from there.2011-12-08
  • 0
    @SivaramAmbikasaran -But i don't know if there are "shortcut" to continue, otherwise i have to check all the cases.2011-12-08
  • 1
    Why don't you try a few examples for $x$ and see what happens? Then try to generalize. You will see the pattern immediately when you try out the examples.2011-12-08
  • 1
    @SivaramAmbikasaran - i hate induction because it can't solve many problem when the problem is complicated2011-12-08
  • 0
    @Victor: Why don't you try out some examples for $x$? You will see it will fail for some of them. If you just want the solution I can write it out.2011-12-08
  • 0
    @SivaramAmbikasaran - May you use a solution not using induction?2011-12-08
  • 5
    Victor, can you tell us where you took the problem from?2011-12-08
  • 0
    @Srivatsan -new york city interscholastic math league , but i change the number2011-12-08
  • 1
    why so many down-votes for this one?2011-12-08
  • 9
    @MaX: possibly because of the obstinate helplessness the OP clings to in the comment thread?2011-12-08
  • 0
    @Henning Makholm:May be yes, but the problem itself is not so bad; +1 from my side :)2011-12-09

1 Answers 1

8

We need to find $x$ such that $x!$ is divisible by $1+2+3+\cdots+x$. Note that $$1+2+\cdots + x = \frac{x(x+1)}{2}$$ Hence, we need $\frac{x!}{x(x+1)/2} = k \in \mathbb{Z}^+$ i.e. $\frac{2 \times (x-1)!}{x+1} = k \in \mathbb{Z}^+$.

Now we split it into five cases:

$1$. $x+1$ is an odd prime. If $x+1$ is an odd prime i.e. a prime greater than $2$, then we need $x+1$ to divide one of the numbers in the set $\{1,\ldots,x-1\} \cup \{2\}$ . But all the numbers in the set are smaller than $x+1$ and hence $x+1$ cannot divide any of the numbers. Hence, when $x+1$ is an odd prime, we cannot have $\frac{2 \times (x-1)!}{x+1}$ to be an integer whenever $x+1$ is an odd prime.

$2$. $x+1 = 2$. This can be easily checked that $x!$ is divisible by $1+2+3+\cdots+x$ i.e. $1!$ is divisible by $1$.

$3$. If $x+1$ is a composite number and is not of the form $p^2$, where $p$ is a prime, then it is not an irreducible. Hence $x+1 = ab$ where $1 < a < b

$4$. If $x+1$ is a composite number of the form $p^2$ where $p$ is an odd prime, then it immediately follows that $2p

$5$. If $x+1$ is $2^2$, then again we can easily check that $4| \left(2 \times 2! \right)$.

Hence, when $x+1$ is a composite number (or) $2$, we have that $(x+1) | \left( 2 \times (x-1)! \right)$.

Hence, the numbers you are interested are $$\{x \in \mathbb{Z}^+: x+1 \text{ is composite (or) }x+1 = 2\}$$

  • 0
    I think you need to be slightly more careful when $x+1 = p^2$, in which case we'll have $a = b$ ($= p$). [I don't think the final answer changes though.]2011-12-09
  • 0
    @Srivatsan: Thanks for pointing that out! It is actually an important piece in the proof.2011-12-09