Разделы 
Дополнительно
Задача по математике - 2787
2019-05-06 
а) Доказать, что произведение $n$ последовательных целых чисел делится на $n!$.
б) Доказать, что дробь $\frac {n!}{a! b! \cdots k!}$ есть число целое, если только $a + b + \cdots + k \leq n$.
в) Доказать, что $(n!)!$ делится на $n!^{(n-1)!}$.
г) Доказать, что произведение $n$ последовательных целых чисел, образующих арифметическую прогрессию, разность которой взаимно проста с $n!$, делится на $n!$.
Примечание. Задача г является обобщением задачи а.
Решение:
Первое решение задач а) и б). Решим сначала задачу а). Пусть $t + 1, t + 2, \cdots, t + n$ будут $n$ произвольных, последовательных целых чисел. Подсчитаем для каждого простого числа p наивысшую степень $m$, с которой оно входит в произведение $n!$ и наивысшую степень $s$, с которой оно входит в произведение $(t+1) \cdots (t+n)$. Для этого обозначим через $m_1$ число чисел ряда $1, 2, \cdots, n$, в которые $р$ входит по крайней мере в первой степени, через $m_2$ - число чисел того же ряда, в которые $р$ входит по крайней мере во второй степени, и т. д. Тогда показатель, с которым $р$ входит в $n!$, будет равен $m = m_1 + m_2 + \cdots$.
Если теперь $s_1$ - число чисел ряда $t+1, \cdots, t+n$, делящихся на $p, s_2$ - число чисел этого же ряда, делящихся на $p^2$, и т. д., то показатель $s$, с которым $р$ входит в произведение $(t+1) \cdots (t+n)$, равен $s = s_1 + s_2 + \cdots$.
Но число чисел ряда $t+1, \cdots, t+n$ делящихся на $р$, не меньше чем $m_1$. Действительно, среди чисел $t+1, \cdots, t+n$ находятся также числа $t+p, t+2p, \cdots, t+m_1p$, а в каждом промежутке между $t+kp$ и $t + (k+1)p (k = 0,1,2, \cdots, m_1 - 1)$ есть хотя бы одно число, делящееся на $р$. Таким образом, $s_1 \geq m_1$ аналогично $s_2 \geq m_2$, и т. д., а потому $s \geq m$. Но это означает, что каждый простой сомножитель числа $n!$ входит в состав числа $(t+1) \cdots (t+n)$, причем в степени, не меньшей чем он входит в $n!$, т. е. число $(t+1) \cdots (t+n)$ делится на $n!$
б) Произведение первых $а$ сомножителей в $n!$ совпадает с $а!$; произведение следующих $b$ сомножителей в силу задачи а) делится на $b!$; произведение следующих с сомножителей - на $с!$, и т. д. Так как $a+b+c+ \cdots+k \neq n$, то отсюда следует, что $n!$ разделится на $a!b! \cdots k!$.
Другое решение задач а) и б). Решим сначала задачу б). Показатель $m$, с которым некоторое простое число $р$ входит в $a!$, как мы видели, равен $m = m_1 + m_2 + \cdots$, где $m_1$ - число чисел ряда $1,2, \cdots, a$, а кратных $p, m_2$ – кратных $p^2$, и т. д. Но число чисел, кратных $p$, равно $\left [ \frac{a}{p} \right ]$, кратных $p^2$ – равно $\left [ \frac{a}{p^2} \right ]$ и т. д., где целые $\left [ \frac{a}{p} \right ] \left [ \frac{a}{p^2} \right ], \cdots$ – целые части дробей $\frac{a}{p}, \frac{a}{p^2}, \cdots$. Таким образом $m = \left [ \frac{a}{p} \right ] + \left [ \frac{a}{p^2} \right ] + \cdots$. Пусть теперь $р$ - любое простое число.
Тогда показатель, с которым $р$ войдет в числитель, равен $\left [ \frac{n}{p} \right ] + \left [ \frac{n}{p^2} \right ] + \cdots$. Показатель, с которым $р$ войдет в знаменатель, равен $\left [ \frac{a}{p} \right ] + \left [ \frac{a}{p^2} \right ] + \cdots + \left [ \frac{b}{p} \right ] + \left [ \frac{b}{p^2} \right ] + \cdots + \left [ \frac{k}{p} \right ] + \left [ \frac{k}{p^2} \right ] + \cdots$.
Но так как $n \geq a+b+ \cdots + k$, то 1), мы получим отсюда, что
$\left [ \frac{n}{p} \right ] + \left [ \frac{n}{p^2} \right ] + \cdots \geq \left ( \left [ \frac{a}{p} \right ] + \left [ \frac{b}{p} \right ] + \cdots \right ) + \left ( \left [ \frac{a}{p^2} \right ] + \left [ \frac{b}{p^2} \right ] + \cdots \right ) + \cdots$,
т. е. $p$ войдет в числитель в большей степени, чем в знаменатель. Значит, наша дробь есть целое число.
Решим теперь задачу а). Дополним для этого произведение $(t+1) \cdots (t+n)$ до $(t+n)!$. По только что доказанному дробь
$\frac {(t+n) \cdots (t+1) t (t-1) \cdots 1}{n! t (t-1) \cdots 1} = \frac {(n + t)!}{n! t!} = \frac {(t+1) \cdots (t+n)}{n!}$
есть число целое.
в) ($(n!)!$) есть произведение $n!$ первых целых чисел. Но эти $n!$ чисел можно разбить на $(n-1)!$ групп по $n$ последовательных целых чисел, а произведение чисел каждой из этих групп в силу результата задачи а) делится на $n!$.
г) Пусть рассматриваемые числа будут $a, a+d, a+2d, \cdots, a+ (n-1)d$. Докажем сначала, что существует такое целое число $k$, что произведение $kd$ дает при делении на $n!$ в остатке 1. Действительно, рассмотрим $n!$ - 1 чисел $d, 2d, 3d, \cdots, (n! - 1)d$. Ни одно из этих чисел не делится на $n!$, так как $d$ взаимно просто с $n!$. С другой стороны, никакие два произведения $pd$ и $qd$, где $р, q$ - целые числа, меньшие $n!$, не могут давать при делении на $n!$ одинаковые остатки, так как иначе разность $pd - qd = (p-q)d$ делилась бы на $n!$. Таким образом, рассматриваемые $n! - 1$ чисел должны при делении на $n!$ давать $n! - 1$ разных остатков, откуда вытекает существование числа $k$, такого, что произведение $kd$ дает при делении на $n!$ остаток $1 \div kd = r \cdot n! + 1$.
Обозначим теперь $ka$ через $А$. Тогда мы имеем:
$ka = A$,
$k(a+d) = A + kd = (A+1) + r \cdot n!$,
$k(a+2d) = A + 2kd = (A+2) + 2r \cdot n!$,
$\cdots$
$k[a+ (n-1)d] = A + (n-1)kd = [A + (n-1)] + (n-1) r \cdot n!$.
Отсюда следует, что произведение
$k^n a (a+d)(a+2d) \cdots [a + (n-1)d]$
дает при делении на $n!$ такой же остаток, как и произведение $A(A+1)(A+2) \cdots [A + (n-1)]$. Но последнее из этих двух произведений делится на $n!$ в силу задачи a), a $k^n$ взаимно просто с $n!$, так как, если бы $k$ не было взаимно просто с $n!$, $kd$ тоже не могло бы быть взаимно просто с $n!$.
а) Доказать, что произведение $n$ последовательных целых чисел делится на $n!$.
б) Доказать, что дробь $\frac {n!}{a! b! \cdots k!}$ есть число целое, если только $a + b + \cdots + k \leq n$.
в) Доказать, что $(n!)!$ делится на $n!^{(n-1)!}$.
г) Доказать, что произведение $n$ последовательных целых чисел, образующих арифметическую прогрессию, разность которой взаимно проста с $n!$, делится на $n!$.
Примечание. Задача г является обобщением задачи а.
Решение:
Первое решение задач а) и б). Решим сначала задачу а). Пусть $t + 1, t + 2, \cdots, t + n$ будут $n$ произвольных, последовательных целых чисел. Подсчитаем для каждого простого числа p наивысшую степень $m$, с которой оно входит в произведение $n!$ и наивысшую степень $s$, с которой оно входит в произведение $(t+1) \cdots (t+n)$. Для этого обозначим через $m_1$ число чисел ряда $1, 2, \cdots, n$, в которые $р$ входит по крайней мере в первой степени, через $m_2$ - число чисел того же ряда, в которые $р$ входит по крайней мере во второй степени, и т. д. Тогда показатель, с которым $р$ входит в $n!$, будет равен $m = m_1 + m_2 + \cdots$.
Если теперь $s_1$ - число чисел ряда $t+1, \cdots, t+n$, делящихся на $p, s_2$ - число чисел этого же ряда, делящихся на $p^2$, и т. д., то показатель $s$, с которым $р$ входит в произведение $(t+1) \cdots (t+n)$, равен $s = s_1 + s_2 + \cdots$.
Но число чисел ряда $t+1, \cdots, t+n$ делящихся на $р$, не меньше чем $m_1$. Действительно, среди чисел $t+1, \cdots, t+n$ находятся также числа $t+p, t+2p, \cdots, t+m_1p$, а в каждом промежутке между $t+kp$ и $t + (k+1)p (k = 0,1,2, \cdots, m_1 - 1)$ есть хотя бы одно число, делящееся на $р$. Таким образом, $s_1 \geq m_1$ аналогично $s_2 \geq m_2$, и т. д., а потому $s \geq m$. Но это означает, что каждый простой сомножитель числа $n!$ входит в состав числа $(t+1) \cdots (t+n)$, причем в степени, не меньшей чем он входит в $n!$, т. е. число $(t+1) \cdots (t+n)$ делится на $n!$
б) Произведение первых $а$ сомножителей в $n!$ совпадает с $а!$; произведение следующих $b$ сомножителей в силу задачи а) делится на $b!$; произведение следующих с сомножителей - на $с!$, и т. д. Так как $a+b+c+ \cdots+k \neq n$, то отсюда следует, что $n!$ разделится на $a!b! \cdots k!$.
Другое решение задач а) и б). Решим сначала задачу б). Показатель $m$, с которым некоторое простое число $р$ входит в $a!$, как мы видели, равен $m = m_1 + m_2 + \cdots$, где $m_1$ - число чисел ряда $1,2, \cdots, a$, а кратных $p, m_2$ – кратных $p^2$, и т. д. Но число чисел, кратных $p$, равно $\left [ \frac{a}{p} \right ]$, кратных $p^2$ – равно $\left [ \frac{a}{p^2} \right ]$ и т. д., где целые $\left [ \frac{a}{p} \right ] \left [ \frac{a}{p^2} \right ], \cdots$ – целые части дробей $\frac{a}{p}, \frac{a}{p^2}, \cdots$. Таким образом $m = \left [ \frac{a}{p} \right ] + \left [ \frac{a}{p^2} \right ] + \cdots$. Пусть теперь $р$ - любое простое число.
Тогда показатель, с которым $р$ войдет в числитель, равен $\left [ \frac{n}{p} \right ] + \left [ \frac{n}{p^2} \right ] + \cdots$. Показатель, с которым $р$ войдет в знаменатель, равен $\left [ \frac{a}{p} \right ] + \left [ \frac{a}{p^2} \right ] + \cdots + \left [ \frac{b}{p} \right ] + \left [ \frac{b}{p^2} \right ] + \cdots + \left [ \frac{k}{p} \right ] + \left [ \frac{k}{p^2} \right ] + \cdots$.
Но так как $n \geq a+b+ \cdots + k$, то 1), мы получим отсюда, что
$\left [ \frac{n}{p} \right ] + \left [ \frac{n}{p^2} \right ] + \cdots \geq \left ( \left [ \frac{a}{p} \right ] + \left [ \frac{b}{p} \right ] + \cdots \right ) + \left ( \left [ \frac{a}{p^2} \right ] + \left [ \frac{b}{p^2} \right ] + \cdots \right ) + \cdots$,
т. е. $p$ войдет в числитель в большей степени, чем в знаменатель. Значит, наша дробь есть целое число.
Решим теперь задачу а). Дополним для этого произведение $(t+1) \cdots (t+n)$ до $(t+n)!$. По только что доказанному дробь
$\frac {(t+n) \cdots (t+1) t (t-1) \cdots 1}{n! t (t-1) \cdots 1} = \frac {(n + t)!}{n! t!} = \frac {(t+1) \cdots (t+n)}{n!}$
есть число целое.
в) ($(n!)!$) есть произведение $n!$ первых целых чисел. Но эти $n!$ чисел можно разбить на $(n-1)!$ групп по $n$ последовательных целых чисел, а произведение чисел каждой из этих групп в силу результата задачи а) делится на $n!$.
г) Пусть рассматриваемые числа будут $a, a+d, a+2d, \cdots, a+ (n-1)d$. Докажем сначала, что существует такое целое число $k$, что произведение $kd$ дает при делении на $n!$ в остатке 1. Действительно, рассмотрим $n!$ - 1 чисел $d, 2d, 3d, \cdots, (n! - 1)d$. Ни одно из этих чисел не делится на $n!$, так как $d$ взаимно просто с $n!$. С другой стороны, никакие два произведения $pd$ и $qd$, где $р, q$ - целые числа, меньшие $n!$, не могут давать при делении на $n!$ одинаковые остатки, так как иначе разность $pd - qd = (p-q)d$ делилась бы на $n!$. Таким образом, рассматриваемые $n! - 1$ чисел должны при делении на $n!$ давать $n! - 1$ разных остатков, откуда вытекает существование числа $k$, такого, что произведение $kd$ дает при делении на $n!$ остаток $1 \div kd = r \cdot n! + 1$.
Обозначим теперь $ka$ через $А$. Тогда мы имеем:
$ka = A$,
$k(a+d) = A + kd = (A+1) + r \cdot n!$,
$k(a+2d) = A + 2kd = (A+2) + 2r \cdot n!$,
$\cdots$
$k[a+ (n-1)d] = A + (n-1)kd = [A + (n-1)] + (n-1) r \cdot n!$.
Отсюда следует, что произведение
$k^n a (a+d)(a+2d) \cdots [a + (n-1)d]$
дает при делении на $n!$ такой же остаток, как и произведение $A(A+1)(A+2) \cdots [A + (n-1)]$. Но последнее из этих двух произведений делится на $n!$ в силу задачи a), a $k^n$ взаимно просто с $n!$, так как, если бы $k$ не было взаимно просто с $n!$, $kd$ тоже не могло бы быть взаимно просто с $n!$.
