Legendreův vzorec
Legendreův vzorec (také De Polignacův vzorec) dovoluje vypočítat nejvyšší exponent u prvočísla , kde  umocněné na tento exponent ještě dělí číslo  (faktoriál přirozeného čísla ). Jedná se v podstatě o výpočet p-adické valuace čísla .

Pomocí Legendreova vzorce lze dokázat například nekonečnost počtu prvočísel.

Základní vzorec 
Buď ,  prvočíslo, které dělí . Potom

, kde , tj. .

Kde  je exponent u prvočísla , sčítance sumy jsou uzavřeny v dolní celé části.

Odvození vzorce 
Odvození vzorce si ukážeme na následujícím příkladu:

Najděte .

Tzn. najděte takové , že  dělí ,  nedělí .

Máme zde tedy  dvojek z násobků čísla 2. Musíme ale zahrnout i další dvojky, z násobků čísel 4, 8...

Dále zde je tedy  dvojky z násobků čísla 4.

Podobně jsou zde  dvojky z násobků čísla 8 a  dvojka z násobků čísla 16.

V součtu je zde tedy tento počet dvojek:

Závěr:  dělí ,  ale už nedělí .

Odtud již plyne výše zmíněný Legendreův vzorec.

Co se týče počtu sčítanců:

Protože nerovnosti vyhovuje pouze jediné .

Řešený příklad č. 1 
Kolika nulami končí dekadický zápis čísla  ?

Řešení: Zadání lze vyslovit také takto: Kolik je v čísle  obsaženo desítek, tedy pětek a dvojek současně?
Dvojek bude samozřejmě více než pětek, proto nám stačí zjistit počet pětek, tedy .

, kde 

Závěr: Číslo  má 5786 cifer, z nichž 502 posledních jsou nuly.

Odhad pro Legendreův vzorec 
Odhad používáme pro zjednodušení výpočtů, avšak za cenu přesnosti. Pro velká čísla totiž může být výše zmíněný vzorec příliš komplikovaný pro výpočet.

Pro odhad platí vzorec:

přičemž rovnost nastane právě tehdy, když .

Příklad 
Odhad pro  z výše zmíněného řešeného příkladu:

Což je velmi dobrý odhad čísla 502.

Důkaz 

Pravá strana nerovnice je zároveň součtem geometrické řady s kvocientem .

Z toho získáme:

 pro 

Pro  jsou všude výše místo nerovností rovnosti. Naopak například pro  je poslední nerovnost ostrá.

Lepší Legendreův vzorec 
Buď ,  prvočíslo, které dělí . Buď

, kde , tj. .

Potom

kde  je ciferný součet čísla  zapsaného v soustavě o základu .

Příklad 

Odtud

Důkaz 
Přirozené číslo  lze v libovolné soustavě o základu  zapsat jako:

kde , tj. .

Platí tedy

Sčítance této sumy vypadají následovně:

...

Takže platí:

Nyní můžeme vidět, že první člen v hranaté závorce je roven číslu  a druhý člen je roven číslu , jak jsou tato čísla rozepsána výše. Proto platí

Řešený příklad č. 2 
Najděte všechna přirozená čísla , pro která  dělí .

Řešení: Tato situace nastane tehdy, když .

Přitom víme, že .

Jde tedy o to, kdy , tj. .

Možnost  implikuje , ale potom .

Možnost  nastává právě tehdy, když  pro libovolné .

Pravidla pro počítání se vzorcem 
Dá se snadno ověřit, že platí následující vztahy:

 (protože pro prvočísla v rozkladech čísel a, b platí )

 (podobný důkaz)

Řešený příklad č. 3 
Dokažte, že pro libovolná čísla ,  a prvočíslo  platí:

Řešení:

Důkaz nekonečného počtu prvočísel 
Pro důkaz předpokládejme, že je počet prvočísel konečný. Potom pro každé přirozené číslo n musí platit podle Legendreova vzorce pro součin přes všechna prvočísla p:

Podle definice Legendreova vzorce také platí:

Odtud vyplývá, že:

Z toho by ovšem vyplynul nepravdivý výrok, že:

Reference 

Teorie čísel