Teorema lui Lucas

În teoria numerelor , teorema lui Lucas dă restul care se obține prin împărțirea coeficientului binomial ${\tbinom {m}{n}}$ ${\ displaystyle {\ tbinom {m} {n}}}$ ${\ displaystyle {\ tbinom {m} {n}}}$ pentru un număr prim ${\textstyle p}$ ${\ textstyle p}$ ${\ textstyle p}$ în ceea ce privește extinderea bazei $p$ ${\ displaystyle p}$ $p$ de numere întregi $m$ ${\ displaystyle m}$ $m$ Și $n$ ${\ displaystyle n}$ $n$ .

Teorema lui Lucas a apărut pentru prima dată în 1878 în articolele lui Édouard Lucas . ^[1]

Formulare

Pentru numere întregi care nu sunt negative $m$ ${\ displaystyle m}$ $m$ Și $n$ ${\ displaystyle n}$ $n$ și un număr prim $p$ ${\ displaystyle p}$ $p$ , are loc următoarea relație de congruență :

${\displaystyle {\binom {m}{n}}\equiv \prod _{i=0}^{k}{\binom {m_{i}}{n_{i}}}{\pmod {p}},}$ ${\ displaystyle {\ displaystyle {\ binom {m} {n}} \ equiv \ prod _ {i = 0} ^ {k} {\ binom {m_ {i}} {n_ {i}}} {\ pmod { p}},}}$ ${\ displaystyle {\ displaystyle {\ binom {m} {n}} \ equiv \ prod _ {i = 0} ^ {k} {\ binom {m_ {i}} {n_ {i}}} {\ pmod { p}},}}$

unde este

$m=m_{k}p^{k}+m_{k-1}p^{k-1}+\cdots +m_{1}p+m_{0},$ ${\ displaystyle m = m_ {k} p ^ {k} + m_ {k-1} p ^ {k-1} + \ cdots + m_ {1} p + m_ {0},}$ ${\ displaystyle m = m_ {k} p ^ {k} + m_ {k-1} p ^ {k-1} + \ cdots + m_ {1} p + m_ {0},}$

Și

$n=n_{k}p^{k}+n_{k-1}p^{k-1}+\cdots +n_{1}p+n_{0}$ ${\ displaystyle n = n_ {k} p ^ {k} + n_ {k-1} p ^ {k-1} + \ cdots + n_ {1} p + n_ {0}}$ ${\ displaystyle n = n_ {k} p ^ {k} + n_ {k-1} p ^ {k-1} + \ cdots + n_ {1} p + n_ {0}}$

sunt respectiv expansiunile în bază $p$ ${\ displaystyle p}$ $p$ din $m$ ${\ displaystyle m}$ $m$ și de $n$ ${\ displaystyle n}$ $n$ . Aceasta folosește convenția care ${\displaystyle {\tbinom {m}{n}}=0}$ ${\ displaystyle {\ displaystyle {\ tbinom {m} {n}} = 0}}$ ${\ displaystyle {\ displaystyle {\ tbinom {m} {n}} = 0}}$ de sine $n>m$ ${\ displaystyle n> m}$ $n> m$ .

Consecinţă

Un coeficient binomial ${\tbinom {m}{n}}$ ${\ displaystyle {\ tbinom {m} {n}}}$ ${\ displaystyle {\ tbinom {m} {n}}}$ este divizibil cu un număr prim $p$ ${\ displaystyle p}$ $p$ dacă și numai dacă cel puțin una din cifrele din bază $p$ ${\ displaystyle p}$ $p$ din $n$ ${\ displaystyle n}$ $n$ este mai mare decât cifra corespunzătoare a $m$ ${\ displaystyle m}$ $m$ .

Demonstrații

Există mai multe moduri de a demonstra teorema lui Lucas. Mai întâi vom face un raționament combinatoriu și apoi o dovadă bazată pe funcții de generare .

Raționamentul combinatoriu

