Legendre-képlet

A Wikipédiából, a szabad enciklopédiából
Ugrás a navigációhoz Ugrás a kereséshez

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

Bizonyítás[szerkesztés]

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

Alkalmazás[szerkesztés]

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