- Теорема Люка
-
В математике теоремой Люка́ называется следующее утверждение об остатке от деления биномиального коэффициента на простое число p:
где и — представления чисел m и n в p-ричной системе счисления.
В частности, биномиальный коэффициент делится на простое число p нацело тогда и только тогда, когда хотя бы одна p-ричная цифра числа n превышает соответствующую цифру числа m.
Теорема Люка была впервые получена французским математиком Люка в 1878 году.
Доказательство
Рассмотрим коэффициент при в многочлене над конечным полем . С одной стороны, он попросту равен . С другой стороны, так как
то, чтобы из последнего произведения получить коэффициент при , нужно из нулевого сомножителя взять коэффициент при , из первого — коэффициент при , a в общем случае из -го сомножителя — коэффициент при . Приравнивая коэффициенты, получаем
Литература
- E. Lucas (1878). «Théorie des Fonctions Numériques Simplement Périodiques». American Journal of Mathematics 1 (2): 184–196. DOI:10.2307/2369308. MR1505161. (part 1);
- E. Lucas (1878). «Théorie des Fonctions Numériques Simplement Périodiques». American Journal of Mathematics 1 (3): 197–240. DOI:10.2307/2369311. MR1505164. (part 2);
- E. Lucas (1878). «Théorie des Fonctions Numériques Simplement Périodiques». American Journal of Mathematics 1 (4): 289–321. DOI:10.2307/2369373. MR1505176. (part 3)
- A. Granville (1997). «Arithmetic Properties of Binomial Coefficients I: Binomial coefficients modulo prime powers». Canadian Mathematical Society Conference Proceedings 20: 253-275. MR1483922.
Категории:- Алгебра
- Доказательства
- Комбинаторика
- Теоремы
- Теория чисел
Wikimedia Foundation. 2010.