Legendre's Theorem

From ProofWiki
Jump to navigation Jump to search

Theorem

Let $n \in \Z_{>0}$ be a (strictly) positive integer.

Let $p$ be a prime number.

Let $n$ be expressed in base $p$ representation.

Let $r$ be the digit sum of the representation of $n$ in base $p$.


Then $n!$ is divisible by $p^\mu$ but not by $p^{\mu + 1}$, where:

$\mu = \dfrac {n - r} {p - 1}$


Corollary

Let $n \in \Z_{>0}$ be a (strictly) positive integer.

Let $B$ be the binary representation of $n$.

Let $r$ be the number of unit digits in $B$.

Let $n!$ denote the factorial of $n$.


Then $2^{n - r}$ is a divisor of $n!$, but $2^{n - r + 1}$ is not.


Proof

$n$ can be represented as:

\(\ds n\) \(=\) \(\ds \sum_{j \mathop = 0}^m a_j p^j\) where $0 \le a_j < p$
\(\ds \) \(=\) \(\ds a_0 + a_1 p + a_2 p^2 + \cdots + a_m p^m\) for some $m > 0$


Using De Polignac's Formula, we may extract all the powers of $p$ from $n!$.

$\mu = \displaystyle \sum_{k \mathop > 0} \floor {\dfrac n {p^k} }$

where $\mu$ is the multiplicity of $p$ in $n!$:

$p^\mu \divides n!$
$p^{\mu + 1} \nmid n!$


We have that:

\(\ds \floor {\dfrac {n!} p}\) \(=\) \(\ds \floor {\dfrac {a_0 + a_1 p + a_2 p^2 + a_3 p^3 + \cdots + a_m p^m} p}\)
\(\ds \) \(=\) \(\ds a_1 + a_2 p + a_3 p^2 + \cdots + a_m p^{m - 1}\)
\(\ds \floor {\dfrac {n!} {p^2} }\) \(=\) \(\ds \floor {\dfrac {a_0 + a_1 p + a_2 p^2 + + a_2 p^2 + \cdots + a_m p^m} {p^2} }\)
\(\ds \) \(=\) \(\ds a_2 + a_3 p + \cdots + a_m p^{m - 2}\)
\(\ds \) \(\vdots\) \(\ds \)
\(\ds \floor {\dfrac {n!} {p^m} }\) \(=\) \(\ds \floor {\dfrac {a_0 + a_1 p + a_2 p^2 + + a_2 p^2 + \cdots + a_m p^m} {p^m} }\)
\(\ds \) \(=\) \(\ds a_m\)


Thus:

\(\ds \mu\) \(=\) \(\ds a_m \paren {p^{m - 1} + p^{m - 2} + \cdots + p + 1}\)
\(\ds \) \(\) \(\, \ds + \, \) \(\ds a_{m - 1} \paren {p^{m - 2} + p^{m - 3} + \cdots + p + 1}\)
\(\ds \) \(\vdots\) \(\ds \)
\(\ds \) \(\) \(\, \ds + \, \) \(\ds a_2 \paren {p + 1}\)
\(\ds \) \(\) \(\, \ds + \, \) \(\ds a_1\)
\(\ds \) \(=\) \(\ds a_m \paren {\dfrac {p^m - 1} {p - 1} } + a_{m - 1} \paren {\dfrac {p^{m - 1} - 1} {p - 1} }\) Sum of Geometric Sequence
\(\ds \) \(\vdots\) \(\ds \)
\(\ds \) \(\) \(\, \ds + \, \) \(\ds a_2 \paren {\dfrac {p^2 - 1} {p - 1} } + a_1 \paren {\dfrac {p^1 - 1} {p - 1} } + a_0 \paren {\dfrac {p^0 - 1} {p - 1} }\) where the last term evaluates to $0$
\(\ds \) \(=\) \(\ds \dfrac {\paren {a_m p^m + a_{m - 1} p^{m - 1} + \cdots + a_2 p^2 + a_1 p + a_0} - \paren {a_m + a_{m - 1} + \cdots + a_2 + a_1 + a_0} } {p - 1}\)
\(\ds \) \(=\) \(\ds \dfrac {n - r} {p - 1}\)


Hence the result.

$\blacksquare$


Source of Name

This entry was named for Adrien-Marie Legendre.


Sources