# Prime divisors of factorials

E

#### 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?

Related Linear and Abstract Algebra News on Phys.org

#### 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

### Physics Forums Values

We Value Quality
• Topics based on mainstream science
• Proper English grammar and spelling
We Value Civility
• Positive and compassionate attitudes
• Patience while debating
We Value Productivity
• Disciplined to remain on-topic
• Recognition of own weaknesses
• Solo and co-op problem solving