12-ші «Жібек жолы» математикалық олимпиадасы, 2012 жыл

Бізге бүтін $n > 1$ саны берілген. $\left\{ C_{2n}^{2i+1}:0\le i\le n-1 \right\}$ сандар жиынының ең үлкен ортақ бөлгішін, яғни әрбір $i = 0, 1, \ldots, n-1 $ үшін $C_{2n}^{2i+1}$ санын қалдықсыз бөлетін ең үлкен оң бүтін санды анықтаңдар. (Мұнда $C_{m}^{l}=\frac{m!}{l!\left( m-l \right)!}$ — биномдық коэффициент.) ( А. Джумадильдаев )

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

Ответ: $\boxed{d=2^{v_2{(2n)}}}$

Будем пользоватся известным фактом для любого натурального $n$ и простого $p$:

$$v_p{(n!)}=\left[\frac{n}{p}\right]+\left[\frac{n}{p^2}\right]+ ~...$$

Утверждение 1: $$v_2{\left(\binom{2n}{2i+1}\right)} \geq v_2{(2n)}$$

Доказательство. У нас верны равенства:

$$v_2{\left(\binom{2n}{2i+1}\right)}=\sum^{\infty}_{k=1}{\left( \left[\frac{2n}{2^k} \right] - \left[\frac{2i+1}{2^k} \right] -\left[\frac{2n-2i-1}{2^k} \right] \right)}$$

$$= \sum^{\infty}_{k=1}{\left( \left[\frac{2n}{2^k} \right] - \left[\frac{2i}{2^k} \right] -\left[\frac{2n-2i-2}{2^k} \right] \right)}$$

$$v_2{\left(\binom{2n-2}{2i}\right)}=\sum^{\infty}_{k=1}{\left( \left[\frac{2n-2}{2^k} \right] - \left[\frac{2i}{2^k} \right] -\left[\frac{2n-2i-2}{2^k} \right] \right)}$$

Выводим что:

$$v_2{\left(\binom{2n}{2i+1}\right)}-v_2{\left(\binom{2n-2}{2i}\right)}= \sum^{\infty}_{k=1}{\left( \left[\frac{2n}{2^k} \right] - \left[\frac{2n-2}{2^k} \right] \right)}=1\cdot v_2{(2n)}+0$$

Где:

$$\left[\frac{2n}{2^k} \right]-\left[\frac{2n-2}{2^k}\right]=\left\{\begin{gathered} 0,~2^k\nmid 2n\\ 1,~ 2^k \mid 2n\\ \end{gathered}\right.$$ $\blacksquare$.

Пусть $p$ любой нечетный простой делитель $2n$ такой что: $$p^N < 2n < p^{N+1}$$

для некоторого натурального $N$.

Утверждение 2: $$p \nmid \binom{2n}{p^N}$$

Доказательство. У нас верны равенства:

$$v_p{\left(\binom{2n}{p^N}\right)}=\sum^{\infty}_{k=1}{\left( \left[\frac{2n}{p^k} \right] - \left[\frac{p^N}{p^k} \right] -\left[\frac{2n-p^N}{p^k} \right] \right)}$$

$$=\sum^{N}_{k=1}{\left( \left[\frac{2n}{p^k} \right] - \left[\frac{p^N}{p^k} \right] -\left[\frac{2n-p^N}{p^k} \right] \right)}=\sum^{N}_{k=1}{\left( \left[\frac{2n-p^N}{p^k} \right] -\left[\frac{2n-p^N}{p^k} \right] \right)}=0$$

Где используем факт что $\left[\frac{p^N}{p^k} \right]$ является целым числом $\blacksquare$.

Обозначим НОД как $d$, тогда верно следующее:

$$d \mid 2n=\binom{2n}{1} \Leftrightarrow v_p{(d)} \leq v_p{(2n)}$$

Получаем по утверждениям 1 и 2 что у нас:

$$v_p(d)=\left\{\begin{gathered} 0,~p\neq 2\\ v_2(2n),~ p=2\\ \end{gathered}\right.$$

Следовательно $\boxed{d=2^{v_2{(2n)}}}$.