М1787. Диафантово уравнение

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

Условие

Пусть $ p $ и $ q $ — натуральные числа, большие 1. Известно, что $ q^3-1 $ делится на $ p $, а $ p-1 $ делится на $ q $. Докажите, что $ p = q^{\frac{3}{2}}+1 $ или $ p = q^2 + q + 1 $.

Решение

Будем рассуждать так.
Имеем $ q^3 — 1 = pk $ для некоторого $ k \geqslant 1 $. Так как $ p = 1 \pmod {q}$, то $ k = -1 \pmod {q}$, т.е. $ k = lq-1$ для некоторого $ l \geqslant 1 $. Из равенства $ \displaystyle p = \frac{(q^3-1)}{(lq-1)}$ следует, что $ l < q^2 $, а также то, что числа $ q^2-l $ и $ q-l^2 $ делятся на $ lq-1 $. Предположим теперь, что $ p \neq q^{\frac{3}{2}} + 1$ (в частности, $ l \neq q^{1/2}$). Если $ 1 < l < q, l \neq q^{\frac{1}{2}} $, то $ 0 < \left|q-l^2\right| < lq-1 $ и, следовательно, делимость $ q-l^2 $ на $ lq-1 $ невозможна. Если же $ q \leqslant l < q^2$, то $ 0 < q^2-l < lq-1$ и невозможна делимость $ q^2-l$ на $  lq-1$. Таким образом, $ l = 1$ и $p = q^2 + q + 1 $. Этим всё доказано.

Н. Осипов

М1787. Диафантово уравнение: 2 комментария

    1. То что (q^2 — l) делится на (lq — 1) следует из того, что (p — 1) делится на q, если подставить формулу для p в виде дроби многочленов. А вот почему (q — l^2) делится на (lq — 1) вопрос хороший )

Добавить комментарий для Artem Отменить ответ

Ваш адрес email не будет опубликован. Обязательные поля помечены *