Legendreova formula

Legendreova formula je teorem u elementarnoj teoriji brojeva pomoću kojega se dobiva najveći eksponent kojim neki prosti broj $p$ dijeli $n!=n(n-1)\cdot \cdot \cdot 2\cdot 1.$

Formula je nazvana prema francuskom matematičaru Adrienu-Marieu Legendreu. Ponegdje je poznata i kao de Polignacova formula po Alphonseu de Polignacu.

Strogi iskaz ovog teorema kaže da ako $p^{\alpha }||n!$ tada $\alpha =\sum _{i=1}^{\mathrm{\infty }}\lfloor \frac{n}{p^i}\rfloor$ za neki prosti $p$ i prirodni broj $n>1.$

Dokaz

Kako je $n!$ umnožak cijelih brojeva od 1 do 500 slijedi da dobivamo barem jedan faktor od $p$ u raspisu broja $n!$ za svaki višekratnik od $p$ u skupu $\{1,2,...,n\}$ kojih ima $\lfloor \frac{n}{p}\rfloor .$ No, svaki višekratnik od $p^2$ daje dodatni faktor od $p$, a tih višekratnika ima $\lfloor \frac{n}{p^2}\rfloor$, pa ih moramo brojati još jednom (ukupno dva puta), svaki višekratnik od $p^3$ daje dodatni faktor od $p$, a tih višekratnika ima $\lfloor \frac{n}{p^3}\rfloor$, pa ih moramo brojati još jednom (ukupno tri puta), itd.

Prema tome, ukupan broj faktora $p$ koji se pojavljuju u raspisu broja $n!$ ima $\sum _{i=1}^{\mathrm{\infty }}\lfloor \frac{n}{p^i}\rfloor$ jer će za neki $m\in \mathbb{N}$ svi pribrojnici u toj sumi, počevši od $\frac{n}{p^m}$, biti manji od 1 pa ćemo ih zaokruživati na nulu.

Primjer

Želimo saznati koliko sedmica se pojavljuje u prostoj faktorizaciji broja $x=500!=500\cdot 499\cdot ...\cdot 2\cdot 1.$

Primjerice, broj $500$ očito nema sedmica u svom raspisu jer nije djeljiv sa sedam pa on neće na traženi način doprinijeti u raspisu broja $x.$

Dakle, tražimo koliko ima brojeva od 1 do 500 koji imaju barem jedan faktor $7$ u svom raspisu, tj. one koji su djeljivi sa sedam. Njih ima $\lfloor \frac{500}{7}\rfloor =71$ (svaki sedmi).

No, od tih 71, brojeva od 1 do 500 koji imaju barem dva faktora $7$ (svaki 49.) u svom raspisu ima $\lfloor \frac{500}{7\cdot 7}\rfloor =10$ pa njih treba brojati dva puta.

Slično, brojeva koji u svom raspisu imaju tri sedmice (svaki 343.) ima $\lfloor \frac{500}{7\cdot 7\cdot 7}\rfloor =1$ pa njih treba brojati tri puta.

Prema tome, odgovor je $71+10+1=82.$

Taj zbroj je jednak $\sum _{i=1}^{\mathrm{\infty }}\lfloor \frac{500}{7^i}\rfloor$ odnosno $\lfloor \frac{500}{7}\rfloor +\lfloor \frac{500}{7^2}\rfloor +\lfloor \frac{500}{7^3}\rfloor +\lfloor \frac{500}{7^4}\rfloor +...$ što zaista daje $71+10+1+0+0+...=82.$