Buď
n
∈
N
{\displaystyle n\in \mathbb {N} }
,
p
≥
2
{\displaystyle p\geq 2}
prvočíslo, které dělí
n
!
{\displaystyle n!}
. Potom
v
p
(
n
!
)
=
∑
k
=
1
N
⌊
n
p
k
⌋
{\displaystyle v_{p}(n!)=\sum _{k=1}^{N}\left\lfloor {\frac {n}{p^{k}}}\right\rfloor }
, kde
p
N
≤
n
≤
p
N
+
1
{\displaystyle p^{N}\leq n\leq p^{N+1}}
, tj.
N
=
⌊
log
n
log
p
⌋
=
⌊
log
p
n
⌋
{\displaystyle N=\left\lfloor {\frac {\log n}{\log p}}\right\rfloor =\left\lfloor \log _{p}n\right\rfloor }
.
Kde
v
p
(
n
!
)
{\displaystyle v_{p}(n!)}
je exponent u prvočísla
p
{\displaystyle p}
, sčítance sumy jsou uzavřeny v dolní celé části .
Odvození vzorce si ukážeme na následujícím příkladu:[2]
Najděte
v
2
(
17
!
)
{\displaystyle v_{2}(17!)}
.
Tzn. najděte takové
k
∈
N
{\displaystyle k\in \mathbb {N} }
, že
2
k
{\displaystyle 2^{k}}
dělí
17
!
{\displaystyle 17!}
,
2
k
+
1
{\displaystyle 2^{k+1}}
nedělí
17
!
{\displaystyle 17!}
.
17
!
=
1
⋅
2
⋅
3
⋅
4
⋅
5
⋅
6
⋅
7
⋅
8
⋅
9
⋅
10
⋅
11
⋅
12
⋅
13
⋅
14
⋅
15
⋅
16
⋅
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
⌊
17
2
⌋
=
8
{\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...
17
!
=
1
⋅
2
⋅
3
⋅
4
⋅
5
⋅
6
⋅
7
⋅
8
⋅
9
⋅
10
⋅
11
⋅
12
⋅
13
⋅
14
⋅
15
⋅
16
⋅
17
{\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
⌊
17
4
⌋
=
4
{\displaystyle \left\lfloor {\frac {17}{4}}\right\rfloor =4}
dvojky z násobků čísla 4.
17
!
=
1
⋅
2
⋅
3
⋅
4
⋅
5
⋅
6
⋅
7
⋅
8
⋅
9
⋅
10
⋅
11
⋅
12
⋅
13
⋅
14
⋅
15
⋅
16
⋅
17
{\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
⌊
17
8
⌋
=
2
{\displaystyle \left\lfloor {\frac {17}{8}}\right\rfloor =2}
dvojky z násobků čísla 8 a
⌊
17
16
⌋
=
1
{\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:
v
2
(
17
!
)
=
⌊
17
2
⌋
+
⌊
17
4
⌋
+
⌊
17
8
⌋
+
⌊
17
16
⌋
=
8
+
4
+
2
+
1
=
15
{\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:
2
15
{\displaystyle 2^{15}}
dělí
17
!
{\displaystyle 17!}
,
2
16
{\displaystyle 2^{16}}
ale už nedělí
17
!
{\displaystyle 17!}
.
Odtud již plyne výše zmíněný Legendreův vzorec .
Co se týče počtu sčítanců:
p
N
≤
n
≤
p
N
+
1
⇒
N
⋅
log
p
≤
log
n
≤
(
N
+
1
)
⋅
log
p
⇒
N
≤
log
n
log
p
≤
N
+
1
⇒
N
=
⌊
log
n
log
p
⌋
{\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é
N
∈
N
{\displaystyle N\in \mathbb {N} }
.
Řešený příklad č. 1
editovat
Kolika nulami končí dekadický zápis čísla
2015
!
{\displaystyle 2015!}
?
Řešení: Zadání lze vyslovit také takto: Kolik je v čísle
2015
!
{\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
v
5
(
2015
!
)
{\displaystyle v_{5}(2015!)}
.
v
5
(
2015
!
)
=
∑
j
=
1
N
⌊
2015
5
j
⌋
{\displaystyle v_{5}(2015!)=\sum _{j=1}^{N}\left\lfloor {\frac {2015}{5^{j}}}\right\rfloor }
, kde
N
=
⌊
log
2015
log
5
⌋
=
4
{\displaystyle N=\left\lfloor {\frac {\log 2015}{\log 5}}\right\rfloor =4}
v
5
(
2015
!
)
=
⌊
2015
5
⌋
+
⌊
2015
25
⌋
+
⌊
2015
125
⌋
+
⌊
2015
625
⌋
=
403
+
80
+
16
+
3
=
502
{\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}
2015
!
≐
1
,
153695
⋅
10
5785
{\displaystyle 2015!\doteq 1,153695\cdot 10^{5785}}
Závěr: Číslo
2015
!
{\displaystyle 2015!}
má 5786 cifer, z nichž 502 posledních jsou nuly.
Odhad pro Legendreův vzorec
editovat
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
!
)
≤
n
−
1
p
−
1
{\displaystyle v_{p}(n!)\leq {\frac {n-1}{p-1}}}
přičemž rovnost nastane právě tehdy, když
n
=
p
N
{\displaystyle n=p^{N}}
.
Odhad pro
v
5
(
2015
!
)
{\displaystyle v_{5}(2015!)}
z výše zmíněného řešeného příkladu:
v
5
(
2015
!
)
≤
2014
4
=
503
,
5
{\displaystyle v_{5}(2015!)\leq {\frac {2014}{4}}=503,5}
Což je velmi dobrý odhad čísla 502.
v
p
(
n
!
)
=
∑
k
=
1
N
⌊
n
p
k
⌋
≤
∑
k
=
1
N
n
p
k
=
n
p
(
1
+
1
p
+
1
p
2
+
.
.
.
+
1
p
N
−
1
)
{\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
1
p
≠
1
{\displaystyle {\frac {1}{p}}\neq 1}
.
Z toho získáme:
n
p
⋅
1
−
1
p
N
1
−
1
p
=
n
−
n
p
N
p
−
1
≤
n
−
1
p
−
1
{\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
p
N
≤
n
{\displaystyle p^{N}\leq n}
Pro
n
=
p
N
{\displaystyle n=p^{N}}
jsou všude výše místo nerovností rovnosti. Naopak například pro
p
N
<
N
{\displaystyle p^{N}<N}
je poslední nerovnost ostrá.
Lepší Legendreův vzorec
editovat
Buď
n
∈
N
{\displaystyle n\in \mathbb {N} }
,
p
≥
2
{\displaystyle p\geq 2}
prvočíslo, které dělí
n
!
{\displaystyle n!}
. Buď
v
p
(
n
!
)
=
∑
k
=
1
N
⌊
n
p
k
⌋
{\displaystyle v_{p}(n!)=\sum _{k=1}^{N}\left\lfloor {\frac {n}{p^{k}}}\right\rfloor }
, kde
p
N
≤
n
≤
p
N
+
1
{\displaystyle p^{N}\leq n\leq p^{N+1}}
, tj.
N
=
⌊
log
n
log
p
⌋
=
⌊
log
p
n
⌋
{\displaystyle N=\left\lfloor {\frac {\log n}{\log p}}\right\rfloor =\left\lfloor \log _{p}n\right\rfloor }
.
Potom
v
p
(
n
!
)
=
n
−
s
p
(
n
)
p
−
1
{\displaystyle v_{p}(n!)={\frac {n-s_{p}(n)}{p-1}}}
kde
s
p
(
n
)
{\displaystyle s_{p}(n)}
je ciferný součet čísla
n
{\displaystyle n}
zapsaného v soustavě o základu
p
{\displaystyle p}
.
7
=
1
⋅
2
2
+
1
⋅
2
1
+
1
⋅
2
0
=
(
111
)
2
{\displaystyle 7=1\cdot 2^{2}+1\cdot 2^{1}+1\cdot 2^{0}=(111)_{2}}
s
2
(
7
)
=
1
+
1
+
1
=
3
{\displaystyle s_{2}(7)=1+1+1=3}
Odtud
v
2
(
7
!
)
=
7
−
3
2
−
1
=
4
{\displaystyle v_{2}(7!)={\frac {7-3}{2-1}}=4}
Přirozené číslo
n
{\displaystyle n}
lze v libovolné soustavě o základu
p
{\displaystyle p}
zapsat jako:
n
=
a
k
p
k
+
a
k
−
1
p
k
−
1
+
.
.
.
+
a
1
p
+
a
0
{\displaystyle n=a_{k}p^{k}+a_{k-1}p^{k-1}+...+a_{1}p+a_{0}}
kde
a
i
∈
{
0
,
1
,
.
.
.
,
p
−
1
}
{\displaystyle a_{i}\in \left\{0,1,...,p-1\right\}}
, tj.
p
k
≤
n
≤
p
k
+
1
{\displaystyle p^{k}\leq n\leq p^{k+1}}
.
Platí tedy
s
p
(
n
)
=
a
k
+
a
k
−
1
+
.
.
.
+
a
1
+
a
0
{\displaystyle s_{p}(n)=a_{k}+a_{k-1}+...+a_{1}+a_{0}}
v
p
(
n
!
)
=
∑
j
=
1
k
⌊
n
p
j
⌋
{\displaystyle v_{p}(n!)=\sum _{j=1}^{k}\left\lfloor {\frac {n}{p^{j}}}\right\rfloor }
Sčítance této sumy vypadají následovně:
⌊
n
p
⌋
=
a
k
p
k
−
1
+
a
k
−
1
p
k
−
2
+
.
.
.
+
a
2
p
+
a
1
{\displaystyle \left\lfloor {\frac {n}{p}}\right\rfloor =a_{k}p^{k-1}+a_{k-1}p^{k-2}+...+a_{2}p+a_{1}}
⌊
n
p
2
⌋
=
a
k
p
k
−
2
+
a
k
−
1
p
k
−
3
+
.
.
.
+
a
2
{\displaystyle \left\lfloor {\frac {n}{p^{2}}}\right\rfloor =a_{k}p^{k-2}+a_{k-1}p^{k-3}+...+a_{2}}
...
⌊
n
p
k
−
1
⌋
=
a
k
p
+
a
k
−
1
{\displaystyle \left\lfloor {\frac {n}{p^{k-1}}}\right\rfloor =a_{k}p+a_{k-1}}
⌊
n
p
k
⌋
=
a
k
{\displaystyle \left\lfloor {\frac {n}{p^{k}}}\right\rfloor =a_{k}}
Takže platí:
v
p
(
n
!
)
=
∑
j
=
1
k
⌊
n
p
j
⌋
=
⌊
n
p
⌋
+
⌊
n
p
2
⌋
+
.
.
.
⌊
n
p
k
⌋
=
a
k
(
1
+
p
+
p
2
+
.
.
.
+
p
k
−
1
)
+
a
k
−
1
(
1
+
p
+
.
.
.
+
p
k
−
2
)
+
a
2
(
1
+
p
)
+
a
1
{\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}}
=
a
k
p
k
−
1
p
−
1
+
a
k
−
1
p
k
−
1
p
−
1
+
.
.
.
+
a
2
p
2
−
1
p
−
1
+
a
1
p
−
1
p
−
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}}}
=
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
)
]
{\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
n
{\displaystyle n}
a druhý člen je roven číslu
s
p
(
n
)
{\displaystyle s_{p}(n)}
, jak jsou tato čísla rozepsána výše. Proto platí
v
p
(
n
!
)
=
n
−
s
p
(
n
)
p
−
1
{\displaystyle v_{p}(n!)={\frac {n-s_{p}(n)}{p-1}}}
Řešený příklad č. 2
editovat
Pravidla pro počítání se vzorcem
editovat
Dá se snadno ověřit, že platí následující vztahy:
v
p
(
a
⋅
b
)
=
v
p
(
a
)
+
v
p
(
b
)
{\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í
p
k
⋅
p
m
=
p
k
+
m
{\displaystyle p^{k}\cdot p^{m}=p^{k+m}}
)
v
p
(
a
b
)
=
v
p
(
a
)
−
v
p
(
b
)
{\displaystyle v_{p}\left({\frac {a}{b}}\right)=v_{p}(a)-v_{p}(b)}
(podobný důkaz)
Řešený příklad č. 3
editovat
Dokažte, že pro libovolná čísla
m
{\displaystyle m}
,
n
{\displaystyle n}
a prvočíslo
p
{\displaystyle p}
platí:
v
p
(
(
n
+
m
m
)
)
=
s
p
(
n
)
+
s
p
(
m
)
−
s
p
(
m
+
n
)
p
−
1
{\displaystyle 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
(
(
n
+
m
m
)
)
=
v
p
(
(
n
+
m
)
!
n
!
m
!
)
=
v
p
(
(
n
+
m
)
!
)
−
v
p
(
n
!
)
−
v
p
(
m
!
)
=
n
+
m
−
s
p
(
m
+
n
)
p
−
1
−
n
−
s
p
(
n
)
p
−
1
−
m
−
s
p
(
m
)
p
−
1
=
s
p
(
n
)
+
s
p
(
m
)
−
s
p
(
m
+
n
)
p
−
1
{\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
editovat
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]
n
!
=
∏
p
p
v
p
(
n
)
{\displaystyle n!=\textstyle \prod _{p}\displaystyle p^{v_{p}(n)}}
Podle definice Legendreova vzorce také platí:
v
p
(
n
)
=
∑
k
=
1
⌊
n
p
k
⌋
<
∑
k
=
1
n
p
k
=
n
p
−
1
≤
n
{\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:
n
!
<
(
∏
p
p
)
n
{\displaystyle n!<\left(\textstyle \prod _{p}\displaystyle p\right)^{n}}
Z toho by ovšem vyplynul nepravdivý výrok, že:
lim
n
→
∞
(
∏
p
p
)
n
n
!
=
0
{\displaystyle \textstyle \lim _{n\to \infty }\displaystyle {\frac {\left(\textstyle \prod _{p}\displaystyle p\right)^{n}}{n!}}=0}
↑ OPRŠAL, Jakub. Celá čísla p-naruby. Matematický korespondenční seminář [online]. [cit. 2016-08-09]. Dostupné online .
↑ Legendre's Theorem - The Prime Factorization of Factorials. www.cut-the-knot.org [online]. [cit. 2016-08-09]. Dostupné online .
↑ WHANG, J. P. Another Proof of the Infinitude of the Prime Numbers. The American Mathematical Monthly . Roč. 2010, čís. 117, s. 181.