Difference between revisions of "Legendre's Formula"

Line 4: Line 4:
  
 
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>.
 +
 +
==Examples==
 +
Find the largest integer <math>k</math> for which <math>2^k</math> divides <math>27!</math>
 +
 +
===Solution 1===
 +
Using the first form of Legendre's Formula, substituting <math>n=27</math> and <math>p=2</math> gives
 +
<cmath>\begin{align*}e_2(27!)=&\left\lfloor\frac{27}{2}\right\rfloor+\left\lfloor\frac{27}{2^2}\right\rfloor+\left\lfloor\frac {27}{2^3}\right\rfloor+\left\lfloor\frac{27}{2^4}\right\rfloor\
 +
=&13+6+3+1\
 +
=&23\end{align*}</cmath>
 +
which means that the largest integer <math>k</math> for which <math>2^k</math> divides <math>27!</math> is <math>\boxed{23}</math>.
 +
 +
===Solution 2===
 +
Using the second form of Legendre's Formula, substituting <math>n=27</math> and <math>p=2</math> gives
 +
<cmath>e_2(27!)=\frac{27-S_2(27)}{2-1}=27-S_2(27)</cmath>
 +
The number <math>27</math> when expressed in Base-2 is <math>11011</math>. This gives us <math>S_2(27)=1+1+0+1+1=4</math>. Therefore,
 +
<cmath>e_2(27!)=27-S_2(27)=27-4=23</cmath>
 +
which means that the largest integer <math>k</math> for which <math>2^k</math> divides <math>27!</math> is <math>\boxed{23}</math>.
  
 
==Proofs==
 
==Proofs==

Revision as of 20:59, 26 June 2019

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$.

Examples

Find the largest integer $k$ for which $2^k$ divides $27!$

Solution 1

Using the first form of Legendre's Formula, substituting $n=27$ and $p=2$ gives \begin{align*}e_2(27!)=&\left\lfloor\frac{27}{2}\right\rfloor+\left\lfloor\frac{27}{2^2}\right\rfloor+\left\lfloor\frac {27}{2^3}\right\rfloor+\left\lfloor\frac{27}{2^4}\right\rfloor\\ =&13+6+3+1\\ =&23\end{align*} which means that the largest integer $k$ for which $2^k$ divides $27!$ is $\boxed{23}$.

Solution 2

Using the second form of Legendre's Formula, substituting $n=27$ and $p=2$ gives \[e_2(27!)=\frac{27-S_2(27)}{2-1}=27-S_2(27)\] The number $27$ when expressed in Base-2 is $11011$. This gives us $S_2(27)=1+1+0+1+1=4$. Therefore, \[e_2(27!)=27-S_2(27)=27-4=23\] which means that the largest integer $k$ for which $2^k$ divides $27!$ is $\boxed{23}$.

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 $\left\lfloor \frac{n}{p}\right\rfloor$. But the multiples of $p^2$ are only counted once, when they should be counted twice. So we need to add $\left\lfloor \frac{n}{p^2}\right\rfloor$ on. But this only counts the multiples of $p^3$ twice, when we need to count them thrice. Therefore we must add a $\left\lfloor \frac{n}{p^3}\right\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 $\left\lfloor \frac{n}{p^i}\right\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{align*} \sum_{j=1}^{x} e_j\cdot(p^{j-1}+p^{j-2}+\cdots +1) &= \sum_{j=1}^{x} e_j \left( \frac{p^j-1}{p-1} \right) \\ &=\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{align*}

Problems

Introductory

Olympiad

  • Let $b_m$ be numbers of factors $2$ of the number $m!$ (that is, $2^{b_m}|m!$ and $2^{b_m+1}\nmid m!$). Find the least $m$ such that $m-b_m = 1990$. (Turkey TST 1990)

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