Задача из журнала «Квант» (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\equiv 1\left(\bmod{q}\right)$, то $k\equiv-1\left(\bmod{q}\right)$, т.е. $k = lq-1$ для некоторого $l\geqslant 1$. Из равенства $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^{\frac{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$ . Этим все доказано.

Н. Осипов