Results 1 to 7 of 7

Thread: A divisibility problem

  1. #1
    Member
    Joined
    Mar 2010
    From
    usa
    Posts
    91

    A divisibility problem

    Prove that $\displaystyle (k!)^{k^2+k+1} \mid (k^3)!$
    Follow Math Help Forum on Facebook and Google+

  2. #2
    Super Member
    Joined
    Apr 2009
    Posts
    678
    Thanks
    1
    Hint - Consider/compare the power of any prime, p, in the expansion of $\displaystyle (k!)^{k^2+k+1}$ and $\displaystyle (k^3)!$
    Last edited by aman_cc; Aug 18th 2010 at 12:30 AM.
    Follow Math Help Forum on Facebook and Google+

  3. #3
    Super Member
    Joined
    Jan 2009
    Posts
    715
    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 .
    Last edited by simplependulum; Aug 18th 2010 at 02:17 AM.
    Follow Math Help Forum on Facebook and Google+

  4. #4
    Super Member
    Joined
    Apr 2009
    Posts
    678
    Thanks
    1
    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.
    Last edited by aman_cc; Aug 18th 2010 at 04:28 AM.
    Follow Math Help Forum on Facebook and Google+

  5. #5
    Super Member
    Joined
    Jan 2009
    Posts
    715
    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 $ .
    Last edited by simplependulum; Aug 18th 2010 at 05:54 AM.
    Follow Math Help Forum on Facebook and Google+

  6. #6
    Super Member
    Joined
    Jan 2009
    Posts
    715
    Edited .
    Last edited by simplependulum; Aug 18th 2010 at 05:56 AM.
    Follow Math Help Forum on Facebook and Google+

  7. #7
    Super Member
    Joined
    Apr 2009
    Posts
    678
    Thanks
    1
    Thanks. Let me re-check my work please.
    Follow Math Help Forum on Facebook and Google+

Similar Math Help Forum Discussions

  1. Divisibility Problem(2)
    Posted in the Number Theory Forum
    Replies: 3
    Last Post: Sep 18th 2010, 01:02 PM
  2. problem with divisibility
    Posted in the Number Theory Forum
    Replies: 3
    Last Post: Sep 8th 2010, 08:06 AM
  3. A problem about divisibility
    Posted in the Number Theory Forum
    Replies: 3
    Last Post: Jul 29th 2010, 09:18 PM
  4. divisibility problem?
    Posted in the Advanced Algebra Forum
    Replies: 1
    Last Post: Feb 24th 2010, 04:18 AM
  5. help this divisibility problem
    Posted in the Algebra Forum
    Replies: 1
    Last Post: Apr 29th 2008, 05:13 AM

Search Tags


/mathhelpforum @mathhelpforum