III математическая олимпиада «Шелковый путь», 2004 год


Найдите все простые числа $p$, для которых существуют целые числа $m$ и $n$, удовлетворяющие условиям $p = m^2 + n^2$ и $p\ |\ m^3 + n^3 - 4$.
посмотреть в олимпиаде

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

пред. Правка 3   0
2020-07-27 17:33:15.0 #

Ответ: $p=2,5,13$

Для $p=2$ подходит $m=n=1$

Далее $p>2$, очевидно, что $m,n\ne 0$, $(m,n)=(m,p)=(n,p)=1$

Заметим, что $ m^3+n^3-4\equiv -n^2*m-m^2*n-4=-mn(m+n)-4\pmod{p}$

значит $$p\mid mn(m+n)+4\mid (mn(m+n))^2-4^2\quad(\color{red}1)$$

Тогда $0\equiv (mn)^2(m+n)^2-16\equiv 2(mn)^3-16=2((mn)^3-8)=$

$=2(mn-2)((mn)^2+2mn+4)\pmod p$

$1)$ случай : $p\mid mn-2$, но $p=m^2+n^2\ge 2|mn|$,

откуда либо $mn-2=0$, либо $2|mn|\le m^2+n^2\le |mn-2|$.

Если $mn=2$, то $p=5$, для которого подходит $m=2, n=1$

Если $2|mn|\le | mn-2|$, то $|mn|+2\ge |mn-2|\ge 2|mn|$,

или $2\ge |mn|\implies |mn|=1,2\implies p=2,5\implies p=5$

$2)$ случай : $p\mid (mn)^2+2mn+4$

Тогда $p\mid [(mn)^2+2mn+4]-[mn(m+n)+4]=mn(mn+2-m-n)$,

но потому как $(mn,p)=1$, то $$p\mid mn-m-n+2\quad(\color{red}2)$$

Откуда

$2|mn|\le m^2+n^2=p\le |mn-m-n+2|\le | mn|+|m|+|n|+2$

или $0\le (|m|-1)(|n|-1)\le 3$,

пусть $a=|m|, b=|n|$, тогда $(a-1)(b-1)=0,1,2,3$

$\mathrm i)$ $(a-1)(b-1)=1,3\implies 2\mid a,b,$ что невозможно

$\mathrm {ii})$ $(a-1)(b-1)=2\implies p=a^2+b^2=2^2+3^2=13$,

для $p=13$ подходит $m=-2,n=-3$

$\mathrm {iii})$ $(a-1)(b-1)=0$, БОО пусть $b=1$,

тогда $n=1,-1$

1] $n=1\implies m^2+1=p\mid m(m+1)+4\implies m^2+1\mid m+3$

$\implies 2|m|\le m^2+1\le |m+3|\le |m|+3\implies |m|\le 3\implies p=5$

2] $n=-1\implies m^2+1=p\mid -m(m-1)+4\implies m^2+1\mid -m+5$

$\implies 2|m|\le m^2+1\le |-m+5|\le |m|+5\implies |m|\le 5\implies$

$\implies p=5,17,$

но для $p=17$ не сущ. $m,n$ удовлетворяющие условиям задачи

(легко убедиться перебором)