Indicați cu $M.$ ${\ displaystyle M}$ $M.$ un set de $m$ ${\ displaystyle m}$ $m$ elemente și împărțiți-l în $m_{i}$ ${\ displaystyle m_ {i}}$ $pe mine$ bucle în lungime $p^{i}$ ${\ displaystyle p ^ {i}}$ ${\ displaystyle p ^ {i}}$ pentru diferitele valori ale $the$ ${\ displaystyle i}$ $the$ . Apoi, fiecare dintre aceste cicluri poate fi rotit separat, astfel încât un singur grup $G.$ ${\ displaystyle G}$ $G.$ , care este produsul cartezian al grupărilor ciclice $C_{p^{i}}$ ${\ displaystyle C_ {p ^ {i}}}$ ${\ displaystyle C_ {p ^ {i}}}$ , acționează pe $M.$ ${\ displaystyle M}$ $M.$ . Apoi, aceasta acționează și asupra subseturilor $Nu.$ ${\ displaystyle N}$ $Nu.$ de măreție $n$ ${\ displaystyle n}$ $n$ . Deoarece numărul de elemente din $G.$ ${\ displaystyle G}$ $G.$ este o putere a $p$ ${\ displaystyle p}$ $p$ , același lucru este valabil pentru fiecare dintre orbitele sale. Deci să calculăm ${\tbinom {m}{n}}$ ${\ displaystyle {\ tbinom {m} {n}}}$ ${\ displaystyle {\ tbinom {m} {n}}}$ modul $p$ ${\ displaystyle p}$ $p$ , trebuie doar să luăm în considerare anumite puncte. Aceste puncte sunt subseturile $Nu.$ ${\ displaystyle N}$ $Nu.$ care sunt unirea unor cicluri. Mai precis poate fi dovedit prin inducție pe $k-i$ ${\ displaystyle ki}$ ${\ displaystyle k-i}$ , acea $Nu.$ ${\ displaystyle N}$ $Nu.$ trebuie să aibă exact $n_{i}$ ${\ displaystyle n_ {i}}$ $n_i$ cicluri de măreție $p^{i}$ ${\ displaystyle p ^ {i}}$ ${\ displaystyle p ^ {i}}$ . De aici și numărul de opțiuni pentru $Nu.$ ${\ displaystyle N}$ $Nu.$ este exact

$\prod _{i=0}^{k}{\binom {m_{i}}{n_{i}}}{\pmod {p}}.$ ${\ displaystyle \ prod _ {i = 0} ^ {k} {\ binom {m_ {i}} {n_ {i}}} {\ pmod {p}}.}$ ${\ displaystyle \ prod _ {i = 0} ^ {k} {\ binom {m_ {i}} {n_ {i}}} {\ pmod {p}}.}$

Dovadă bazată pe generarea de funcții

Această demonstrație este creditată lui Nathan Fine. ^[2]

De sine $p$ ${\ displaystyle p}$ $p$ este un număr prim și $n$ ${\ displaystyle n}$ $n$ este un număr întreg cu ${\textstyle 1\leq n\leq p-1}$ ${\ textstyle 1 \ leq n \ leq p-1}$ ${\ textstyle 1 \ leq n \ leq p-1}$ , apoi numeratorul coeficientului binomial

${\binom {p}{n}}={\frac {p\cdot (p-1)\cdots (p-n+1)}{n\cdot (n-1)\cdots 1}}$ ${\ displaystyle {\ binom {p} {n}} = {\ frac {p \ cdot (p-1) \ cdots (p-n + 1)} {n \ cdot (n-1) \ cdots 1}}}$ ${\ displaystyle {\ binom {p} {n}} = {\ frac {p \ cdot (p-1) \ cdots (p-n + 1)} {n \ cdot (n-1) \ cdots 1}}}$

este divizibil cu $p$ ${\ displaystyle p}$ $p$ în timp ce numitorul nu este. Prin urmare $p$ ${\ displaystyle p}$ $p$ împarte ${\displaystyle {\tbinom {p}{n}}}$ ${\ displaystyle {\ displaystyle {\ tbinom {p} {n}}}}$ ${\ displaystyle {\ displaystyle {\ tbinom {p} {n}}}}$ . În ceea ce privește funcțiile obișnuite de generare, aceasta înseamnă că

$(1+X)^{p}\equiv 1+X^{p}{\pmod {p}}.$ ${\ displaystyle (1 + X) ^ {p} \ equiv 1 + X ^ {p} {\ pmod {p}}.}$ ${\ displaystyle (1 + X) ^ {p} \ equiv 1 + X ^ {p} {\ pmod {p}}.}$

Continuând prin inducție, avem pentru fiecare număr întreg negativ $the$ ${\ displaystyle i}$ $the$ acea

