Legendreův vzorec

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

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

Základní vzorec

Buď ${\displaystyle n\in \mathbb {N} }$, ${\displaystyle p\geq 2}$ prvočíslo, které dělí ${\displaystyle n!}$. Potom

${\displaystyle v_{p}(n!)=\sum _{k=1}^{N}\left\lfloor {\frac {n}{p^{k}}}\right\rfloor }$, kde ${\displaystyle p^{N}\leq n\leq p^{N+1}}$, tj. ${\displaystyle N=\left\lfloor {\frac {\log n}{\log p}}\right\rfloor =\left\lfloor \log _{p}n\right\rfloor }$.

Kde ${\displaystyle v_{p}(n!)}$ je exponent u prvočísla ${\displaystyle p}$, sčítance sumy jsou uzavřeny v dolní celé části.

Odvození vzorce

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

Najděte ${\displaystyle v_{2}(17!)}$.

Tzn. najděte takové ${\displaystyle k\in \mathbb {N} }$, že ${\displaystyle 2^{k}}$ dělí ${\displaystyle 17!}$, ${\displaystyle 2^{k+1}}$ nedělí ${\displaystyle 17!}$.

${\displaystyle 17!=1\cdot {\color {red}2}\cdot 3\cdot {\color {red}4}\cdot 5\cdot {\color {red}6}\cdot 7\cdot {\color {red}8}\cdot 9\cdot {\color {red}10}\cdot 11\cdot {\color {red}12}\cdot 13\cdot {\color {red}14}\cdot 15\cdot {\color {red}16}\cdot 17}$

Máme zde tedy ${\displaystyle \left\lfloor {\frac {17}{2}}\right\rfloor =8}$ dvojek z násobků čísla 2. Musíme ale zahrnout i další dvojky, z násobků čísel 4, 8...

${\displaystyle 17!=1\cdot 2\cdot 3\cdot {\color {green}4}\cdot 5\cdot 6\cdot 7\cdot {\color {green}8}\cdot 9\cdot 10\cdot 11\cdot {\color {green}12}\cdot 13\cdot 14\cdot 15\cdot {\color {green}16}\cdot 17}$

Dále zde je tedy ${\displaystyle \left\lfloor {\frac {17}{4}}\right\rfloor =4}$ dvojky z násobků čísla 4.

${\displaystyle 17!=1\cdot 2\cdot 3\cdot 4\cdot 5\cdot 6\cdot 7\cdot {\color {blue}8}\cdot 9\cdot 10\cdot 11\cdot 12\cdot 13\cdot 14\cdot 15\cdot {\color {blue}16}\cdot 17}$

Podobně jsou zde ${\displaystyle \left\lfloor {\frac {17}{8}}\right\rfloor =2}$ dvojky z násobků čísla 8 a ${\displaystyle \left\lfloor {\frac {17}{16}}\right\rfloor =1}$ dvojka z násobků čísla 16.

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

${\displaystyle v_{2}(17!)=\left\lfloor {\frac {17}{2}}\right\rfloor +\left\lfloor {\frac {17}{4}}\right\rfloor +\left\lfloor {\frac {17}{8}}\right\rfloor +\left\lfloor {\frac {17}{16}}\right\rfloor =8+4+2+1=15}$

Závěr: ${\displaystyle 2^{15}}$ dělí ${\displaystyle 17!}$, ${\displaystyle 2^{16}}$ ale už nedělí ${\displaystyle 17!}$.

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

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

${\displaystyle p^{N}\leq n\leq p^{N+1}\Rightarrow N\cdot \log p\leq \log n\leq (N+1)\cdot \log p\Rightarrow N\leq {\frac {\log n}{\log p}}\leq N+1\Rightarrow N=\left\lfloor {\frac {\log n}{\log p}}\right\rfloor }$

Protože nerovnosti vyhovuje pouze jediné ${\displaystyle N\in \mathbb {N} }$.

Řešený příklad č. 1

Kolika nulami končí dekadický zápis čísla ${\displaystyle 2015!}$ ?

Řešení: Zadání lze vyslovit také takto: Kolik je v čísle ${\displaystyle 2015!}$ 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 ${\displaystyle v_{5}(2015!)}$.

${\displaystyle v_{5}(2015!)=\sum _{j=1}^{N}\left\lfloor {\frac {2015}{5^{j}}}\right\rfloor }$, kde ${\displaystyle N=\left\lfloor {\frac {\log 2015}{\log 5}}\right\rfloor =4}$

