Изображения страниц
Текст статьи Задачи наших читателей // Квант. — 1982. — № 1. — С. 39.
«Квант» получает много писем с новыми задачами. Часть из них мы помещаем в постоянных разделах “Задачник «Кванта»” и “«Квант» для младших школьников”; немало интересных по формулировке отдельных задач публикуется под рубриками «Задачи наших читателей» и «Задачи для исследования». Иногда это — забавные задачи-головоломки, ребусы, но нередко — и такие, над решением которых придётся серьёзно потрудиться; кроме школьной программы, могут понадобиться дополнительные сведения (из статей «Кванта», факультативных курсов и дополнительной литературы).
Решения этих задач обычно помещаются в следующем номере журнала.
В этом номере мы предлагаем вам несколько трудных задач по алгебре и арифметике целых чисел.
Докажите, что число, составленное из 1980 двоек, делится на 1982. Указание. Используйте малую теорему Ферма: если
$p$ — простое число и$a$ не делится на$p$, то$a^{p-1}-1$ делится на$p$ («Квант», 1978, № 10, с. 7 или 1972, № 10, с. 2).Докажите, что если
$\dfrac{m!}{n!\,(m-n)!}$ делится на$p^r$ и$p$ — простое число, то$p^r\le m$. Для каких$m$ может достигаться равенство?Про многочлен
$8x^4+ax^3+bx^2+cx+d$ известно, что для всех$x$ из промежутка$[-1;1]$ его значения по модулю не превосходят единицы. Докажите, что это — многочлен Чебышева$T_4(x)$ (см. таблицу 1 из статьи Н. Васильева и А. Зелевинского на с. 12). Указание. Рассмотрите значения этого многочлена при$x=0$, $\pm\dfrac1{\sqrt2}$, $\pm\dfrac12$, $\pm1$.
Ответы, указания, решения
- Поскольку
$\underbrace{22\ldots2}_{\mathclap{1980~\text{«двоек»}}}= 2\cdot\dfrac{100^{991-1}-1}9$, $100^{991-1}-1$ по малой теореме Ферма делится на 991 и числа 9 и 991 взаимно просты, число$\underbrace{22\ldots2}_{\mathclap{1980~\text{«двоек»}}}$ делится на$2\cdot991=1982$. Пусть
$q$ — простое число и$t$ — показатель степени, с которым$q$ входит в разложение числа$l!=1\cdot2\cdot\ldots\cdot l$ на простые множители. Среди чисел, не превосходящих$l$, ровно$\left[\dfrac lq\right]$ делится на$q$; из чисел, кратных$q$, ровно$\left[\dfrac l{q^2}\right]$ делится на$q^2$; из чисел, кратных$q^2$, ровно$\left[\dfrac l{q^3}\right]$ делится на$q^3$ и т. д.; поэтому $$ t={\left(\left[\dfrac lq\right]-\left[\dfrac l{q^2}\right]\right)}+ 2{\left(\left[\dfrac l{q^2}\right]-\left[\dfrac l{q^3}\right]\right)}+ 3{\left(\left[\dfrac l{q^3}\right]-\left[\dfrac l{q^4}\right]\right)}+\ldots= \left[\dfrac lq\right]+\left[\dfrac l{q^2}\right]+\left[\dfrac l{q^3}\right] +\ldots $$ (очевидно, здесь все слагаемые, начиная с некоторого, — нули). Поэтому если$s$ — показатель степени, которой$p$ входит в$\dfrac{m!}{n!\,(m-n)!}$, то $$ s=\sum\limits_k\left(\left[\dfrac m{p^k}\right]-\left[\dfrac n{p^k}\right]- \left[\dfrac{m-n}{p^k}\right]\right), $$ причём при$k\gt\log_pm$ слагаемые обращаются в нуль, а при$k\le\log_pm$ — не превосходят 1, ибо являются целыми числами, меньшими 2: $$ \left[\dfrac m{p^k}\right]-\left[\dfrac n{p^k}\right]- \left[\dfrac{m-n}{p^k}\right]= \left\{\dfrac n{p^k}\right\}+\left\{\dfrac{m-n}{p^k}\right\}- \left\{\dfrac m{p^k}\right\}\lt2. $$ В силу этого$s$ нe превосходит числа слагаемых, т. е.$s\le\log_pm$. Поэтому$r\le s\le\log_pm$, т. е.$p^r\le m$. Равенство
$p^r=m$ достигается для всех$m$, являющихся степенью простого числа.