Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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

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

1 Answer

up vote 7 down vote accepted

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

share|improve this answer
    
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
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.