Difference between revisions of "Legendre's Formula"

m (Part 2)
(Proof)
Line 5: Line 5:
 
where <math>p</math> is a prime and <math>e_p(n)</math> is the [[exponent]] of <math>p</math> in the [[prime factorization]] of <math>n</math> and <math>S_p(n)</math> is the [[sum]] of the [[digit]]s of <math>n</math> when written in [[base]] <math>p</math>.
 
where <math>p</math> is a prime and <math>e_p(n)</math> is the [[exponent]] of <math>p</math> in the [[prime factorization]] of <math>n</math> and <math>S_p(n)</math> is the [[sum]] of the [[digit]]s of <math>n</math> when written in [[base]] <math>p</math>.
  
==Proof==
+
==Proofs==
 
=== Part 1 ===
 
=== Part 1 ===
 +
We use a counting argument.
 +
 
We could say that <math>e_p(n!)</math> is equal to the number of multiples of <math>p</math> less than <math>n</math>, or <math>\lfloor \frac{n}{p}\rfloor</math>. But the multiples of <math>p^2</math> are only counted once, when they should be counted twice. So we need to add <math>\lfloor \frac{n}{p^2}\rfloor</math> on. But this only counts the multiples of <math>p^3</math> twice, when we need to count them thrice. Therefore we must add a <math>\lfloor \frac{n}{p^3}\rfloor</math> on. We continue like this to get <math>e_p(n!)=\sum_{i=1}^{\infty} \left\lfloor \dfrac{n}{p^i}\right\rfloor</math>. This makes sense, because the terms of this series tend to 0.
 
We could say that <math>e_p(n!)</math> is equal to the number of multiples of <math>p</math> less than <math>n</math>, or <math>\lfloor \frac{n}{p}\rfloor</math>. But the multiples of <math>p^2</math> are only counted once, when they should be counted twice. So we need to add <math>\lfloor \frac{n}{p^2}\rfloor</math> on. But this only counts the multiples of <math>p^3</math> twice, when we need to count them thrice. Therefore we must add a <math>\lfloor \frac{n}{p^3}\rfloor</math> on. We continue like this to get <math>e_p(n!)=\sum_{i=1}^{\infty} \left\lfloor \dfrac{n}{p^i}\right\rfloor</math>. This makes sense, because the terms of this series tend to 0.
  
 
=== Part 2 ===
 
=== Part 2 ===
Let the base <math>p</math> representation of <math>n</math> be <math>e_xe_{x-1}e_{x-2}\dots e_0</math>, where <math>e_i</math> is a digit for all <math>0\leq i\leq x</math>. Therefore the base <math>p</math> representation of <math>\lfloor \frac{n}{p^i}\rfloor</math> is <math>e_xe_{x-1}\dots e_{x-i}</math>. Note that the infinite sum of these numbers (which is <math>e_p(n!)</math>) is
+
Let the base <math>p</math> representation of <math>n</math> be <cmath>e_xe_{x-1}e_{x-2}\dots e_0</cmath> where the <math>e_i</math> are digits in base <math>p.</math> Then, the base <math>p</math> representation of <math>\lfloor \frac{n}{p^i}\rfloor</math> is <cmath>e_xe_{x-1}\dots e_{x-i}.</cmath> Note that the infinite sum of these numbers (which is <math>e_p(n!)</math>) is
 
 
<math>\sum_{j=1}^{x} e_j(p^{j-1}+p^{j-2}+\cdots +1)=\sum_{j=1}^{x} e_j(\frac{p^j-1}{p-1})=\frac{\sum_{j=1}^{x} e_jp^j -\sum_{j=1}^{x} e_j}{p-1}</math>
 
  
<math>=\frac{(n-e_0)-(S_p(n)-e_0)}{p-1}=\frac{n-S_p(n)}{p-1}</math>.
+
<cmath>\begin{aligned} \sum_{j=1}^{x} e_j(p^{j-1}+p^{j-2}+\cdots +1) &= \sum_{j=1}^{x} e_j(\frac{p^j-1}{p-1}) \ &=\frac{\sum_{j=1}^{x} e_jp^j -\sum_{j=1}^{x} e_j}{p-1} \ &=\frac{(n-e_0)-(S_p(n)-e_0)}{p-1}=\frac{n-S_p(n)}{p-1}. \end{aligned}</cmath>
  
 
{{stub}}
 
{{stub}}

Revision as of 10:07, 25 November 2013

Legendre's Formula states that

\[e_p(n!)=\sum_{i=1}^{\infty} \left\lfloor \dfrac{n}{p^i}\right\rfloor =\frac{n-S_{p}(n)}{p-1}\]

where $p$ is a prime and $e_p(n)$ is the exponent of $p$ in the prime factorization of $n$ and $S_p(n)$ is the sum of the digits of $n$ when written in base $p$.

Proofs

Part 1

We use a counting argument.

We could say that $e_p(n!)$ is equal to the number of multiples of $p$ less than $n$, or $\lfloor \frac{n}{p}\rfloor$. But the multiples of $p^2$ are only counted once, when they should be counted twice. So we need to add $\lfloor \frac{n}{p^2}\rfloor$ on. But this only counts the multiples of $p^3$ twice, when we need to count them thrice. Therefore we must add a $\lfloor \frac{n}{p^3}\rfloor$ on. We continue like this to get $e_p(n!)=\sum_{i=1}^{\infty} \left\lfloor \dfrac{n}{p^i}\right\rfloor$. This makes sense, because the terms of this series tend to 0.

Part 2

Let the base $p$ representation of $n$ be \[e_xe_{x-1}e_{x-2}\dots e_0\] where the $e_i$ are digits in base $p.$ Then, the base $p$ representation of $\lfloor \frac{n}{p^i}\rfloor$ is \[e_xe_{x-1}\dots e_{x-i}.\] Note that the infinite sum of these numbers (which is $e_p(n!)$) is

\begin{aligned} \sum_{j=1}^{x} e_j(p^{j-1}+p^{j-2}+\cdots +1) &= \sum_{j=1}^{x} e_j(\frac{p^j-1}{p-1}) \\ &=\frac{\sum_{j=1}^{x} e_jp^j -\sum_{j=1}^{x} e_j}{p-1} \\ &=\frac{(n-e_0)-(S_p(n)-e_0)}{p-1}=\frac{n-S_p(n)}{p-1}. \end{aligned} (Error compiling LaTeX. Unknown error_msg)

This article is a stub. Help us out by expanding it.