Dismiss Notice
Join Physics Forums Today!
The friendliest, high quality science and math community on the planet! Everyone who loves science is here!

Homework Help: Evaluate ord_p(p^N!)

  1. Jun 21, 2010 #1
    1. The problem statement, all variables and given/known data
    The question is from Koblitz's "P-adic Numbers, p-adic Analysis, and Zeta Functions". It asks me to prove that
    [tex]ord_p(p^N!)= \sum _{i=1}^{N-1}p^i[/tex].

    2. Relevant equations
    Firstly it would be important to define [tex]ord_px[/tex]. This is defined to be the exponent of the highest power of the prime p that divides x. The only additional useful bit of information is that, in general,


    3. The attempt at a solution
    So I have an evaluation of the ord function, but I can't show that it equals
    [tex]\sum _{i=1}^{N-1}p^i[/tex].

    Since we have the logarithmic like property for the order function, I can say that

    [tex]ord_p(p^N!)=\sum _{i=1}^{p^N}ord_p(i)[/tex].

    My basic approach then is combinatorial. Firstly, I ask how many numbers x in the interval [tex]1\leq x\leq p^N[/tex] have order n. The first such number will be [tex]p^n[/tex], and then all other numbers will be multiples of this number, so the next question is to ask how many multiples we can have of [tex]p^n[/tex] such that the resulting product is still less than or equal to p^N.

    There are going to [tex]p^{N-n}[/tex] such coefficients, but out of these, some of them will result in a number whose order is larger than n. These will be precisely those coefficients that are some power of p. There are N-n of these, so in all we have:
    [tex](p^{N-n})-(N-n)=p^{N-n}+n-N[/tex] numbers whose order is n.

    Now the amount that these numbers contributes to the overall sum will be [tex]n(p^{N-n}+n-N)[/tex], and the possible degrees range from 1 to N, so we have:
    [tex]ord_p(p^N!)=\sum _{i=1}^{N}ip^{N-i}+i^2-iN[/tex].

    My trouble is that I cannot see how this can be shown to be equal to the answer given in the book, which is the quite simple [tex]\sum _{i=1}^{N-1}p^i[/tex].
    Last edited: Jun 21, 2010
  2. jcsd
  3. Jun 21, 2010 #2


    User Avatar
    Staff Emeritus
    Science Advisor
    Gold Member

    You can kick double counting in the teeth with this problem and not even worry about it.

    For all the numbers between 1 and pN, there are pN-1 of them that are divisible by p (every pth one). There are pN-2 of them that are divisible by p2. If we just add those together, we haven't double counted the p2 terms because they were counted once when we counted the terms divisible by p, and once when we counted the terms divisible by p2, and they were supposed to be counted twice to begin with

    You can probably see how this argument extends
  4. Jun 21, 2010 #3
Share this great discussion with others via Reddit, Google+, Twitter, or Facebook