Lukas teorem

I matematik är Lucas sats följande påstående om resten av att dividera en binomial koefficient med ett primtal p : ${\tbinom {m}{n))$

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

där och är representationer av talen m och n i det p -ära talsystemet . $m=(m_{{k-1}},\dots ,m_{0})_{p}$ $n=(n_{{k-1}},\dots ,n_{0})_{p}$

I synnerhet är binomialkoefficienten jämnt delbar med ett primtal p om och endast om minst en p -är siffra av talet n överstiger motsvarande siffra i talet m . ${\tbinom {m}{n))$

Teoremet härleddes först av den franske matematikern Edouard Lucas 1878.

Bevis

Betrakta koefficienten för i ett polynom över ett ändligt fält . Å ena sidan är det helt enkelt lika med . Å andra sidan, sedan $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}},

sedan, för att erhålla koefficienten at från den sista produkten , är det nödvändigt att ta koefficienten för at från nollfaktorn , koefficienten för at från den första , och i det allmänna fallet från den -th faktorn, koefficienten på . Att likställa koefficienterna får vi $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}}.

Litteratur

E. Lucas. Théorie des Fonctions Numériques Simplement Périodiques (franska) // American Journal of Mathematics : tidskrift. - 1878. - Vol. 1 , nr 2 . _ - S. 184-196 . - doi : 10.2307/2369308 . (del 1);
E. Lucas. Théorie des Fonctions Numériques Simplement Périodiques (franska) // American Journal of Mathematics : tidskrift. - 1878. - Vol. 1 , nr 3 . _ - S. 197-240 . - doi : 10.2307/2369311 . (del 2);
E. Lucas. Théorie des Fonctions Numériques Simplement Périodiques (franska) // American Journal of Mathematics : tidskrift. - 1878. - Vol. 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 (engelska) // Canadian Mathematical Society Conference Proceedings : journal. - 1997. - Vol. 20 . - S. 253-275 . Arkiverad från originalet den 2 februari 2017.