теория-чисел - Докажите, что при любом натуральном n число является целым

Переформулируем условие: по сути, требуется доказать, что НОД чисел от $%1$% до $%2n+1$% делится на $%(2n+1)!/(n!)^2$%. Последнее число является целым, поскольку оно равно $%(n+1)C_{2n+1}^n$%.

Разложим число $%(2n+1)!/(n!)^2$% в произведение степеней простых чисел. Пусть $%p^k$% -- один из сомножителей такого произведения, где $%p$% простое, $%k=k(p)\ge1$%. Достаточно доказать, что $%p^k\le2n+1$%. Тогда НОД$%(1,2,...,2n+1)$% делится на $%p^k$% для каждого такого простого $%p$%, а потому делится и на произведение $%\prod\limits_p p^{k(p)}$%, что и нужно установить.

Прежде всего, выясним, на какую максимальную степень простого числа $%p$% делится число $%m!$%. Среди чисел от $%1$% до $%m$% имеется ровно $%\lfloor{\frac{m}{p}}\rfloor$% делящихся на $%p$%. Среди них ровно $%\lfloor{\frac{m}{p^2}}\rfloor$% делящихся на $%p^2$%, ровно $%\lfloor{\frac{m}{p^3}}\rfloor$% делящихся на $%p^3$% и так далее. Поэтому искомый показатель степени будет равен $$\nu_p(m)=\left\lfloor{\frac{m}{p}}\right\rfloor+\left\lfloor{\frac{m}{p^2}}\right\rfloor+\cdots,$$ где суммирование ведётся до тех пор, пока получаются ненулевые слагаемые.

Теперь ясно, что интересующий нас показатель $%k(p)$% будет равен $%\nu_p(2n+1)-2\nu_p(n)$%. Оценим его сверху. Ясно, что $%k(p)$% при этом будет равняться сумме величин вида $%\lfloor{\frac{2n+1}{p^t}}\rfloor-2\lfloor{\frac{n}{p^t}}\rfloor$%, где $%t=1,2,...$%. Ключевым соображением здесь является тот факт, что каждое такое слагаемое равно нулю или единице; проверим это.

Пусть целая часть числа $%\frac{n}{p^t}$% равна $%q$%. Тогда $%qp^t\le n < (q+1)p^t$%. В частности, $%n+1\le(q+1)p^t$%, и потому $%2n+1 < 2n+2\le2(q+1)p^t$%. Следовательно, $%\frac{2n+1}{p^t} < 2q+2$%, и тем самым $%\lfloor{\frac{2n+1}{p^t}}\rfloor-2\lfloor{\frac{n}{p^t}}\rfloor < 2$%, будучи целым числом. Отсюда ясно, что оно равно $%0$% или $%1$% (отрицательным это число быть не может).

Итак, мы установили, что $%k=k(p)$% равно $%\nu_p(2n+1)-2\nu_p(n)$%, что, в свою очередь, есть сумма нулей или единиц вида $%\lfloor{\frac{2n+1}{p^t}}\rfloor-2\lfloor{\frac{n}{p^t}}\rfloor$%, где $%t=1,2,...$%. Понятно, что ненулевые слагаемые могут получиться только при условии $%p^t\le2n+1$%, то есть этих слагаемых не больше, чем $%\log_p(2n+1)$%. Поскольку суммируются только нули и единицы, вся сумма не превосходит числа слагаемых, то есть $%k(p)\le\log_p(2n+1)$%. Но это в точности значит, что $%p^{k(p)}\le2n+1$%, а именно это мы и ставили себе целью доказать.

Приведённое рассуждение может на первый взгляд показаться длинным, но на самом деле оно весьма естественное.