${\displaystyle v_{5}(2015!)=\left\lfloor {\frac {2015}{5}}\right\rfloor +\left\lfloor {\frac {2015}{25}}\right\rfloor +\left\lfloor {\frac {2015}{125}}\right\rfloor +\left\lfloor {\frac {2015}{625}}\right\rfloor =403+80+16+3=502}$

${\displaystyle 2015!\doteq 1,153695\cdot 10^{5785}}$

Závěr: Číslo ${\displaystyle 2015!}$ 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:

${\displaystyle v_{p}(n!)\leq {\frac {n-1}{p-1}}}$

přičemž rovnost nastane právě tehdy, když ${\displaystyle n=p^{N}}$.

Příklad

Odhad pro ${\displaystyle v_{5}(2015!)}$ z výše zmíněného řešeného příkladu:

${\displaystyle v_{5}(2015!)\leq {\frac {2014}{4}}=503,5}$

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

Důkaz

${\displaystyle v_{p}(n!)=\sum _{k=1}^{N}\left\lfloor {\frac {n}{p^{k}}}\right\rfloor \leq \sum _{k=1}^{N}{\frac {n}{p^{k}}}={\frac {n}{p}}\left(1+{\frac {1}{p}}+{\frac {1}{p^{2}}}+...+{\frac {1}{p^{N-1}}}\right)}$

Pravá strana nerovnice je zároveň součtem geometrické řady s kvocientem ${\displaystyle {\frac {1}{p}}\neq 1}$.

Z toho získáme:

${\displaystyle {\frac {n}{p}}\cdot {\frac {1-{\frac {1}{p^{N}}}}{1-{\frac {1}{p}}}}={\frac {n-{\frac {n}{p^{N}}}}{p-1}}\leq {\frac {n-1}{p-1}}}$ pro ${\displaystyle p^{N}\leq n}$

Pro ${\displaystyle n=p^{N}}$ jsou všude výše místo nerovností rovnosti. Naopak například pro ${\displaystyle p^{N}<N}$ je poslední nerovnost ostrá.

Lepší Legendreův vzorec

Buď ${\displaystyle n\in \mathbb {N} }$, ${\displaystyle p\geq 2}$ prvočíslo, které dělí ${\displaystyle n!}$. Buď

${\displaystyle v_{p}(n!)=\sum _{k=1}^{N}\left\lfloor {\frac {n}{p^{k}}}\right\rfloor }$, kde ${\displaystyle p^{N}\leq n\leq p^{N+1}}$, tj. ${\displaystyle N=\left\lfloor {\frac {\log n}{\log p}}\right\rfloor =\left\lfloor \log _{p}n\right\rfloor }$.

Potom

${\displaystyle v_{p}(n!)={\frac {n-s_{p}(n)}{p-1}}}$

kde ${\displaystyle s_{p}(n)}$ je ciferný součet čísla ${\displaystyle n}$ zapsaného v soustavě o základu ${\displaystyle p}$.

Příklad

${\displaystyle 7=1\cdot 2^{2}+1\cdot 2^{1}+1\cdot 2^{0}=(111)_{2}}$

${\displaystyle s_{2}(7)=1+1+1=3}$

Odtud

${\displaystyle v_{2}(7!)={\frac {7-3}{2-1}}=4}$

Důkaz

Přirozené číslo ${\displaystyle n}$ lze v libovolné soustavě o základu ${\displaystyle p}$ zapsat jako:

${\displaystyle n=a_{k}p^{k}+a_{k-1}p^{k-1}+...+a_{1}p+a_{0}}$

kde ${\displaystyle a_{i}\in \left\{0,1,...,p-1\right\}}$, tj. ${\displaystyle p^{k}\leq n\leq p^{k+1}}$.

Platí tedy

${\displaystyle s_{p}(n)=a_{k}+a_{k-1}+...+a_{1}+a_{0}}$

${\displaystyle v_{p}(n!)=\sum _{j=1}^{k}\left\lfloor {\frac {n}{p^{j}}}\right\rfloor }$

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

${\displaystyle \left\lfloor {\frac {n}{p}}\right\rfloor =a_{k}p^{k-1}+a_{k-1}p^{k-2}+...+a_{2}p+a_{1}}$

${\displaystyle \left\lfloor {\frac {n}{p^{2}}}\right\rfloor =a_{k}p^{k-2}+a_{k-1}p^{k-3}+...+a_{2}}$

...

${\displaystyle \left\lfloor {\frac {n}{p^{k-1}}}\right\rfloor =a_{k}p+a_{k-1}}$

${\displaystyle \left\lfloor {\frac {n}{p^{k}}}\right\rfloor =a_{k}}$

Takže platí:

