# A divisibility problem

• Aug 17th 2010, 07:20 AM
elim
A divisibility problem
Prove that $\displaystyle (k!)^{k^2+k+1} \mid (k^3)!$
• Aug 18th 2010, 12:18 AM
aman_cc
Hint - Consider/compare the power of any prime, p, in the expansion of $\displaystyle (k!)^{k^2+k+1}$ and $\displaystyle (k^3)!$
• Aug 18th 2010, 01:25 AM
simplependulum
Let $\displaystyle L_p(m)$ and $\displaystyle N_p(m)$ be the max. power of prime $\displaystyle p$ dividing $\displaystyle m$ and $\displaystyle m!$ respectively , then we need to show that

$\displaystyle N_p(k^3) \geq (k^2 + k + 1 ) N_p(k)$ for any $\displaystyle p \leq k$

First note that $\displaystyle a_i = \lfloor { a_i \rfloor} +\{ a_i \}$ so $\displaystyle \lfloor{ \sum a_i \rfloor } = \lfloor{ \sum \lfloor{ a_i \rfloor} + \sum \{ a_i \} \rfloor} = \sum \lfloor{ a_i \rfloor} + \lfloor{ \sum \{ a_i \} \rfloor}$

For $\displaystyle k,n > 1$ , we thus have

$\displaystyle N_p(k^{n+1}) = \displaystyle{ \sum_{i=1}^{\infty} \lfloor{ \frac{ k^{n+1} }{p^i } \rfloor } }$

$\displaystyle = \displaystyle{ \sum_{i=1}^{\infty} \lfloor{ k ~\cdot~ \frac{ k^n }{p^i } \rfloor } }$

$\displaystyle = \displaystyle{ \sum_{i=1}^{\infty} \left( k \lfloor{ \frac{ k^n }{p^i } \rfloor } + \lfloor{ k \{ \frac{ k^n }{p^i }\} \rfloor} \right) }$

$\displaystyle = k N_p(k^n) + \displaystyle{ \sum_{i=1}^{\infty} \lfloor{ k \{ \frac{ k^n }{p^i }\} \rfloor} }$

Let $\displaystyle x = (\frac{ k}{ p^{L_p(k)} } )^n$ and $\displaystyle i = nL_p(k) + j$ , then

$\displaystyle \displaystyle{ \sum_{i=1}^{\infty} \lfloor{ k \{ \frac{ k^n }{p^i }\} \rfloor} = \sum_{j=1}^{\infty} \lfloor{ k \{ \frac{x}{p^j }\} \rfloor} }$ ( since $\displaystyle \{ \frac{a}{b} \} = 0$ if $\displaystyle b|a$ and now , $\displaystyle (x,p) = 1$ . )

Obviously , $\displaystyle \displaystyle{ \sum_{j=1}^{\infty} \lfloor{ k \{ \frac{x}{p^j }\} \rfloor} \geq \sum_{j=1}^{\infty} \lfloor{ \frac{k}{p^j} \rfloor} } = N_p(k)$

Therefore , $\displaystyle N_p(k^{n+1} ) \geq N_p(k) + k N_p(k^n)$

We can prove by induction , $\displaystyle N_p(k^n) \geq (1+k+k^2+...+ k^{n-1} )N_p(k)$ :

It is true when $\displaystyle n=1$ and assume the case is true for any natural number $\displaystyle n$ . When we jump to the next case $\displaystyle n+ 1$ , we have $\displaystyle N_p(k^{n+1} ) \geq N_p(k) + k N_p(k^n) \geq [1 + k(1+k+k^2 + ... + k^{n-1} )]N_p(k) = ( 1 + k + k^2 + ... + k^n ) N_p(k)$ which completes the proof .
• Aug 18th 2010, 04:16 AM
aman_cc
It may be enough to note/prove that for any n,m,a (all positive integers).
$\displaystyle \lfloor n^m/a \rfloor \geq (1+n+n^2+...+ n^{m-1}) \lfloor n/a \rfloor$

This can be shown easily using induction on m.

Once this is established use this fact in the series to find the power of a prime in n! i.e. N_p(n) (as per notation used by simplependulum)

This might just give a little simpler proof for the same.
• Aug 18th 2010, 05:43 AM
simplependulum
It is false when $\displaystyle a|n^m$ , perhaps we need to elaborate more at this point . That's why i need to introduce the substitution $\displaystyle i = n L_p(k) + j$ .
• Aug 18th 2010, 05:43 AM
simplependulum
Edited .
• Aug 19th 2010, 08:21 PM
aman_cc
Thanks. Let me re-check my work please.