Show that for all natural numbers, (n!)! is divisible by (n!)^(n-1)!.

Lets look at the case when n=5
we want to show (5!)! is divisible by (5!)^(4!)
or 120! is divisible by (120)^24
Lets looks at how many factors each has

120!  has [120/5] + [120/5^2] = 24 + 4 = 28 factors of 5
120^24 = 5^24*4^24*3^24*2^24 has 24 factors of 5

120! has [120/4] + [120/4^2] + [120/4^3] = 30+7+1 = 38 factors of 4
120^24 has 24 factors of 4 (not counting the 24 that are factors of 2)

(3's are fine)

How many factors of 120! are factors of 2 but not 4?
Well there are a total of 60+30+15+7+3+1=116 factors of 2 subtract 2*38 leaves 40.  So there are enough factors of 2.

So it works with n=5.


It is again clear this will work with factors of n in the general case but what is not clear is that it will work with smaller numbers that are factors of each other.
For example when n=13 do the factors of 12 leave enough factors of 6?  Do the 12, 9, and 6 leave enough factors of 3?

Posted by Jer on 2013-01-02 13:40:19