$(1+X)^{p^{i}}\equiv 1+X^{p^{i}}{\pmod {p}}.$ ${\ displaystyle (1 + X) ^ {p ^ {i}} \ equiv 1 + X ^ {p ^ {i}} {\ pmod {p}}.}$ ${\ displaystyle (1 + X) ^ {p ^ {i}} \ equiv 1 + X ^ {p ^ {i}} {\ pmod {p}}.}$

Acum indicăm cu $m$ ${\ displaystyle m}$ $m$ un număr întreg negativ și cu $p$ ${\ displaystyle p}$ $p$ un număr prim. Noi scriem $m$ ${\ displaystyle m}$ $m$ in conformitate $p$ ${\ displaystyle p}$ $p$ astfel încât $m=\sum _{i=0}^{k}m_{i}p^{i}$ ${\ displaystyle m = \ sum _ {i = 0} ^ {k} m_ {i} p ^ {i}}$ ${\ displaystyle m = \ sum _ {i = 0} ^ {k} m_ {i} p ^ {i}}$ pentru un număr întreg non-negativ $k$ ${\ displaystyle k}$ $k$ iar pentru numere întregi $m_{i}$ ${\ displaystyle m_ {i}}$ $pe mine$ cu ${\textstyle 0\leq m_{i}\leq p-1}$ ${\ textstyle 0 \ leq m_ {i} \ leq p-1}$ ${\ textstyle 0 \ leq m_ {i} \ leq p-1}$ .

Atunci

${\begin{aligned}\sum _{n=0}^{m}{\binom {m}{n}}X^{n}&=(1+X)^{m}=\prod _{i=0}^{k}\left((1+X)^{p^{i}}\right)^{m_{i}}\\&\equiv \prod _{i=0}^{k}\left(1+X^{p^{i}}\right)^{m_{i}}=\prod _{i=0}^{k}\left(\sum _{n_{i}=0}^{m_{i}}{\binom {m_{i}}{n_{i}}}X^{n_{i}p^{i}}\right)\\&=\prod _{i=0}^{k}\left(\sum _{n_{i}=0}^{p-1}{\binom {m_{i}}{n_{i}}}X^{n_{i}p^{i}}\right)=\sum _{n=0}^{m}\left(\prod _{i=0}^{k}{\binom {m_{i}}{n_{i}}}\right)X^{n}{\pmod {p}},\end{aligned}}$ ${\ displaystyle {\ begin {align} \ sum _ {n = 0} ^ {m} {\ binom {m} {n}} X ^ {n} & = (1 + X) ^ {m} = \ prod _ {i = 0} ^ {k} \ left ((1 + X) ^ {p ^ {i}} \ right) ^ {m_ {i}} \\ & \ equiv \ prod _ {i = 0} ^ {k} \ left (1 + X ^ {p ^ {i}} \ right) ^ {m_ {i}} = \ prod _ {i = 0} ^ {k} \ left (\ sum _ {n_ {i } = 0} ^ {m_ {i}} {\ binom {m_ {i}} {n_ {i}}} X ^ {n_ {i} p ^ {i}} \ right) \\ & = \ prod _ {i = 0} ^ {k} \ left (\ sum _ {n_ {i} = 0} ^ {p-1} {\ binom {m_ {i}} {n_ {i}}} X ^ {n_ { i} p ^ {i}} \ right) = \ sum _ {n = 0} ^ {m} \ left (\ prod _ {i = 0} ^ {k} {\ binom {m_ {i}} {n_ {i}}} \ right) X ^ {n} {\ pmod {p}}, \ end {align}}}$ ${\ displaystyle {\ begin {align} \ sum _ {n = 0} ^ {m} {\ binom {m} {n}} X ^ {n} & = (1 + X) ^ {m} = \ prod _ {i = 0} ^ {k} \ left ((1 + X) ^ {p ^ {i}} \ right) ^ {m_ {i}} \\ & \ equiv \ prod _ {i = 0} ^ {k} \ left (1 + X ^ {p ^ {i}} \ right) ^ {m_ {i}} = \ prod _ {i = 0} ^ {k} \ left (\ sum _ {n_ {i } = 0} ^ {m_ {i}} {\ binom {m_ {i}} {n_ {i}}} X ^ {n_ {i} p ^ {i}} \ right) \\ & = \ prod _ {i = 0} ^ {k} \ left (\ sum _ {n_ {i} = 0} ^ {p-1} {\ binom {m_ {i}} {n_ {i}}} X ^ {n_ { i} p ^ {i}} \ right) = \ sum _ {n = 0} ^ {m} \ left (\ prod _ {i = 0} ^ {k} {\ binom {m_ {i}} {n_ {i}}} \ right) X ^ {n} {\ pmod {p}}, \ end {align}}}$

