6-я Международная Жаутыковская олимпиада, 2010 год

Найдите все простые числа $p$, $q$ такие, что $p^3-q^7=p-q$.

Комментарий/решение

Разложив на множители

$p(p-1)(p+1) = q(q-1)(q+1)(q^2-q+1)(q^2+q+1)$ левая часть равенство имеет только один множитель $3$ так как три последователен числа, а правая больше одной при $q >3$ потому что $q(q-1)(q+1)$ три последовательных числа , а один из $q(q-1), \ q(q+1)$ будет иметь остаток $2$ по $\mod \ 3$ если $q \ne 3$, значит решение только единственно при $q=3$ откуда $p=13$.

$p(p-1)(p+1)$ может иметь более одного множителя 3, например, если $p\equiv1\pmod9$.

$p^3-p=q^7-q<p^7-p\Rightarrow p>q$

$q|p^2-1=(p-1)(p+1)$

$p|q^6-1=(q^3-1)(q^3+1)\Leftrightarrow p|(q^2+q+1)(q^2-q+1)$($p\neq q+1$, т.к. иначе $0>(q+1)^3-q^7=1$ - противоречие). Поэтому, либо $p|q^2-q+1$, либо $p|q^2+q+1$. Пусть $q^2\pm q+1=kp$. Рассмотрим два случая:

1) $q|p+1$, тогда $1\equiv q^2\pm q +1=kp\Rightarrow k\equiv -1\pmod q\Rightarrow k\ge q-1$. Если $k\ge2q-1\Rightarrow p=\frac{q^2\pm q+1}{k}<\frac{(q+1)^2}{2q-1}<q+1$ - противоречие. Если $k=q-1\Rightarrow q-1|q^2\pm q+1\equiv1,3$, поэтому $q=2,4$, оба варианта не подходят.

2) $q|p-1\Rightarrow k\equiv kp=q^2\pm q+1\equiv1\pmod q$.

При $k\ge q+1: p=\frac{q^2\pm q+1}{k}<\frac{(q+1)^2}{q+1}=q+1$ - противоречие. Поэтому $k=1$.

2.1) $p=q^2-q+1\Rightarrow q^7-q=(q^2-q+1)^3-q-(q^2-2q+1)<q^7-q$ - противоречие.

2.2) $p=q^2+q+1\Rightarrow (q^2+q)(q^2+q+1)(q^2+q+2)=q(q^3-1)(q^3+1)\Leftrightarrow q^2+q+2=(q-1)(q^2-q+1)$, взяв $\pmod q$ получаем, что $q=3, p=13$.