Prime divisors of factorials

  • Thread starter Ethereal
  • Start date
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 [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.
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?
 
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
Top