Азиатско-Тихоокеанская математическая олимпиада, 1994 год

Найдите все натуральные $n$, которые можно представить в виде суммы квадратов двух взаимно простых чисел $(n =a^2+b^2)$, таким образом, что любое простое число $p\leq \sqrt{n}$ является делителем $ab$.

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

$(a,b)=1 \rightarrow (a^2+b^2,ab)=1$

$(n, ab)=1 \rightarrow p \nmid n$

$n \in P$

Допустим что: $a-b>1$

Берем делитель $q$ числа $a-b$

$q \leq a-b < \sqrt{n}$

$q \mid ab$

$q \mid a^2-ab$

$q \mid b^2-ab$

$q \mid a^2+b^2 \rightarrow q \mid n \rightarrow \varnothing$

$(i)a=b$

$2a^2 \in P \rightarrow a=1=b, n=2$

$(ii)a=b+1$

$b \geq 3$

$a^2+b^2 > (a+1)^2$

$r \mid a+1$

$r \in P$

$r \mid ab$

$2=(a+1,b)=(b,2)>1$

$(a,a+1)=1 \rightarrow r=2$

$q \mid b-1$

$q \in P$

$q \ne 2$

$(b+1,b-1)>2 \rightarrow \varnothing$

Из чего $b=1, a=2, n=5; b=2, a=3, n=13;$

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