Show that (k^3)! is divisible by(k!)^(k^2+k+1).

We need to show that all factors of (k!)^(k^2+k+1) are also factors of (k^3)!

The easiest way to see the structure is to look at an example.  Let k=4
(4!)^(4^2+4+1) = (4*3*2*1)^21 = 4^21 * 3^21 * 2^21*1^21
So the other number must contain at least 21 factors each of 4, 3 and 2

(4^3)! = (64)! = 64*63*62*...*2*1
How many factors of 4 is this?
16 for the multiples of 4
4 more for the multiples of 16 = 4^2
1 more for the 64 = 4^3
For a total of 21 (nice, we can see where the problem came from)
Likewise the number of factors of 3 is at least 21 since by similar reasoning there are 21 factors of 3 in 27 = 3^3
The number of factors of 2 is a bit tricky since we can't reuse multiples of 4. 
There are 16 multiples of 2 that are not multiples of 4.
Of the 16 multiples of 4, half have another factor of 2 so that's 8 more and were are over 21.

So it works for 4.

I can 'see' that most of this will work for any k.
Certainly the number of factors of k in each case is (k!)^(k^2+k+1)
What I'm not sure is that (k^3)! will have an abundance of smaller numbers.  It feels that it should, but how to prove...

Posted by Jer on 2012-12-29 23:32:15