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}^{\infty }\left\lfloor {\frac {n}{p^{i}}}\right\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 $\left\lfloor {\frac {n}{p}}\right\rfloor .$ No, svaki višekratnik od $p^{2}$ daje dodatni faktor od $p$, a tih višekratnika ima $\left\lfloor {\frac {n}{p^{2}}}\right\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 $\left\lfloor {\frac {n}{p^{3}}}\right\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}^{\infty }\left\lfloor {\frac {n}{p^{i}}}\right\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 $\left\lfloor {\frac {500}{7}}\right\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 $\left\lfloor {\frac {500}{7\cdot 7}}\right\rfloor =10$ pa njih treba brojati dva puta.

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

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

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