Дано: р — простое число.
Найти: доказать, что все числа, кроме первого и последнего, в р-й строке треугольника Паскаля делятся на р.
Решение:
Треугольник Паскаля можно представить в виде биномиальных коэффициентов, где значения вычисляются по формуле:
С(n, k) = n! / (k!(n-k)!)
где n — номер строки, k — позиция числа в строке.
Так как р — простое число, то по теореме о делении нацело имеем:
n! ≡ 0 (mod р) для n >= р
Также, рассмотрим произвольное число С(n, k) в р-й строке. Для чисел, не находящихся в крайних позициях (k=0 и k=n), выпишем формулу:
С(n, k) = n! / (k!(n-k)!)
Так как по модулю р числа от 1 до (р-1) взаимно просты с р, получаем что числитель n! делится на р только при k=0 и k=n, а числитель делится на р для остальных чисел в строке.
Ответ: все числа, кроме первого и последнего, в р-й строке треугольника Паскаля делятся на р.