For a prime for , you've probably seen this formula somewhere for the highest power of dividing :
In fact, there's a much more surprising formula (let's face it, this one isn't that hard to derive): suppose , or
and let be the digit sum of base . Then the highest power of dividing is
Wow. That's a heck of a lot shorter, isn't it? But why does this even work? Let's prove it below...
Then factor (by difference of nth powers) and cancel the in the denominator. This results in
Now write this sum out - term by term - in columns (not a typo, I mean columns - there's a trick here):
Okay, while each term was written by column before, let's look at the rows now. In fact, each row is equal to a term in this familiar expression:
because each time you divide by again one term in the base expansion vanishes (that associated with ) and the others go down an exponent of . So, we have