Legendre-képlet

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:

$\varepsilon _{p}(n)=\sum _{k=1}^{\left\lfloor \log _{p}n\right\rfloor }\left\lfloor {\frac {n}{p^{k}}}\right\rfloor$

Bizonyítás

$n$-ig pontosan $\left\lfloor {\frac {n}{p}}\right\rfloor$ darab szám osztható $p$-vel (minden $p$-edik), mindegyik egyet ad $p$ kitevőjéhez. Továbbá $\left\lfloor {\frac {n}{p^{2}}}\right\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}\leq 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 $\varepsilon _{5}(n)\leq \varepsilon _{2}(n)$, ezért a válasz rá $\varepsilon _{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.