Legendreův vzorec

Legendreů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

Reference

Kategorie:Teorie čísel