2
$\begingroup$

If $n$ is a prime less than $m$, with $n,m \in \mathbb N$, why does $$\sum_{k=1}^\infty \left\lfloor \frac{m}{n^k}\right\rfloor$$ give you the number of times that $n$ divides $m!$?

Examples:

$n=13$

$m=321$

$\sum\limits_{k=1}^\infty \lfloor 321/(13^k)\rfloor=25$

$n=5$

$m=321$

$\sum\limits_{k=1}^\infty \lfloor 321/(5^k)\rfloor=78$

In fact, 

FactorInteger[321!]={{2, 318}, {3, 157}, {5, 78}, {7, 51}, {11, 31}, {13, 25}, {17, 
  19}, {19, 16}, {23, 13}, {29, 11}, {31, 10}, {37, 8}, {41, 7}, {43, 
  7}, {47, 6}, {53, 6}, {59, 5}, {61, 5}, {67, 4}, {71, 4}, {73, 
  4}, {79, 4}, {83, 3}, {89, 3}, {97, 3}, {101, 3}, {103, 3}, {107, 
  3}, {109, 2}, {113, 2}, {127, 2}, {131, 2}, {137, 2}, {139, 
  2}, {149, 2}, {151, 2}, {157, 2}, {163, 1}, {167, 1}, {173, 
  1}, {179, 1}, {181, 1}, {191, 1}, {193, 1}, {197, 1}, {199, 
  1}, {211, 1}, {223, 1}, {227, 1}, {229, 1}, {233, 1}, {239, 
  1}, {241, 1}, {251, 1}, {257, 1}, {263, 1}, {269, 1}, {271, 
  1}, {277, 1}, {281, 1}, {283, 1}, {293, 1}, {307, 1}, {311, 
  1}, {313, 1}, {317, 1}}

and so on, for every $n,m ∈ N$, $n$ prime and $<m$...?

Can someone explain?

$\endgroup$
8
  • $\begingroup$ Can you edit the title to be a complete question? $\endgroup$ – Matthew Leingang Feb 11 '15 at 15:54
  • $\begingroup$ Look at my answer to a similar question. $\endgroup$ – achille hui Feb 11 '15 at 15:56
  • 1
    $\begingroup$ @daniel Thanks! I'm improving/modifying the proof, because I don't think Mathematica was right, I put each time a different $n$ to see the result, and even if the result "seems" to go to Infinity, it's slowing down, and I conjecture there will be a large $n$ that will make the disequality $<1$, so I'm working on it :P $\endgroup$ – Andrea Feb 13 '15 at 10:05
  • 1
    $\begingroup$ @Andrea: You could make simplifications that I think would make the inequality true but they might depend on results that are also open questions. Even if you cannot prove the last inequality the question is a good model of a reasonable approach to something like this. $\endgroup$ – daniel Feb 13 '15 at 10:14
  • 1
    $\begingroup$ @daniel get it, I think I will un-delete, meanwhile I'm already working on another similar proof. $\endgroup$ – Andrea Feb 13 '15 at 10:18
0
$\begingroup$

There are $\lfloor \frac{m}{n} \rfloor $ numbers less than $m$ that are multiples of $n$.
Amongst these numbers, an $n$th is also divisible by $n^2$, i.e. is a multiple of it. So $\frac{1}{n} \lfloor \frac{m}{n} \rfloor= \lfloor \frac{m}{n^2} \rfloor $ additional $n$'s appear. Because we already counted every multiple of $n^2$ as a multiple of $n$ in the previous step we just add $1$ to the total sum for each multiple. An $n$th of all these square-multiples is also a multiple of $n^3$...
This continues for each power of $n$, until some number $x$ such that $n^x > m$. Of course we can write this as an infinite sum with $x \rightarrow \infty$ as well - we then add a finite amount of nonzero summands and an infinite amount of summands that are zero.

This doesn't hold for composite $n$ as then the prime factors that $n$ is composed of can also be combined by multiplying two other numbers less than $m$, where the product contains all prime factors of $n$.

$\endgroup$

Not the answer you're looking for? Browse other questions tagged or ask your own question.