Lukova věta

V matematice je Lucasova věta následující tvrzení o zbytku dělení binomického koeficientu prvočíslem p : ${\tbinom {m}{n))$

{\binom {m}{n}}\equiv \prod _{{i=0}}^{{k-1}}({\binom {m_{i}}{n_{i}}}}{\ pmodp},

kde a jsou reprezentace čísel m a n v p -ární číselné soustavě . $m=(m_{{k-1}},\tečky ,m_{0})_{p}$ $n=(n_{{k-1}},\tečky ,n_{0})_{p}$

Konkrétně, binomický koeficient je rovnoměrně dělitelný prvočíslem p právě tehdy, když alespoň jedna p -ární cifra čísla n přesahuje odpovídající cifru čísla m . ${\tbinom {m}{n))$

Tuto větu poprvé odvodil francouzský matematik Edouard Lucas v roce 1878.

Důkaz

Uvažujme koeficient pro v polynomu nad konečným tělesem . Na jednu stranu se prostě rovná . Na druhou stranu od $x^n$ $(x+1)^{m}$ $GF(p)$ ${\tbinom {m}{n))$

(x+1)^{m}=\prod _{{i=0}}^{{k-1}}(x+1)^{{m_{i}p^{i}}}\ekviv \ prod _{{i=0}}^{{k-1}}(x^{{p^{i}}}+1)^{{m_{i}}}{\pmod {p}},

pak, abychom získali koeficient at z posledního součinu , je nutné vzít koeficient at z nulového faktoru , koeficient at z prvního a v obecném případě z -tého faktoru, koeficient at . Porovnáním koeficientů dostaneme $x^n$ $x^{{n_{0}}}$ $x^{{n_{1}p}}$ $i$ $x^{{n_{i}p^{i}}}$

{\binom {m}{n}}\equiv \prod _{{i=0}}^{{k-1}}({\binom {m_{i}}{n_{i}}}}{\ pmod{p}}.

Literatura

E. Lucas. Théorie des Fonctions Numériques Simplement Périodiques (francouzsky) // American Journal of Mathematics : magazín. - 1878. - Sv. 1 , č . 2 . - S. 184-196 . - doi : 10.2307/2369308 . (část 1);
E. Lucas. Théorie des Fonctions Numériques Simplement Périodiques (francouzsky) // American Journal of Mathematics : magazín. - 1878. - Sv. 1 , č . 3 . - str. 197-240 . - doi : 10.2307/2369311 . (část 2);
E. Lucas. Théorie des Fonctions Numériques Simplement Périodiques (francouzsky) // American Journal of Mathematics : magazín. - 1878. - Sv. 1 , č . 4 . - str. 289-321 . - doi : 10.2307/2369373 . (část 3)
A. Granville. Aritmetické vlastnosti binomických koeficientů I: Binomické koeficienty modulo prime power (anglicky) // Canadian Mathematical Society Conference Proceedings: journal. - 1997. - Sv. 20 . - str. 253-275 . Archivováno z originálu 2. února 2017.