Legendreova formula

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

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 [math]\displaystyle{ p^{\alpha} || n! }[/math] tada [math]\displaystyle{ \alpha = \sum_{i=1}^{\infty} \left\lfloor \frac{n}{p^i} \right\rfloor }[/math] za neki prosti [math]\displaystyle{ p }[/math] i prirodni broj [math]\displaystyle{ n \gt 1. }[/math]

Dokaz

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

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

Primjer

Želimo saznati koliko sedmica se pojavljuje u prostoj faktorizaciji broja [math]\displaystyle{ x = 500! = 500 \cdot 499 \cdot ... \cdot 2 \cdot 1. }[/math]

Primjerice, broj [math]\displaystyle{ 500 }[/math] 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 [math]\displaystyle{ x. }[/math]

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

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

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

Prema tome, odgovor je [math]\displaystyle{ 71 + 10 + 1 = 82. }[/math]

Taj zbroj je jednak [math]\displaystyle{ \sum_{i=1}^{\infty} \left\lfloor \frac{500}{7^i} \right\rfloor }[/math] odnosno [math]\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 + ... }[/math] što zaista daje [math]\displaystyle{ 71 + 10 + 1 + 0 + 0 + ... = 82. }[/math]