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\ge 2$ prvočíslo, které dělí $n!$. Potom

$v_p(n!)=\sum _{k=1}^N\lfloor \frac{n}{p^k}\rfloor$, kde $p^N\le n\le p^{N+1}$, tj. $N=\lfloor \frac{\log n}{\log p}\rfloor =\lfloor {\log }_{p}n\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 2\cdot 3\cdot 4\cdot 5\cdot 6\cdot 7\cdot 8\cdot 9\cdot 10\cdot 11\cdot 12\cdot 13\cdot 14\cdot 15\cdot 16\cdot 17$

Máme zde tedy $\lfloor \frac{17}{2}\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 4\cdot 5\cdot 6\cdot 7\cdot 8\cdot 9\cdot 10\cdot 11\cdot 12\cdot 13\cdot 14\cdot 15\cdot 16\cdot 17$

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

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

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

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

$v_2(17!)=\lfloor \frac{17}{2}\rfloor +\lfloor \frac{17}{4}\rfloor +\lfloor \frac{17}{8}\rfloor +\lfloor \frac{17}{16}\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\le n\le p^{N+1}\Rightarrow N\cdot \log p\le \log n\le (N+1)\cdot \log p\Rightarrow N\le \frac{\log n}{\log p}\le N+1\Rightarrow N=\lfloor \frac{\log n}{\log p}\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ě? 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\lfloor \frac{2015}{5^j}\rfloor$, kde $N=\lfloor \frac{\log 2015}{\log 5}\rfloor =4$

$v_5(2015!)=\lfloor \frac{2015}{5}\rfloor +\lfloor \frac{2015}{25}\rfloor +\lfloor \frac{2015}{125}\rfloor +\lfloor \frac{2015}{625}\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!)\le \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!)\le \frac{2014}{4}=503,5$

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

Důkaz

$v_p(n!)=\sum _{k=1}^N\lfloor \frac{n}{p^k}\rfloor \le \sum _{k=1}^N\frac{n}{p^k}=\frac{n}{p}(1+\frac{1}{p}+\frac{1}{p^2}+...+\frac{1}{p^{N-1}})$

Pravá strana nerovnice je zároveň součtem geometrické řady s kvocientem $\frac{1}{p}\ne 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}\le \frac{n-1}{p-1}$ pro $p^N\le n$

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

Lepší Legendreův vzorec

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

$v_p(n!)=\sum _{k=1}^N\lfloor \frac{n}{p^k}\rfloor$, kde $p^N\le n\le p^{N+1}$, tj. $N=\lfloor \frac{\log n}{\log p}\rfloor =\lfloor {\log }_{p}n\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_k{p}^k+a_{k-1}{p}^{k-1}+...+a_{1}p+a_0$

kde $a_i\in \{0,1,...,p-1\}$, tj. $p^k\le n\le p^{k+1}$.

Platí tedy

$s_p(n)=a_k+a_{k-1}+...+a_1+a_0$

$v_p(n!)=\sum _{j=1}^k\lfloor \frac{n}{p^j}\rfloor$

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

$\lfloor \frac{n}{p}\rfloor =a_k{p}^{k-1}+a_{k-1}{p}^{k-2}+...+a_{2}p+a_1$

$\lfloor \frac{n}{p^2}\rfloor =a_k{p}^{k-2}+a_{k-1}{p}^{k-3}+...+a_2$

...

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

$\lfloor \frac{n}{p^k}\rfloor =a_k$

Takže platí:

$v_p(n!)=\sum _{j=1}^k\lfloor \frac{n}{p^j}\rfloor =\lfloor \frac{n}{p}\rfloor +\lfloor \frac{n}{p^2}\rfloor +...\lfloor \frac{n}{p^k}\rfloor =a_k(1+p+p^2+...+p^{k-1})+a_{k-1}(1+p+...+p^{k-2})+a_2(1+p)+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}[(a_k{p}^k+a_{k-1}{p}^{k-1}+...+a_{1}p+a_0)-(a_k+a_{k-1}+...+a_1+a_0)]$

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!)\ge 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)\ge n-1$, tj. $s_2(n)\le 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(a\cdot b)=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((\genfrac{}{}{0ex}{}{n+m}{m})\right)=\frac{s_p(n)+s_p(m)-s_p(m+n)}{p-1}$

Řešení:

$v_p\left((\genfrac{}{}{0ex}{}{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:

$n!=\prod _p{p}^{v_p(n)}$

Podle definice Legendreova vzorce také platí:

$v_p(n)=\sum _{k=1}\lfloor \frac{n}{p^k}\rfloor <\sum _{k=1}\frac{n}{p^k}=\frac{n}{p-1}\le n$

Odtud vyplývá, že:

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

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

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