unde în produsul final, $n_{i}$ ${\ displaystyle n_ {i}}$ $n_i$ si $the$ ${\ displaystyle i}$ $the$ -alea cifră a reprezentării în bază $p$ ${\ displaystyle p}$ $p$ din $n$ ${\ displaystyle n}$ $n$ . Aceasta dovedește teorema lui Lucas.

Variații și generalizări

Teorema lui Kummer
Andrew Granville a generalizat teorema lui Lucas pentru caz $p$ ${\ displaystyle p}$ $p$ este puterea unui număr prim. ^[3]

Notă

^ * Edouard Lucas, Théorie des Fonctions Numériques Simplement Périodiques , în American Journal of Mathematics , vol. 1, nr. 2, 1878, pp. 184–196, DOI : 10.2307 / 2369308 , JSTOR 2369308 , MR 1505161 . (partea 1);
- Edouard Lucas, Théorie des Fonctions Numériques Simplement Périodiques , în American Journal of Mathematics , vol. 1, nr. 3, 1878, pp. 197-240, DOI : 10.2307 / 2369311 , JSTOR 2369311 , MR 1505164 . (partea 2);
- Edouard Lucas, Théorie des Fonctions Numériques Simplement Périodiques , în American Journal of Mathematics , vol. 1, nr. 4, 1878, pp. 289-321, DOI : 10.2307 / 2369373 , JSTOR 2369373 , MR 1505176 . (partea 3)
^ Nathan Fine, Binomial coefficients modulo a prime , în American Mathematical Monthly , vol. 54, 1947, pp. 589–592, DOI : 10.2307 / 2304500 .
^ Andrew Granville , Arithmetic Properties of Binomial Coefficients I: Binomial coefficients module prime powers ( PDF ), în Canadian Mathematical Society Conference Proceedings , vol. 20, 1997, pp. 253-275, MR 1483922 (arhivat din original la 2 februarie 2017) .

linkuri externe

( EN ) Teorema lui Lucas , în PlanetMath .
Dovadă alternativă a teoremei lui Lucas

[1] * Edouard Lucas, Théorie des Fonctions Numériques Simplement Périodiques , în American Journal of Mathematics , vol. 1, nr. 2, 1878, pp. 184–196, DOI : 10.2307 / 2369308 , JSTOR 2369308 , MR 1505161 . (partea 1);
Edouard Lucas, Théorie des Fonctions Numériques Simplement Périodiques , în American Journal of Mathematics , vol. 1, nr. 3, 1878, pp. 197-240, DOI : 10.2307 / 2369311 , JSTOR 2369311 , MR 1505164 . (partea 2);
Edouard Lucas, Théorie des Fonctions Numériques Simplement Périodiques , în American Journal of Mathematics , vol. 1, nr. 4, 1878, pp. 289-321, DOI : 10.2307 / 2369373 , JSTOR 2369373 , MR 1505176 . (partea 3)

[2] Edouard Lucas, Théorie des Fonctions Numériques Simplement Périodiques , în American Journal of Mathematics , vol. 1, nr. 3, 1878, pp. 197-240, DOI : 10.2307 / 2369311 , JSTOR 2369311 , MR 1505164 . (partea 2);

[3] Edouard Lucas, Théorie des Fonctions Numériques Simplement Périodiques , în American Journal of Mathematics , vol. 1, nr. 4, 1878, pp. 289-321, DOI : 10.2307 / 2369373 , JSTOR 2369373 , MR 1505176 . (partea 3)

[2] Nathan Fine, Binomial coefficients modulo a prime , în American Mathematical Monthly , vol. 54, 1947, pp. 589–592, DOI : 10.2307 / 2304500 .

[3] Andrew Granville , Arithmetic Properties of Binomial Coefficients I: Binomial coefficients module prime powers ( PDF ), în Canadian Mathematical Society Conference Proceedings , vol. 20, 1997, pp. 253-275, MR 1483922 (arhivat din original la 2 februarie 2017) .

[1]

[2]

[3]