# Difference between revisions of "Legendre's Formula"

m (fixing broxen latex) |
Borealbear (talk | contribs) |
||

(9 intermediate revisions by 6 users not shown) | |||

Line 3: | Line 3: | ||

<cmath>e_p(n!)=\sum_{i=1}^{\infty} \left\lfloor \dfrac{n}{p^i}\right\rfloor =\frac{n-S_{p}(n)}{p-1}</cmath> | <cmath>e_p(n!)=\sum_{i=1}^{\infty} \left\lfloor \dfrac{n}{p^i}\right\rfloor =\frac{n-S_{p}(n)}{p-1}</cmath> | ||

− | 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== | ||

Line 9: | Line 26: | ||

We use a counting argument. | 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>\left\lfloor \frac{n}{p}\right\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>\left\lfloor \frac{n}{p^2}\right\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>\left\lfloor \frac{n}{p^3}\right\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 <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 | + | 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>\left\lfloor \frac{n}{p^i}\right\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 |

− | <cmath>\begin{align*} \sum_{j=1}^{x} e_j(p^{j-1}+p^{j-2}+\cdots +1) &= \sum_{j=1}^{x} e_j \left( \frac{p^j-1}{p-1} \right) \\ | + | <cmath>\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{\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-e_0)-(S_p(n)-e_0)}{p-1} \\ | ||

Line 20: | Line 37: | ||

\end{align*}</cmath> | \end{align*}</cmath> | ||

+ | ===Problems=== | ||

+ | ==== Introductory==== | ||

+ | * How many zeros are at the end of the base-<math>15</math> representation of <math>50!</math>? | ||

+ | * <math> \binom{4042}{2021}+\binom{4043}{2022} </math> can be written as <math> n\cdot 10^x </math> where <math> n </math> and <math> x </math> are positive integers. What is the largest possible value of <math> x </math>? (BorealBear) | ||

+ | ====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}} | {{stub}} | ||

[[Category:Number theory]] | [[Category:Number theory]] | ||

[[Category:Theorems]] | [[Category:Theorems]] | ||

[[Category:Definition]] | [[Category:Definition]] |

## Latest revision as of 20:05, 27 April 2021

**Legendre's Formula** states that

where is a prime and is the exponent of in the prime factorization of and is the sum of the digits of when written in base .

## Contents

## Examples

Find the largest integer for which divides

### Solution 1

Using the first form of Legendre's Formula, substituting and gives which means that the largest integer for which divides is .

### Solution 2

Using the second form of Legendre's Formula, substituting and gives The number when expressed in Base-2 is . This gives us . Therefore, which means that the largest integer for which divides is .

## Proofs

### Part 1

We use a counting argument.

We could say that is equal to the number of multiples of less than , or . But the multiples of are only counted once, when they should be counted twice. So we need to add on. But this only counts the multiples of twice, when we need to count them thrice. Therefore we must add a on. We continue like this to get . This makes sense, because the terms of this series tend to 0.

### Part 2

Let the base representation of be where the are digits in base Then, the base representation of is Note that the infinite sum of these numbers (which is ) is

### Problems

#### Introductory

- How many zeros are at the end of the base- representation of ?
- can be written as where and are positive integers. What is the largest possible value of ? (BorealBear)

#### Olympiad

- Let be numbers of factors of the number (that is, and ). Find the least such that . (Turkey TST 1990)

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