Областная олимпиада по математике, 2001 год, 11 класс

Даны натуральные числа $q$, $n$ $\text{и}$ $r$, $0 < r \le n$. Докажите, что число $(q^n-1)(q^n-q) \dots (q^n-q^{r-1})$ делится на $r$!.

Комментарий/решение

Рассматриваем $r\geq 5:$

$$p\in\mathbb{P} \leq r\quad v_p(r!)=\left[\dfrac{r}{p} \right]+\dots+\left[\dfrac{r}{p^k} \right] \leq \dfrac{r}{p}+\dots+\dfrac{r}{p^k}< \dfrac{rp}{p-1}$$

Если $p \mid q:$

$$~ v_p(q)\cdot \dfrac{(r-1)r}{2} \geq 2r > v_p(r!)$$

Если $p \not \mid q:$

$$p\mid q^{p-1}-1, \quad v_p(q^{(p-1)k}-1)=v_p(q^{p-1}-1)+v_p(k) \geq v_p(k)+1$$

$$v_p(q^n-1)+\dots+v_p(q^{n-r+1}-1) \geq \left[\dfrac{n}{p-1} \right]-\left[\dfrac{n-r}{p-1} \right]+\left[\dfrac{n}{p(p-1)} \right]-\left[\dfrac{n-r}{p(p-1)} \right]+\dots+\left[\dfrac{n}{p^{k-1}(p-1)} \right]-\left[\dfrac{n-r}{p^{k-1}(p-1)} \right]$$

Остается показать что выражение справа не меньше $v_p(r!)$, достаточно показать что:

$$\left[\dfrac{n}{p^t(p-1)} \right]-\left[\dfrac{n-r}{p^t(p-1)} \right] \geq \left[\dfrac{r}{p^{t+1}} \right] \quad 0\leq t \leq k-1$$

$$p^{t+1}(p-1)\left[\dfrac{n}{p^t(p-1)} \right]-p^{t+1}(p-1)\left[\dfrac{n-r}{p^t(p-1)} \right] \geq p^{t+1}(p-1)\left[\dfrac{r}{p^{t+1}} \right]$$

Это сравнимо с:

$$pr-n'+nr' \geq (p-1)r-r' \quad pn\equiv n' \pmod {p^{t+1}(p-1)}, ~ pn-pr \equiv nr' \pmod {p^{t+1}(p-1)}, ~ (p-1)r \equiv r' \pmod {p^{t+1}(p-1)}$$

$$r+r'+nr' \geq n' \quad r+r'+nr' \equiv r+(p-1)r+pn-pr \equiv n' \pmod {p^{t+1}(p-1)}$$

Что верно.

Для $r=1, 2, 3, 4$ используем что:

$q\not\equiv 0 \pmod 2 \rightarrow q^2-1 \equiv 0 \pmod 8 \quad q\not\equiv 0 \pmod 3 \rightarrow q^2-1\equiv 0 \pmod 3$