Задачка
Решил одну интересную задачу. В процессе появилась интересная лемма с очень простым доказательством. Хочу поделиться. Комменты не скрываю, кто не хочет - пусть не подсматривает :) Своё доказательство опубликую завтра.
Доказать, что для любого простого числа Р и для любого К между 0 и Р-1, число сочетаний из Р-1 по К даёт при делении на Р остаток либо 1, либо -1.
Пример: Р=7,K=2: C(6,2)=15=1 (mod 7). P=11,K=5: C(10,5)=252=-1 (mod 11).
Доказать, что для любого простого числа Р и для любого К между 0 и Р-1, число сочетаний из Р-1 по К даёт при делении на Р остаток либо 1, либо -1.
Пример: Р=7,K=2: C(6,2)=15=1 (mod 7). P=11,K=5: C(10,5)=252=-1 (mod 11).