# How to answer to this algebra problem?

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

-
@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? – user17762 Dec 8 '11 at 22:38
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. – user17762 Dec 8 '11 at 22:48
@SivaramAmbikasaran - i hate induction because it can't solve many problem when the problem is complicated – Victor Dec 8 '11 at 22:50
Victor, can you tell us where you took the problem from? – Srivatsan Dec 8 '11 at 23:01
@MaX: possibly because of the obstinate helplessness the OP clings to in the comment thread? – Henning Makholm Dec 8 '11 at 23:22

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<x+1$. Further note that in fact we have $a < b < x$. If $x|(x+1)$, then $x | (x+1-x)$ i.e. $x | 1$ i.e. $x=1$ which is not possible. Hence, if $x+1$ is a composite number, then $x+1 = ab$ where $1 < a < b < x$. Note that this means \begin{align} (x-1)! & = 1 \times 2 \times \cdots \times (a-1) \times a \times \cdots \times (b-1) \times b \times \cdots \times (x-1)\\ & = ab \times \left( 1 \times 2 \times \cdots \times (a-1) \times (a+1) \times \cdots \times (b-1) \times (b+1) \times \cdots \times (x-1) \right)\\ & = (x+1) \times \left( 1 \times 2 \times \cdots \times (a-1) \times (a+1) \times \cdots \times (b-1) \times (b+1) \times \cdots \times (x-1) \right) \end{align} Hence, $x+1$ divides $(x-1)!$.

$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<p^2-1$. Hence, a similar argument as $3$, by grouping $p$ and $2p$, gives us that $x+1$ divides $(x-1)!$.

$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\}$$

-
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.] – Srivatsan Dec 9 '11 at 0:11
@Srivatsan: Thanks for pointing that out! It is actually an important piece in the proof. – user17762 Dec 9 '11 at 0:24