Lukács tétele

A matematikában a Lucas-tétel a következő állítás a binomiális együttható p prímszámmal való osztásának maradékáról : ${\tbinom {m}{n))$

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

ahol és az m és n számok reprezentációi a p - áris számrendszerben . $m=(m_{{k-1}},\pontok ,m_{0})_{p}$ $n=(n_{{k-1}},\pontok ,n_{0})_{p}$

Pontosabban, a binomiális együttható akkor és csak akkor osztható egyenlően egy p prímszámmal , ha az n szám legalább egy p -számjegye meghaladja az m szám megfelelő jegyét . ${\tbinom {m}{n))$

A tételt először Edouard Lucas francia matematikus vezette le 1878-ban.

Bizonyítás

Tekintsük a for együtthatót egy véges mező feletti polinomban . Egyrészt egyszerűen egyenlő a -val . Másrészt azóta $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}},

akkor ahhoz, hogy az utolsó szorzatból megkapjuk az at együtthatót, ki kell venni az at együtthatót a nulla tényezőből , az at együtthatót az elsőből , és általános esetben a -edik tényezőből, együtthatója at . Az együtthatók egyenlővé tételével azt kapjuk, hogy $x^n$ $x^{{n_{0}}}$ $x^{{n_{1}p}}$ $én$ $x^{{n_{i}p^{i}}}$

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

Irodalom

E. Lucas. Théorie des Fonctions Numériques Simplement Périodiques (francia) // American Journal of Mathematics : magazin. - 1878. - évf. 1 , n o 2 . - P. 184-196 . - doi : 10.2307/2369308 . (1. rész);
E. Lucas. Théorie des Fonctions Numériques Simplement Périodiques (francia) // American Journal of Mathematics : magazin. - 1878. - évf. 1 , n o 3 . - P. 197-240 . - doi : 10.2307/2369311 . (2. rész);
E. Lucas. Théorie des Fonctions Numériques Simplement Périodiques (francia) // American Journal of Mathematics : magazin. - 1878. - évf. 1 , n o 4 . - P. 289-321 . - doi : 10.2307/2369373 . (3. rész)
A. Granville. A binomiális együtthatók aritmetikai tulajdonságai I: Binomiális együtthatók modulo prime powers (angol) // Canadian Mathematical Society Conference Proceedings : Journal. - 1997. - 1. évf. 20 . - P. 253-275 . Archiválva az eredetiből 2017. február 2-án.