Legendre-képlet

Sablon:Nincs forrás Legendre 1808-ban fedezte fel hogyan kell kiszámítani, hogy mi az a legnagyobb hatványa egy $p$ prímszámnak, ami $n$ faktoriálisát osztja, eszerint $p$ kitevője:

${\epsilon }_p(n)=\sum _{k=1}^{\lfloor {\log }_{p}n\rfloor }\lfloor \frac{n}{p^k}\rfloor$

Bizonyítás

$n$-ig pontosan $\lfloor \frac{n}{p}\rfloor$ darab szám osztható $p$-vel (minden $p$-edik), mindegyik egyet ad $p$ kitevőjéhez. Továbbá $\lfloor \frac{n}{p^2}\rfloor$ darab osztható még $p^2$-tel is, ezek mind még egyet adnak $p$ kitevőjéhez. Az eljárást folytatva kapjuk $p$ kitevőjére a fenti képletet. Nyilván elég addig elmenni az összegzésben, amíg még $p^k\le n$ teljesül, hiszen annál nagyobb $p$ hatványok már nem szerepelnek $n!$-ban.

Alkalmazás

Programozásban klasszikus példa, hogy adott $n$-re $n!$ hány darab nullára végződik. A fenti tétel erre megadja a választ, mivel triviálisan ${\epsilon }_5(n)\le {\epsilon }_2(n)$, ezért a válasz rá ${\epsilon }_5(n)$, ami ezáltal gyorsan és kevés memóriával kiszámítható, anélkül, hogy $n!$ értékét konkrétan kiszámítanánk, ami egy nagy szám.