Results 1 to 7 of 7

Math Help - A divisibility problem

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

    A divisibility problem

    Prove that (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 (k!)^{k^2+k+1} and (k^3)!
    Last edited by aman_cc; August 18th 2010 at 01:30 AM.
    Follow Math Help Forum on Facebook and Google+

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

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

  6. #6
    Super Member
    Joined
    Jan 2009
    Posts
    715
    Edited .
    Last edited by simplependulum; August 18th 2010 at 06: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: September 18th 2010, 02:02 PM
  2. problem with divisibility
    Posted in the Number Theory Forum
    Replies: 3
    Last Post: September 8th 2010, 09:06 AM
  3. A problem about divisibility
    Posted in the Number Theory Forum
    Replies: 3
    Last Post: July 29th 2010, 10:18 PM
  4. divisibility problem?
    Posted in the Advanced Algebra Forum
    Replies: 1
    Last Post: February 24th 2010, 05:18 AM
  5. help this divisibility problem
    Posted in the Algebra Forum
    Replies: 1
    Last Post: April 29th 2008, 06:13 AM

Search Tags


/mathhelpforum @mathhelpforum