Results 1 to 6 of 6

Math Help - Number Theory Help Part 2

  1. #1
    Junior Member
    Joined
    Jan 2009
    Posts
    57

    Number Theory Help Part 2

    exp(p, n!) = \sum_{i=1}^{\infty} \lfloor \frac{n}{p^i}\rfloor

    After getting the first formula above, please help me build the more general formula for the exponent of any particular prime in the prime factorization of the product of any set of
    consecutive positive integers (which can be expressed as nPr ).

    For the purposes of this problem, we introduce the notation

    exp(p, nPr)= the exponent of prime p in the PF of nPr

    Example: exp(5, 25P6)=3

    please help!
    Follow Math Help Forum on Facebook and Google+

  2. #2
    Senior Member
    Joined
    Apr 2009
    From
    Atlanta, GA
    Posts
    409

    One step further

    exp(p, n!) = \sum_{i=1}^{\infty} \lfloor \frac{n}{p^i}\rfloor

    _nP_r=\frac{n!}{(n-r)!}

    So exp(p, nPr) = exp(p,n) - exp(p, n-r)

    exp(p, nPr) = \sum_{i=1}^{\infty} \lfloor \frac{n}{p^i}\rfloor -  \lfloor \frac{n-r}{p^i}\rfloor

    exp(p, nPr) \approx \sum_{i=1}^{\infty} \frac{r}{p^i}

    I don't think there's an explicit way to simplify the sum of two floor functions, so the error term on this approximation will be \pm \lfloor \frac{\ln n}{\ln p}\rfloor . Just like in the original, you don't have to sum to \infty, only to \lfloor \frac{\ln n}{\ln p}\rfloor .
    Last edited by Media_Man; May 23rd 2009 at 08:09 AM. Reason: spelling error
    Follow Math Help Forum on Facebook and Google+

  3. #3
    Junior Member
    Joined
    Jan 2009
    Posts
    57

    Last Part Help

    Prove that a number of the form nCr (where n is an integer and is greater than or equal to r) must be a positive integer.

    I don't understand the question-- please help!

    Thanks.
    Follow Math Help Forum on Facebook and Google+

  4. #4
    Senior Member
    Joined
    Apr 2009
    From
    Atlanta, GA
    Posts
    409

    Not a fraction

    Prove that a number of the form \frac{n!}{(n-r)!r!} comes out to a whole number, not a fraction, as long as n>r and both are positive integers. They are asking you to prove that everything without exception in the denominator cancels with something in the numerator.
    Follow Math Help Forum on Facebook and Google+

  5. #5
    Junior Member
    Joined
    Jan 2009
    Posts
    57
    Oh I understand the question now, but how are you supposed to get from the first two things that you solved for to this step?

    I actually tried to do a proof by contradiction, because as you substitute the values found in the first 2 (you have to prove the numerator is greater than the denominator), but it's not complete- any help?
    Last edited by amma0913; May 28th 2009 at 08:50 AM.
    Follow Math Help Forum on Facebook and Google+

  6. #6
    Senior Member
    Joined
    Apr 2009
    From
    Atlanta, GA
    Posts
    409

    Hint to get you started

    Here's a hint that makes things simpler: Start by proving \frac{n!}{(n-r)!} is always a whole number, and call it P.

    Then show why \frac P{r!} would always be a whole number...
    Follow Math Help Forum on Facebook and Google+

Similar Math Help Forum Discussions

  1. Textbooks on Galois Theory and Algebraic Number Theory
    Posted in the Advanced Algebra Forum
    Replies: 3
    Last Post: July 8th 2011, 07:09 PM
  2. Imaginary part of number
    Posted in the Algebra Forum
    Replies: 8
    Last Post: January 25th 2009, 06:00 PM
  3. Replies: 2
    Last Post: December 18th 2008, 06:28 PM
  4. Approximate Each Number...Part A
    Posted in the Pre-Calculus Forum
    Replies: 4
    Last Post: November 10th 2008, 09:10 AM
  5. Approximate Each Number...Part B
    Posted in the Pre-Calculus Forum
    Replies: 2
    Last Post: November 9th 2008, 10:25 PM

Search Tags


/mathhelpforum @mathhelpforum