Задача из журнала «Квант» (2002 год, 1 выпуск)

Условие

Докажите, что $\frac{\displaystyle a}{\displaystyle\sqrt{a^2+8bc}} + \frac{\displaystyle b}{\displaystyle\sqrt{b^2+8ca}} + \frac{\displaystyle c}{\displaystyle\sqrt{c^2+8ab}} \geqslant 1$ для любых положительных чисел $a$, $b$ и $c.$

Доказательство

Так как выражение в левой части однородно относительно $a,\ b$ и $c$ (т.е. $f(a, b, c)$=$f(\lambda a, \lambda b, \lambda c)$), то мы можем считать, что $abc = 1.$ Из равенства $abc = 1$ следует, что $\displaystyle\frac{a}{\sqrt{a^2+8bc}} = \displaystyle\frac{1}{\sqrt{1+\displaystyle\frac{8abc}{a^3}}} = \displaystyle\frac{1}{\sqrt{1+\displaystyle\frac{8}{a^3}}}\ .$ Пусть $1+\displaystyle\frac8{a^3}=x\ , \ 1+\displaystyle\frac8{b^3}=y\ , \ 1+\displaystyle\frac8{c^3}=z\ ,$ тогда нужно доказать неравенство \begin{multline}\displaystyle\frac1{\sqrt{\mathstrut x}} + \displaystyle\frac1{\sqrt{\mathstrut y}} + \displaystyle\frac1{\sqrt{\mathstrut z}} \geqslant 1 \ \Leftrightarrow \ \sqrt{\mathstrut xy} + \sqrt{\mathstrut xz} + \sqrt{\mathstrut yz} \geqslant \sqrt{\mathstrut xyz}\ \Leftrightarrow \\ \Leftrightarrow \ xy + xz + yz + 2\sqrt{x^2yz} + 2\sqrt{xy^2z} + 2\sqrt{xyz^2} \geqslant xyz \ \Leftrightarrow \\ \Leftrightarrow xy + xz + yz + 2\sqrt{\mathstrut xyz} \left(\sqrt{\mathstrut x} + \sqrt{\mathstrut y} + \sqrt{\mathstrut z} \right) \geqslant xyz\ .\end{multline} Теперь, применив неравенство о среднем арифметическом и среднем геометрическом, находим $x = 1 + \underbrace{\displaystyle\frac1{a^3} + … + \displaystyle\frac1{a^3}}_{8\ раз} \geqslant 9\sqrt[9]{1\cdot\left(\displaystyle\frac1{a^3}\right)^8} = \displaystyle\frac9{a^{\frac83}}\ ,$ поэтому $\sqrt{\mathstrut x} \geqslant \displaystyle\frac3{a^{\frac43}}\ .$ Аналогично, $\sqrt{\mathstrut y} \geqslant \displaystyle\frac3{b^{\frac43}}\ , \ \sqrt{\mathstrut z} \geqslant \displaystyle\frac3{c^{\frac43}}\ ,$ следовательно, $\sqrt{\mathstrut xyz} \geqslant \displaystyle\frac{27}{\left(abc\right)^{\frac43}} = 27$ и $\sqrt{\mathstrut x} + \sqrt{\mathstrut y} + \sqrt{\mathstrut z} \geqslant 3\sqrt[3]{\sqrt{\mathstrut xyz}} \geqslant 3\sqrt[3]{\mathstrut 27} = 9\ .$ Поэтому для доказательства неравенства $(1)$ достаточно показать, что \begin{equation}xy + xz + yz + 2 \cdot 27 \cdot 9 \geqslant xyz\ .\end{equation} Положим $\displaystyle\frac8{a^3} = A\ ,\ \displaystyle\frac8{b^3} = B\ ,\ \displaystyle\frac8{c^3} = C\ ,$ тогда $(2)$ примет вид $\left(1+A\right)\left(1+B\right) + \left(1+A\right)\left(1+C\right) + \left(1+B\right)\left(1+C\right) + 486 \geqslant \\ \geqslant \left(1+A\right)\left(1+B\right)\left(1+C\right)\ \Leftrightarrow A+B+C+488 \geqslant ABC\ .$
Но $A \cdot B \cdot C = \displaystyle\frac{8^3}{(abc)^3} = 8^3\ ,$ отсюда $A+B+C \geqslant 3\sqrt[3]{\mathstrut ABC} = 24\ ,$ и, значит, $A+B+C+488 \geqslant 512 = 8^3 = A \cdot B \cdot C\ .$ Утверждение доказано.

(Южная Корея)

Задача из журнала «Квант»(2002 год, 2 выпуск)

Условие

