Legendreova formula

Legendreova formula je teorem u elementarnoj teoriji brojeva pomoću kojega se dobiva najveći eksponent kojim neki prosti broj $p$ dijeli Obrada nije uspjela. (Conversion error. Server ("https://wikimedia.org/api/rest_") reported: "Cannot get mml. Server problem."): {\displaystyle 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 Obrada nije uspjela. (Conversion error. Server ("https://wikimedia.org/api/rest_") reported: "Cannot get mml. Server problem."): {\displaystyle p^{\alpha }||n!} tada Obrada nije uspjela. (Conversion error. Server ("https://wikimedia.org/api/rest_") reported: "Cannot get mml. Server problem."): {\displaystyle \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 Obrada nije uspjela. (Conversion error. Server ("https://wikimedia.org/api/rest_") reported: "Cannot get mml. Server problem."): {\displaystyle n!} umnožak cijelih brojeva od 1 do 500 slijedi da dobivamo barem jedan faktor od $p$ u raspisu broja Obrada nije uspjela. (Conversion error. Server ("https://wikimedia.org/api/rest_") reported: "Cannot get mml. Server problem."): {\displaystyle n!} za svaki višekratnik od $p$ u skupu Obrada nije uspjela. (Conversion error. Server ("https://wikimedia.org/api/rest_") reported: "Cannot get mml. Server problem."): {\displaystyle \{1,2,...,n\}} kojih ima Obrada nije uspjela. (Conversion error. Server ("https://wikimedia.org/api/rest_") reported: "Cannot get mml. Server problem."): {\displaystyle \left\lfloor {\frac {n}{p}}\right\rfloor .} No, svaki višekratnik od $p^{2}$ daje dodatni faktor od $p$, a tih višekratnika ima Obrada nije uspjela. (Conversion error. Server ("https://wikimedia.org/api/rest_") reported: "Cannot get mml. Server problem."): {\displaystyle \left\lfloor {\frac {n}{p^{2}}}\right\rfloor } , pa ih moramo brojati još jednom (ukupno dva puta), svaki višekratnik od Obrada nije uspjela. (Conversion error. Server ("https://wikimedia.org/api/rest_") reported: "Cannot get mml. Server problem."): {\displaystyle p^{3}} daje dodatni faktor od $p$, a tih višekratnika ima Obrada nije uspjela. (Conversion error. Server ("https://wikimedia.org/api/rest_") reported: "Cannot get mml. Server problem."): {\displaystyle \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 Obrada nije uspjela. (Conversion error. Server ("https://wikimedia.org/api/rest_") reported: "Cannot get mml. Server problem."): {\displaystyle n!} ima $\sum _{i=1}^{\infty }\left\lfloor {\frac {n}{p^{i}}}\right\rfloor$ jer će za neki Obrada nije uspjela. (Conversion error. Server ("https://wikimedia.org/api/rest_") reported: "Cannot get mml. Server problem."): {\displaystyle m\in \mathbb {N} } svi pribrojnici u toj sumi, počevši od Obrada nije uspjela. (Conversion error. Server ("https://wikimedia.org/api/rest_") reported: "Cannot get mml. Server problem."): {\displaystyle {\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 Obrada nije uspjela. (Conversion error. Server ("https://wikimedia.org/api/rest_") reported: "Cannot get mml. Server problem."): {\displaystyle x=500!=500\cdot 499\cdot ...\cdot 2\cdot 1.}

Primjerice, broj Obrada nije uspjela. (Conversion error. Server ("https://wikimedia.org/api/rest_") reported: "Cannot get mml. Server problem."): {\displaystyle 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 Obrada nije uspjela. (Conversion error. Server ("https://wikimedia.org/api/rest_") reported: "Cannot get mml. Server problem."): {\displaystyle 7} u svom raspisu, tj. one koji su djeljivi sa sedam. Njih ima Obrada nije uspjela. (Conversion error. Server ("https://wikimedia.org/api/rest_") reported: "Cannot get mml. Server problem."): {\displaystyle \left\lfloor {\frac {500}{7}}\right\rfloor =71} (svaki sedmi).

No, od tih 71, brojeva od 1 do 500 koji imaju barem dva faktora Obrada nije uspjela. (Conversion error. Server ("https://wikimedia.org/api/rest_") reported: "Cannot get mml. Server problem."): {\displaystyle 7} (svaki 49.) u svom raspisu ima Obrada nije uspjela. (Conversion error. Server ("https://wikimedia.org/api/rest_") reported: "Cannot get mml. Server problem."): {\displaystyle \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 Obrada nije uspjela. (Conversion error. Server ("https://wikimedia.org/api/rest_") reported: "Cannot get mml. Server problem."): {\displaystyle 71+10+1=82.}

Taj zbroj je jednak Obrada nije uspjela. (MathML sa SVG ili PNG za rezervu (preporučljivo za moderne preglednike i alate za pristupačnost): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle \sum_{i=1}^{\infty} \left\lfloor \frac{500}{7^i} \right\rfloor } odnosno Obrada nije uspjela. (MathML sa SVG ili PNG za rezervu (preporučljivo za moderne preglednike i alate za pristupačnost): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle \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 Obrada nije uspjela. (MathML sa SVG ili PNG za rezervu (preporučljivo za moderne preglednike i alate za pristupačnost): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle 71 + 10 + 1 + 0 + 0 + ... = 82. }