Problem:
For how many integers n between 1 and 50 , inclusive, is
(n!)n(n2−1)!
an integer? (Recall that 0!=1.)
Answer Choices:
A. 31
B. 32
C. 33
D. 34
E. 35
Solution:
The main insight is that (n!)n+1(n2)! is always an integer. This is true because it is precisely the number of ways to split up n2 objects into n unordered groups of size n. Thus, (n!)n(n2−1)!=(n!)n+1(n2)!⋅n2n! is an integer if n2∣n!, or in other words, if n(n−1)!, is an integer. This condition is false precisely when n=4 or n is prime, by Wilson's Theorem. There are 15 primes between 1 and 50, inclusive, so there are 15+1=16 terms for which (n!)n(n2−1)! is potentially not an integer. It can be easily verified that the above expression is not an integer for n=4 as there are more factors of 2 in the denominator than the numerator. Similarly, it can be verified that the above expression is not an integer for any prime n=p, as there are more factors of p in the denominator than the numerator. Thus all 16 values of n make the expression not an integer and the answer is 50−16= (D)34.
SideNote: Another method to prove that
(n!)n+1(n2)!
is always an integer is instead as follows using Number Theory. Notice that n will divide the numerator n+1 times, since n2=n×n contains not one but two factors of n. Also, for a<n, notice that a divides (n2) ! at least
⌊an2⌋≥⌊n−1n2⌋≥⌊n−1n2−1⌋≥n+1
times. Thus, each integer from 1 to n will divide (n2) ! at least n+1 times, which proves such a lemma
OR
We can use the P-Adic Valuation (more info could be found here: Mathematicial notation) of n to solve this problem (recall the P-Adic Valuation of ' n ' is denoted by vp(n) and is defined as the greatest power of some prime ' p ' that divides n. For example, v2(6)=1 or v7(245)=2.) Using Legendre's formula, we know that :
vp(n!)=∑i=1∞⌊pin⌋
Seeing factorials involved in the problem, this prompts us to use Legendre's Formula where n is a power of a prime.
We also know that, vp(mn)=n⋅vp(m). Knowing that a∣b if vp(a)≤vp(b), we have that:
n⋅vp(n!)≤vp((n2−1)!)
and we must find all n for which this is true.
If we plug in n=p, by Legendre's we get two equations:
vp((n2−1)!)=∑i=1∞⌊pin2−1⌋=(p−1)+0+…+0=p−1
And we also get:
vp((n!)n)=n⋅vp(n!)=n⋅∑i=1∞⌊pin⌋=p⋅(1+0+…0)=p
But we are asked to prove that n⋅vp(n!)≤vp((n2−1)!)⟹p≤p−1 which is false for all ' n ' where n is prime.
Now we try the same for n=p2, where p is a prime. By Legendre we arrive at:
vp((p4−1)!)=p3+p2+p−3
(as vp(p4!)=p3+p2+p+1 and p4 contains 4 factors of p ) and
p^{2} \cdot v_{p}\left(p^{2}!\right)=p^{3}+p^
Then we get:
p2⋅vp(p!)≤vp((n4−1)!)⟹p3+p2≤p3+p2+p−3
Which is true for all primes except for 2 , so 22=4 doesn't work. It can easily be verified that for all n=pi where i is an integer greater than 2 , satisfies the inequality :
n⋅vp(n!)≤vp((n2−1)!)
Therefore, there are 16 values that don't work and 50−16=(D)34 values that work.
The problems on this page are the property of the MAA's American Mathematics Competitions