Legendreova formula

Izvor: Wikipedija
Prijeđi na navigaciju Prijeđi na pretraživanje

Legendreova formula je teorem u elementarnoj teoriji brojeva pomoću kojega se dobiva najveći eksponent kojim neki prosti broj dijeli

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 tada za neki prosti i prirodni broj [1]

Dokaz[uredi | uredi kôd]

Kako je umnožak cijelih brojeva od 1 do 500 slijedi da dobivamo barem jedan faktor od u raspisu broja za svaki višekratnik od u skupu kojih ima No, svaki višekratnik od daje dodatni faktor od , a tih višekratnika ima , pa ih moramo brojati još jednom (ukupno dva puta), svaki višekratnik od daje dodatni faktor od , a tih višekratnika ima , pa ih moramo brojati još jednom (ukupno tri puta), itd.

Prema tome, ukupan broj faktora koji se pojavljuju u raspisu broja ima jer će za neki svi pribrojnici u toj sumi, počevši od , biti manji od 1 pa ćemo ih zaokruživati na nulu.[2]

Primjer[uredi | uredi kôd]

Želimo saznati koliko sedmica se pojavljuje u prostoj faktorizaciji broja

Primjerice, broj 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

Dakle, tražimo koliko ima brojeva od 1 do 500 koji imaju barem jedan faktor u svom raspisu, tj. one koji su djeljivi sa sedam. Njih ima (svaki sedmi).

No, od tih 71, brojeva od 1 do 500 koji imaju barem dva faktora (svaki 49.) u svom raspisu ima pa njih treba brojati dva puta.

Slično, brojeva koji u svom raspisu imaju tri sedmice (svaki 343.) ima pa njih treba brojati tri puta.

Prema tome, odgovor je

Taj zbroj je jednak odnosno što zaista daje

Izvori[uredi | uredi kôd]

  1. Andrej Dujella, Teorija brojeva, Školska knjiga, Zagreb, 2019.
  2. https://artofproblemsolving.com/wiki/index.php/Legendre%27s_Formula