Difference between revisions of "Legendre's Formula"

Revision as of 06:25, 8 August 2018

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

@@ Line 20: / Line 20: @@
 \end{align*}</cmath>
+===Problems===
+==== Introductory====
+====Olympiad====
+* Let <math>b_m</math> be numbers of factors <math>2</math> of the number <math>m!</math> (that is, <math>2^{b_m}|m!</math> and <math>2^{b_m+1}\nmid m!</math>). Find the least <math>m</math> such that <math>m-b_m = 1990</math>. (Turkey TST 1990)
 {{stub}}
 [[Category:Number theory]]
 [[Category:Theorems]]
 [[Category:Definition]]

Page

Toolbox

Search