${\displaystyle v_{p}(n!)=\sum _{j=1}^{k}\left\lfloor {\frac {n}{p^{j}}}\right\rfloor =\left\lfloor {\frac {n}{p}}\right\rfloor +\left\lfloor {\frac {n}{p^{2}}}\right\rfloor +...\left\lfloor {\frac {n}{p^{k}}}\right\rfloor =a_{k}\left(1+p+p^{2}+...+p^{k-1}\right)+a_{k-1}\left(1+p+...+p^{k-2}\right)+a_{2}\left(1+p\right)+a_{1}}$

${\displaystyle =a_{k}{\frac {p^{k}-1}{p-1}}+a_{k-1}{\frac {p^{k-1}}{p-1}}+...+a_{2}{\frac {p^{2}-1}{p-1}}+a_{1}{\frac {p-1}{p-1}}}$

${\displaystyle ={\frac {1}{p-1}}\left[\left(a_{k}p^{k}+a_{k-1}p^{k-1}+...+a_{1}p+a_{0}\right)-\left(a_{k}+a_{k-1}+...+a_{1}+a_{0}\right)\right]}$

Nyní můžeme vidět, že první člen v hranaté závorce je roven číslu ${\displaystyle n}$ a druhý člen je roven číslu ${\displaystyle s_{p}(n)}$, jak jsou tato čísla rozepsána výše. Proto platí

${\displaystyle v_{p}(n!)={\frac {n-s_{p}(n)}{p-1}}}$

Řešený příklad č. 2

Najděte všechna přirozená čísla ${\displaystyle n}$, pro která ${\displaystyle 2^{n-1}}$ dělí ${\displaystyle n!}$.

Řešení: Tato situace nastane tehdy, když ${\displaystyle v_{2}(n!)\geq n-1}$.

Přitom víme, že ${\displaystyle v_{2}(n!)={\frac {n-s_{2}(n)}{2-1}}=n-s_{2}(n)}$.

Jde tedy o to, kdy ${\displaystyle n-s_{2}(n)\geq n-1}$, tj. ${\displaystyle s_{2}(n)\leq 1}$.

Možnost ${\displaystyle s_{2}(n)=0}$ implikuje ${\displaystyle n=0}$, ale potom ${\displaystyle n\notin \mathbb {N} }$.

Možnost ${\displaystyle s_{2}(n)=1}$ nastává právě tehdy, když ${\displaystyle n=2^{k}}$ pro libovolné ${\displaystyle k\in \mathbb {N} _{0}}$.

Pravidla pro počítání se vzorcem

Dá se snadno ověřit, že platí následující vztahy:

${\displaystyle v_{p}\left(a\cdot b\right)=v_{p}(a)+v_{p}(b)}$ (protože pro prvočísla v rozkladech čísel a, b platí ${\displaystyle p^{k}\cdot p^{m}=p^{k+m}}$)

${\displaystyle v_{p}\left({\frac {a}{b}}\right)=v_{p}(a)-v_{p}(b)}$ (podobný důkaz)

Řešený příklad č. 3

Dokažte, že pro libovolná čísla ${\displaystyle m}$, ${\displaystyle n}$ a prvočíslo ${\displaystyle p}$ platí:

${\displaystyle v_{p}\left({\binom {n+m}{m}}\right)={\frac {s_{p}(n)+s_{p}(m)-s_{p}(m+n)}{p-1}}}$

Řešení:

${\displaystyle v_{p}\left({\binom {n+m}{m}}\right)=v_{p}\left({\frac {(n+m)!}{n!m!}}\right)=v_{p}((n+m)!)-v_{p}(n!)-v_{p}(m!)={\frac {n+m-s_{p}(m+n)}{p-1}}-{\frac {n-s_{p}(n)}{p-1}}-{\frac {m-s_{p}(m)}{p-1}}={\frac {s_{p}(n)+s_{p}(m)-s_{p}(m+n)}{p-1}}}$

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:^[3]

${\displaystyle n!=\textstyle \prod _{p}\displaystyle p^{v_{p}(n)}}$

Podle definice Legendreova vzorce také platí:

${\displaystyle v_{p}(n)=\sum _{k=1}\left\lfloor {\frac {n}{p^{k}}}\right\rfloor <\sum _{k=1}{\frac {n}{p^{k}}}={\frac {n}{p-1}}\leq n}$

Odtud vyplývá, že:

${\displaystyle n!<\left(\textstyle \prod _{p}\displaystyle p\right)^{n}}$

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

${\displaystyle \textstyle \lim _{n\to \infty }\displaystyle {\frac {\left(\textstyle \prod _{p}\displaystyle p\right)^{n}}{n!}}=0}$

Reference