Пусть $a$, $m_1$, $m_2$ $-$ натуральные числа, причем $a$ взаимно просто как с $m_1$, так и с $m_2$. Обозначим через $r_n$ остаток от деления целой части числа $\frac{a^n}{m_1}$ на $m_2$ $(n = 0, 1, 2, \ldots)$.

Докажите, что последовательность $\{r_n\}$ является периодической.

Доказательство

Так как НОД$(a$, $m_1)$ $=$ НОД$(a$, $m_2) = 1$, то НОД$(a$, $m_1m_2) = 1$. Пусть $n_0 -$ какое-нибудь натуральное число, для которого $a^{n_0}$ при делении на $m_1m_2$ дает в остатке $1$. (Если НОД$(a$, $m_1m_2) = 1$, то такое число обязательно существует. Можно, например, положить $n_0 = \varphi(m_1m_2)$, где $ \varphi(m) — $ функция Эйлера $-$ см. статью В.Сендерова и А.Спивака «Малая теорема Ферма» в «Кванте» №1 за 2000 год.)

Тогда $a^{n_0} = Qm_1m_2 + 1$ для некоторого целого числа $Q$. Теперь при любом $n \geqslant n_0$ имеем $$\left[\frac{a^n}{m_1}\right] = \left[\frac{a^{n_0}a^{n-n_0}}{m_1}\right] = \left[\frac{(Qm_1m_2 + 1)a^{n-n_0}}{m_1}\right] =$$ $$= \left[a^{n-n_0}Qm_2 + \frac{a^{n-n_0}}{m_1}\right] = a^{n-n_0}Qm_2 + \left[\frac{a^{n-n_0}}{m_1}\right]$$ ($\left[x\right]$ обозначает целую часть числа $x$).

Таким образом, остатки чисел $\left[\frac{a^n}{m_1}\right]$ и $\left[\frac{a^{n-n_0}}{m_1}\right]$ при делении на $m_2$ совпадают, т.е. $r_n = r_{n-n_0}$. Значит, последовательность $\{r_n\}$ имеет период длины $n_0$ (доказано также и то, что этот период начинается с самого начала последовательности).

Возникает вопрос о длине наименьшего периода последовательности $\{r_n\}$. Верно ли, что если в качестве $n_0$ взять наименьшее натуральное число такое, что $a^{n_0}$ при делении на $m_1m_2$ дает в остатке $1$, то $n_0$ и будет длиной наименьшего периода? Как показывает пример $a = 3$, $m_1 = 13$, $m_2 = 2$ (здесь $n_0 = 3$, а последовательность $\{r_n\}$ сплошь состоит из нулей), ответ на этот вопрос в общем случае отрицателен. Однако если дополнительно предположить, например, что $m_2 \geqslant m_1$, то ответ будет утвердительным (читателю предлагается доказать это в качестве упражнения).

Н.Осипов

Задача из журнала «Квант» (2001 год, 4 выпуск)

Условие

Существует ли натуральное число $n$ такое, что $n$ имеет ровно $2000$ различных простых делителей и $2^n+1$ делится на $n$?

Решение

Докажем по индукции, что для любого натурального $k$ существует натуральное $n_k$, имеющее $k$ различных простых делителей, делящееся на $3$ и такое, что $2^{n_k}+1$ делится на $n_k$.

Для $k=1$ можно взять $n=3$. Пусть число $n_k=n$, кратное $3$, имеет $k$ различных простых делителей, причём $2^n+1$ делится на $n$.

Число $2^{3n}+1=\left(2^n+1\right)\left(2^{2n}-2n+1\right)$ делится на $3n$. Это следует из того, что $2^n+1$ делится на $n$, а
$$2^{2n}-2^n+1=\left(2^n-2\right)\left(2^n+1\right)+3\;\;\;(*)$$ делится на $3$ (поскольку при нечётном $n$ числа $2^n+1$ и $2^n-2$ делятся на $3$).

Далее, число $2^{2n}-2^n+1$ не делится на $9$, поскольку на $9$ делится произведение $\left(2^n-2\right)\left(2^n+1\right)$. Значит, поскольку $2^{2n}-2^n+1>3$ при $n>1$, то это число имеет при $n>1$ простой делитель $p>3$. Так как НОД $\left(2^n+1, 2^{2n}-2^n+1\right)=3$ (это тоже ясно из равенства $(*)$), то $p$ — не делитель $n$.

Из сказанного следует, что число $3pn$ имеет $k+1$ простой делитель, причём $2^{3pn}+1$ делится на $3pn$. Последнее следует, например из равенства
$$\left(2^{3n}\right)^p+1=\left(2^{3n}+1\right)\left(\left(2^{3n}\right)^{p-1}-\left(2^{3n}\right)^{p-2}+\cdots+1\right)$$

Для завершения решения достаточно положить $n_{k+1}=3pn=3pn_k$.

А.Егоров, В.Сендеров