Задача из журнала «Квант» (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$. Этим всё доказано.

Н. Осипов