Разделы 
Дополнительно
Задача по математике - 2920
2019-05-06 
Доказать, что если $p$ - простое число, то разность
$C_n^p - \left [ \frac{n}{p} \right ]$
делится на $p$ ($C_n^p$ - число сочетаний из $n$ элементов по $p$; $n$ - произвольное целое положительное число, не меньшее $p$).
Так, например, $C_{11}^5 = \frac {11 \cdot 10 \cdot 9 \cdot 8 \cdot 7}{1 \cdot 2 \cdot 3 \cdot 4 \cdot 5} = 462; C_{11}^5 - \left [ \frac{11}{5} \right ] = 462 - 2$ делится на 5.
Решение:
$C_n^p = \frac {n(n-1)(n-2) \cdots (n-p+1)}{p!}$. Из $p$ последовательных целых чисел $n, n-1, n-2, \cdots, n-p+1$ одно и только одно число делится на $p$; обозначим это число буквой $N$. В таком случае $\left [ \frac{n}{p} \right ] = \frac{N}{p}$ разность, стоящая в условии задачи, принимает вид
$\frac {n(n-1) \cdots(N+1)N(N-1) \cdots (n-p+1)}{p!} - \frac{N}{p}$.
Заметим теперь, что числа $n, n-1, \cdots, N+1, N-1, \cdots, n - p + 1$ дают при делении на $p$ всевозможные остатки $1,2,3, \cdots, p-1$ ($p$ последовательных целых чисел от $n - p + 1$ до $n$ дают при делении на $p$ все остатки $0,1,2, \cdots, p-1$, причем каждый из них по одному разу). Отсюда следует, что разность
$n ( n -1) \cdots (N + 1)(N-1) \cdots (n-p+1) - (p-1)!$
делится на $p$ (для доказательства достаточно перемножить почленно все равенства $n = k_1p + a_1, n - 1 = k_2p + a_2, \cdots, N + 1 = k_ip + a_i, N -1 = k_{i+1}p + a_{i+1}, \cdots, n - p + 1 = k_{p-1}p + a_{p-1}$, где $k_1, k_2, \cdots, k_{p-1}$ - целые числа, а $a_1, a_2, \cdots, a_{p-1}$ равны числам $1, 2, \cdots, p-1$, взятым в каком-то неизвестном нам порядке). Умножая эту разность на целое число $\frac{N}{p}$, получим:
$\frac {n(n-1) \cdots (n-p+1)}{p} - \frac {N (p-1)!}{p}$;
новая разность, разумеется, будет по-прежнему делиться на $p$. Разделив, наконец, оба члена последней разности на $(p-1)!$, мы придем к требуемому результату (частное от деления на $(p-1)!$) также будет делиться на $p$, ибо $(p-1)!$) взаимно просто с $p$).
Доказать, что если $p$ - простое число, то разность
$C_n^p - \left [ \frac{n}{p} \right ]$
делится на $p$ ($C_n^p$ - число сочетаний из $n$ элементов по $p$; $n$ - произвольное целое положительное число, не меньшее $p$).
Так, например, $C_{11}^5 = \frac {11 \cdot 10 \cdot 9 \cdot 8 \cdot 7}{1 \cdot 2 \cdot 3 \cdot 4 \cdot 5} = 462; C_{11}^5 - \left [ \frac{11}{5} \right ] = 462 - 2$ делится на 5.
Решение:
$C_n^p = \frac {n(n-1)(n-2) \cdots (n-p+1)}{p!}$. Из $p$ последовательных целых чисел $n, n-1, n-2, \cdots, n-p+1$ одно и только одно число делится на $p$; обозначим это число буквой $N$. В таком случае $\left [ \frac{n}{p} \right ] = \frac{N}{p}$ разность, стоящая в условии задачи, принимает вид
$\frac {n(n-1) \cdots(N+1)N(N-1) \cdots (n-p+1)}{p!} - \frac{N}{p}$.
Заметим теперь, что числа $n, n-1, \cdots, N+1, N-1, \cdots, n - p + 1$ дают при делении на $p$ всевозможные остатки $1,2,3, \cdots, p-1$ ($p$ последовательных целых чисел от $n - p + 1$ до $n$ дают при делении на $p$ все остатки $0,1,2, \cdots, p-1$, причем каждый из них по одному разу). Отсюда следует, что разность
$n ( n -1) \cdots (N + 1)(N-1) \cdots (n-p+1) - (p-1)!$
делится на $p$ (для доказательства достаточно перемножить почленно все равенства $n = k_1p + a_1, n - 1 = k_2p + a_2, \cdots, N + 1 = k_ip + a_i, N -1 = k_{i+1}p + a_{i+1}, \cdots, n - p + 1 = k_{p-1}p + a_{p-1}$, где $k_1, k_2, \cdots, k_{p-1}$ - целые числа, а $a_1, a_2, \cdots, a_{p-1}$ равны числам $1, 2, \cdots, p-1$, взятым в каком-то неизвестном нам порядке). Умножая эту разность на целое число $\frac{N}{p}$, получим:
$\frac {n(n-1) \cdots (n-p+1)}{p} - \frac {N (p-1)!}{p}$;
новая разность, разумеется, будет по-прежнему делиться на $p$. Разделив, наконец, оба члена последней разности на $(p-1)!$, мы придем к требуемому результату (частное от деления на $(p-1)!$) также будет делиться на $p$, ибо $(p-1)!$) взаимно просто с $p$).
