# A divisibility problem

Printable View

• Aug 17th 2010, 07:20 AM
elim
A divisibility problem
Prove that $(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 $(k!)^{k^2+k+1}$ and $(k^3)!$
• Aug 18th 2010, 01:25 AM
simplependulum
Let $L_p(m)$ and $N_p(m)$ be the max. power of prime $p$ dividing $m$ and $m!$ respectively , then we need to show that

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

First note that $a_i = \lfloor { a_i \rfloor} +\{ a_i \}$ so $\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 $k,n > 1$ , we thus have

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

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

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

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

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

$\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 $\{ \frac{a}{b} \} = 0$ if $b|a$ and now , $(x,p) = 1$ . )

Obviously , $\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 , $N_p(k^{n+1} ) \geq N_p(k) + k N_p(k^n)$

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

It is true when $n=1$ and assume the case is true for any natural number $n$ . When we jump to the next case $n+ 1$ , we have $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).
$\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 $a|n^m$ , perhaps we need to elaborate more at this point . That's why i need to introduce the substitution $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.