Lukas sætning

I matematik er Lucas-sætningen følgende udsagn om resten af at dividere en binomial koefficient med et primtal p : ${\tbinom {m}{n))$

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

hvor og er repræsentationer af tallene m og n i det p -ære talsystem . $m=(m_{{k-1}},\dots ,m_{0})_{p}$ $n=(n_{{k-1}},\dots,n_{0})_{p}$

Især er binomialkoefficienten ligeligt delelig med et primtal p , hvis og kun hvis mindst et p -ært ciffer af tallet n overstiger det tilsvarende ciffer i tallet m . ${\tbinom {m}{n))$

Sætningen blev først udledt af den franske matematiker Edouard Lucas i 1878.

Bevis

Overvej koefficienten for i et polynomium over et begrænset felt . På den ene side er det simpelthen lig med . På den anden side siden $x^n$ $(x+1)^{m}$ $GF(p)$ ${\tbinom {m}{n))$

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

derefter, for at opnå koefficienten for at fra det sidste produkt , er det nødvendigt at tage koefficienten for at fra nulfaktoren , koefficienten for at fra den første , og i det generelle tilfælde fra den -th faktor, koefficienten på kl . Ved at sidestille koefficienterne får vi $x^n$ $x^{{n_{0}}}$ $x^{{n_{1}p}}$ $jeg$ $x^{{n_{i}p^{i}}}$

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

Litteratur

E. Lucas. Théorie des Fonctions Numériques Simplement Périodiques (fransk) // American Journal of Mathematics : magasin. - 1878. - Bd. 1 , nr . 2 . - S. 184-196 . - doi : 10.2307/2369308 . (del 1);
E. Lucas. Théorie des Fonctions Numériques Simplement Périodiques (fransk) // American Journal of Mathematics : magasin. - 1878. - Bd. 1 , nr . 3 . - S. 197-240 . - doi : 10.2307/2369311 . (del 2);
E. Lucas. Théorie des Fonctions Numériques Simplement Périodiques (fransk) // American Journal of Mathematics : magasin. - 1878. - Bd. 1 , nr . 4 . - S. 289-321 . - doi : 10.2307/2369373 . (del 3)
A. Granville. Arithmetic Properties of Binomial Coefficients I: Binomial coefficients modulo prime powers (engelsk) // Canadian Mathematical Society Conference Proceedings : journal. - 1997. - Bd. 20 . - S. 253-275 . Arkiveret fra originalen den 2. februar 2017.