М1814. О периодической последовательности

Задача из журнала «Квант»(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$, то ответ будет утвердительным (читателю предлагается доказать это в качестве упражнения).

Н.Осипов

M1815. О перпендикулярах в неплоском четырехугольнике

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

Условие

Общие перпендикуляры к противоположным сторонам неплоского четырехугольника $ABCD$ взаимно перпендикулярны.

Докажите, что они пересекаются.

Решение

Инструментом решения является теорема Менелая для пространственного четырехугольника, утверждающая, что точки $X,$ $U,$ $Y,$ $V,$ взятые на сторонах четырехугольника $AB,$ $BC,$ $CD,$ $DA$ или их продолжениях, лежат в одной плоскости тогда и только тогда, когда $\frac{AX}{XB} \cdot \frac{BU}{UC} \cdot \frac{CY}{YD} \cdot \frac{DV}{VA} = 1.$

Для доказательства теоремы Менелая продолжим прямые $XU$ и $YV$ до пересечения с $AC.$ Точки $X,$ $U,$ $Y,$ $V$ лежат в одной плоскости тогда и только тогда, когда все три прямые пересекаются в одной точке $P$ либо параллельны (рис. 1).

Рис. 1

Но в этом случае, применяя теорему Менелая к треугольникам $ABC$ и $ACD,$ получаем $\frac{AX}{XB} \cdot \frac{BU}{UC} \cdot \frac{CP}{PA} = 1$ и $\frac{CY}{YD} \cdot \frac{DV}{VA} \cdot \frac{AP}{PC} = 1.$ Перемножая эти равенства, получим требуемое соотношение.

Пусть теперь $XY$ – перпендикуляр к сторонам $AB$ и $CD,$ $UV$ – перпендикуляр к $AD$ и $BC.$ При ортогональной проекции на плоскость, параллельную $XY$ и $UV,$ прямой угол между прямыми $AB$ и $XY$ остается прямым. Поэтому четырехугольник $ABCD$ проецируется в прямоугольник $A’B’C’D’,$ а прямые $XY$ и $UV$ – в параллельные его сторонам прямые $X′Y′$ и $U′V′$ (рис. 2). Очевидно, что $\frac{A’X’}{X’B’} \cdot \frac{B’U’}{U’C’} \cdot \frac{C’Y’}{Y’D’} \cdot \frac{D’V’}{V’A’} = 1.$

Рис. 2

Следовательно, $\frac{AX}{XB} \cdot \frac{BU}{UC} \cdot \frac{CY}{YD} \cdot \frac{DV}{VA} = 1,$ и по теореме Менелая точки $X,$ $Y,$ $U,$ $V$ лежат в одной плоскости. Отсюда сразу следует утверждение задачи.

А.Заславский