How Do Prime Numbers Divide Factorials?

[Ethereal]

I was reading this tutorial and I came across this part which I didn't quite understand:

Theorem: Let n and p be positive integers and p be prime. Then the largest exponent s such that $$p^s|n!$$ is:
$$s = \sum_{j{\geq}1} \displaystyle{\lfloor} \frac{n}{p^j} \displaystyle{\rfloor}$$ (1)

Proof Let $$m_i$$ be the number of multiples of $$p^i$$ in the set {1,2,3,...,n}. Let

$$t = m_1 + m_2 + m_3 + ... + m_k$$ (2)

Suppose that a belongs to {1,2,3,...,n}, and such that $$p^j|a$$ but not $$p^{j+1}|a$$. Then in the sum (2) a will be counted j times and will contribute i towards t. This shows that t=s.

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?

 

[TenaliRaman]

First get this clear ...
m1 denotes the number of values in {1,..,n} divisible by p
m2 denotes the number of values in {1,..,n} divisible by p^2
m3 denotes the number of values in {1,..,n} divisible by p^3
...
...
mk denotes the number of values in {1,..,n} divisible by p^k

if a is divisible by p^j and not by p^j+1
that means the maximum power of p that can divide a is j ...

if p^j|a then p|a,p^2|a,p^3|a,p^4|a,...,p^j|a

that means this number a will have been counted in m1,m2,m3,m4,...,mj
t = sum of all m_i's
so a will have been counted j times in t ...

contribute an i towards t

or in other words contribute an m_i towards t
(can u see why?)

why is t=s?

set a=n and apply floor

-- AI

 

[M98Ranger]

The theorem is stating that the largest exponent (s) of a prime number (p) that divides a factorial (n!) is equal to the sum of the number of multiples of p^i in the set {1,2,3,...,n}, where i ranges from 1 to k.

The proof is using the fact that if we have a number a that is a multiple of p^j, but not p^(j+1), then it will contribute j to the sum t. This is because a is counted j times in the sum (since it is a multiple of p^j) and it will contribute i (which is equal to j) towards t. This is because a is counted j times in the sum (since it is a multiple of p^j) and it will contribute i (which is equal to j) towards t.

This means that for each multiple of p^j in the set {1,2,3,...,n}, it will contribute j towards t. And since the set includes all multiples of p^j up to n, the sum t will be equal to the total number of multiples of p^j in the set. This is why t is equal to m_1 + m_2 + m_3 + ... + m_k, where k is the largest exponent of p that divides n!.

Therefore, by showing that t=s, we are proving that the largest exponent of p that divides n! is equal to the sum of the number of multiples of p^i in the set {1,2,3,...,n}. This is what the theorem (1) is stating.