All about flooble | fun stuff | Get a free chatterbox | Free JavaScript | Avatars    
perplexus dot info

Home > Numbers
Divisibility of factorials (Posted on 2012-12-29) Difficulty: 3 of 5
Show that (k^3)! is divisible by(k!)^(k^2+k+1).

No Solution Yet Submitted by Danish Ahmed Khan    
No Rating

Comments: ( Back to comment list | You must be logged in to post comments.)
Some Thoughts A start. Comment 1 of 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
Please log in:
Remember me:
Sign up! | Forgot password

Search body:
Forums (0)
Newest Problems
Random Problem
FAQ | About This Site
Site Statistics
New Comments (0)
Unsolved Problems
Top Rated Problems
This month's top
Most Commented On

Copyright © 2002 - 2020 by Animus Pactum Consulting. All rights reserved. Privacy Information