Legendreův vzorec
Author
Albert FloresLegendreův vzorec (také De Polignacův vzorec) dovoluje vypočítat nejvyšší exponent u prvočísla p, kde p umocněné na tento exponent ještě dělí číslo n! (faktoriál přirozeného čísla n). Jedná se v podstatě o výpočet p-adické valuace čísla n!.
Pomocí Legendreova vzorce lze dokázat například nekonečnost počtu prvočísel.
Základní vzorec
Buď n \in \mathbb{N}, p \geq 2 prvočíslo, které dělí n!. Potom
v_p(n!) = \sum_{k=1}^{N} \left\lfloor \frac{n}{p^k} \right\rfloor, kde p^N \leq n \leq p^{N+1}, tj. N=\left\lfloor \frac{\log n}{\log p} \right\rfloor=\left\lfloor \log_{p} n \right\rfloor.
Kde v_p(n!) je exponent u prvočísla 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:
Najděte v_2(17!).
Tzn. najděte takové k \in \mathbb{N}, že 2^k dělí 17!, 2^{k+1} nedělí 17!.
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 \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...
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 \left\lfloor \frac{17}{4} \right\rfloor = 4 dvojky z násobků čísla 4.
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 \left\lfloor \frac{17}{8} \right\rfloor = 2 dvojky z násobků čísla 8 a \left\lfloor \frac{17}{16} \right\rfloor = 1 dvojka z násobků čísla 16.
V součtu je zde tedy tento počet dvojek:
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: 2^{15} dělí 17!, 2^{16} ale už nedělí 17!.
Odtud již plyne výše zmíněný Legendreův vzorec.
Co se týče počtu sčítanců:
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é N \in \mathbb{N}.
Řešený příklad č. 1
Kolika nulami končí dekadický zápis čísla 2015! ?
Řešení: Zadání lze vyslovit také takto: Kolik je v čísle 2015. obsaženo desítek, tedy pětek a dvojek současně. +more Dvojek bude samozřejmě více než pětek, proto nám stačí zjistit počet pětek, tedy v_5(2015. ).
v_5(2015!) = \sum_{j=1}^{N} \left\lfloor \frac{2015}{5^j} \right\rfloor, kde N = \left\lfloor \frac{\log 2015}{\log 5} \right\rfloor = 4
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
2015! \doteq 1,153695 \cdot 10^{5785}
Závěr: Číslo 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:
v_p(n!) \leq \frac{n-1}{p-1}
přičemž rovnost nastane právě tehdy, když n = p^N.
Příklad
Odhad pro v_5(2015!) z výše zmíněného řešeného příkladu:
v_5(2015!) \leq \frac{2014}{4} = 503,5
Což je velmi dobrý odhad čísla 502.
Důkaz
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 \frac{1}{p} \neq 1.
Z toho získáme:
\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 p^N \leq n
Pro n = p^N jsou všude výše místo nerovností rovnosti. Naopak například pro p^N je poslední nerovnost ostrá.
Lepší Legendreův vzorec
Buď n \in \mathbb{N}, p \geq 2 prvočíslo, které dělí n!. Buď
v_p(n!) = \sum_{k=1}^{N} \left\lfloor \frac{n}{p^k} \right\rfloor, kde p^N \leq n \leq p^{N+1}, tj. N=\left\lfloor \frac{\log n}{\log p} \right\rfloor=\left\lfloor \log_{p} n \right\rfloor.
Potom
v_p(n!) = \frac{n-s_p(n)}{p-1}
kde s_p(n) je ciferný součet čísla n zapsaného v soustavě o základu p.
Příklad
7 = 1 \cdot 2^2 + 1 \cdot 2^1 + 1 \cdot 2^0 = (111)_2
s_2(7) = 1 + 1 + 1 = 3
Odtud
v_2(7!) = \frac{7-3}{2-1} = 4
Důkaz
Přirozené číslo n lze v libovolné soustavě o základu p zapsat jako:
n = a_kp^k + a_{k-1}p^{k-1} + ... + a_1p + a_0
kde a_i \in \left \{ 0, 1, ..., p-1 \right \}, tj. p^k \leq n \leq p^{k+1}.
Platí tedy
s_p(n) = a_k + a_{k-1} + ... + a_1 + a_0
v_p(n!) = \sum_{j=1}^{k} \left\lfloor \frac{n}{p^j} \right\rfloor
Sčítance této sumy vypadají následovně:
\left\lfloor \frac{n}{p} \right\rfloor = a_kp^{k-1} + a_{k-1}p^{k-2} + ... + a_2p + a_1
\left\lfloor \frac{n}{p^2} \right\rfloor = a_kp^{k-2} + a_{k-1}p^{k-3} + ... + a_2
...
\left\lfloor \frac{n}{p^{k-1}} \right\rfloor = a_kp + a_{k-1}
\left\lfloor \frac{n}{p^k} \right\rfloor = a_k
Takže platí:
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 + . +more \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.
= 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}
= \frac{1}{p-1}\left [ \left ( a_kp^k + a_{k-1}p^{k-1} + ... + a_1p + 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 n a druhý člen je roven číslu s_p(n), jak jsou tato čísla rozepsána výše. Proto platí
v_p(n!) = \frac{n-s_p(n)}{p-1}
Řešený příklad č. 2
Najděte všechna přirozená čísla n, pro která 2^{n-1} dělí n!.
Řešení: Tato situace nastane tehdy, když v_2(n!) \geq n - 1.
Přitom víme, že v_2(n!) = \frac{n - s_2(n)}{2 - 1} = n - s_2(n).
Jde tedy o to, kdy n - s_2(n) \geq n - 1, tj. s_2(n) \leq 1.
Možnost s_2(n) = 0 implikuje n = 0, ale potom n \notin \mathbb{N}.
Možnost s_2(n) = 1 nastává právě tehdy, když n = 2^k pro libovolné k \in \mathbb{N}_0.
Pravidla pro počítání se vzorcem
Dá se snadno ověřit, že platí následující vztahy:
v_p\left ( a \cdot b \right ) = v_p(a) + v_p(b) (protože pro prvočísla v rozkladech čísel a, b platí p^k \cdot p^m = p^{k+m})
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 m, n a prvočíslo p platí:
v_p\left ( \binom{n + m}{m} \right ) = \frac{s_p(n) + s_p(m) - s_p(m+n)}{p-1}
Řešení:
v_p\left ( \binom{n + m}{m} \right ) = v_p\left ( \frac{(n + m). }{n. +morem. } \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:
n!=\textstyle \prod_{p} \displaystyle p^{v_p(n)}
Podle definice Legendreova vzorce také platí:
v_p(n)=\sum_{k=1}\left \lfloor \frac{n}{p^k} \right \rfloor
Odtud vyplývá, že:
n!
Z toho by ovšem vyplynul nepravdivý výrok, že:
\textstyle \lim_{n \to \infty} \displaystyle \frac{\left ( \textstyle \prod_{p} \displaystyle p \right )^n}{n!} = 0