- #1
Ethereal
I was reading this tutorial and I came across this part which I didn't quite understand:
I don't follow this. What does "a will be counted j times and will contribute i towards t" mean? Why does this show that t=s?Theorem: Let n and p be positive integers and p be prime. Then the largest exponent s such that [tex]p^s|n![/tex] is:
[tex]s = \sum_{j{\geq}1} \displaystyle{\lfloor} \frac{n}{p^j} \displaystyle{\rfloor}[/tex] (1)
Proof Let [tex]m_i[/tex] be the number of multiples of [tex]p^i[/tex] in the set {1,2,3,...,n}. Let
[tex]t = m_1 + m_2 + m_3 + ... + m_k[/tex] (2)
Suppose that a belongs to {1,2,3,...,n}, and such that [tex]p^j|a[/tex] but not [tex]p^{j+1}|a[/tex]. Then in the sum (2) a will be counted j times and will contribute i towards t. This shows that t=s.