ГЛАВНАЯ » РЕШЕБНИК

2014-06-07   
Доказать, что для любого значения $n \in \mathbf{N}$ и простого числа $p$ следующие условия эквивалентны:
а) ни одно из чисел $C^{k}_{n}$ при $k = 0, 1, \cdots , n$ не делится на $p$.
б) $n=p^{s}m-1$, где $s \in \mathbf{Z}^{+},m \in \mathbf{N}, m < p$.


Решение:


Докажем, что условие б) эквивалентно следующему условию:
в) $n=p^{t}l + (p^{t}-1)$, где $t \in \mathbf{Z}^{+}, l \in \mathbf{N}, l < p$.
Действительно, из условия б) имеем
$n=p^{s}m-1=p^{s}(m-1)+(p^{s}-1)$.
где $s \in \mathbf{Z}^{+}, m \in \mathbf{N}, l< p$. Если $m > 1$, то положим
$t=s, l=(m-1) > 0$.
Если же $m = 1$, то $s > 0$, так как иначе $n = p^{0} \cdot l - 1 =0 \notin \mathbf{N}$. Поэтому
$n=p^{s-1} \cdot p -1 = p^{s-1} (p-1) + (p^{s-1}-1)$
и можно положить $t=s-1 \geq 0, l= p – 1 < p$. В обоих случаях условие в) выполнено. С другой стороны, из условия в) имеем
$n= p^{t}l + (p^{t}-1) = p^{t} (l+1) - 1$.
Если $l +1 < p$, то
$m = l + l, s = t$,
а если $l + 1 = p$, то
$m = 1, s = t + 1$.
Для заданного числа $n \in \mathbf{N}$ найдется такое $t \in \mathbf{Z}^{+}$, что
$p^{t} \leq n < p^{t+1}$,
откуда
$n = p^{t} l + r$, где $0 \leq r < p^{t}, l \leq l < p$.
Поскольку наибольший показатель степени простого числа $p$, на которую делится число $ql$, равен
$\left [ \frac{q}{p} \right ] + \left [ \frac{q}{p^{2}} \right ] + \left [ \frac{q}{p^{3}} \right ] + \cdots$,
то наибольшая степень числа $p$, на которую делится число
$C^{k}_{n}= \frac{n!}{k!(n-k)!}$,
имеет показатель
$d_{k}= \left (\left [ \frac{n}{p} \right ] - \left [ \frac{k}{p} \right ] - \left [ \frac{n-k}{p} \right ] \right ) + \left (\left [ \frac{r}{p^{2}} \right ] - \left [ \frac{q}{p^{2}} \right ] - \left [ \frac{n-k}{p^{2}} \right ] \right ) +$
$+ \left (\left [ \frac{r}{p^{3}} \right ] - \left [ \frac{k}{p^{3}} \right ] - \left [ \frac{n-k}{p^{3}} \right ] \right ) + \cdots$
(при $i > t$ каждое из чисел $[n/p^{i}], [k/p^{i}], [(n-k)/p^{i}]$ равно нулю). Из соотношений
$\left [ \frac{n}{p^{i}} \right ] = \left [\frac{k}{p^{i}} + \frac{n-k}{p^{i}} \right ] \geq \left [\left [\frac{k}{p^{i}} \right ] + \left [\frac{n-k}{p^{i}} \right ] \right ] = \left [\frac{k}{p^{i}} \right ] + \left [\frac{n-k}{p^{i}} \right ]$
вытекает, что $d_{k}=0$ тогда и только тогда, когда имеют место равенства
$\left [ \frac{n}{p^{i}} \right ] = \left [ \frac{k}{p^{i}} \right ] + \left [ \frac{n-k}{p^{i}} \right ], i = 0,1, \cdots t $.
Докажем, что это возможно лишь в случае $r = p^{t} – 1$, т. е. при условии в). Действительно, если $r < p^{t} – 2$, то положим $k =p^{t} – 1, i = t$. Тогда имеем
$\left [ \frac{k}{p^{t}} \right ] = \left [ \frac{p^{t}-1}{p^{t}} \right ] = 0, \left [ \frac{n-k}{p^{t}} \right ] \leq \left [ \frac{p^{t} l - 1}{p^{t}} \right ] = l-1$,
$\left [ \frac{n}{p^{t}} \right ] = \left [ \frac{p^{t} l + r}{p^{t}} \right ] = l, l > 0 + (l-1)$,
следовательно, указанное выше равенство, а с ним и условие а) не выполняются. Пусть теперь выполнено условие в) тогда для всех значений $i = 0, 1, \cdots , t$ и $k = 0, 1, \cdots , n$ имеем
$n = p^{i} \left [ \frac{n}{p^{i}} \right ] + (p^{i}-1)$,
$k = p^{i} \left [ \frac{k}{p^{i}} \right ] + q, 0 \leq q < p^{i}$,
$\left [ \frac{n-k}{p^{i}} \right ] = \left [ \left [ \frac{n}{p^{i}} \right ] - \left [ \frac{k}{p^{i}} \right ] + \frac{p^{i} – (q+1)}{p^{i}} \right ] = \left [ \frac{n}{p^{i}} \right ] - \left [ \frac{k}{p^{i}} \right ]$,
поскольку $0 < p^{i} – (q+1) < p^{i}$. Поэтому $d_{k} = 0$ при $k = 0, 1, \cdots , n$, а значит, условие а) выполнено. Доказательство закончено.