Представление простых чисел

[xmaister]

Какие нечётные простые числа можно записать в виде $m^2+16n^2$? А в виде $4m^2+4mn+5n^2$, где $m,n$ могут быть отрицательные?

(Источник)

Putnam 1974A3, хотелось бы узнать решения, отличные от авторского

[Sonic86]

xmaister в сообщении #494882 писал(а):

Какие нечётные простые числа можно записать в виде $m^2+16n^2$?

Любое простое число $p:p \equiv 1 \pmod 4$ представимо в виде $m^2+k^2$. Если $p \neq 2$, то хотя бы один из квадратов четный, а значит любое $p:p>2,p \equiv 1 \pmod 4$ представимо в виде $m^2+4k^2$ с нечетным $m$. Далее, разбиение $k$ на классы по модулю 2: $k=2n$ либо $k=2n+1$ порождает разбиение множества простых вида $m^2+4k^2$ на 2 класса, сравнимых с $1$ либо с $5$ по модулю $8$. Значит формой $m^2+16n^2$ представимы все простые $p:p \equiv 1 \pmod 8$.

-- Пт окт 21, 2011 18:14:30 --

xmaister в сообщении #494882 писал(а):

А в виде $4m^2+4mn+5n^2$, где $m,n$ могут быть отрицательные?

$4m^2+4mn+5n^2=(2m+n)^2+(2n)^2$. Поскольку $n$ нечетное, то $2m+n=t$ - нечетно и получаем 2-й вариант формы $m^2+4n^2$, описанный выше (только у нас вместо $m$ буква $t$)- простые $p:p \equiv 5 \pmod 8$.

[xmaister]

Sonic86 в сообщении #494891 писал(а):

Любое простое число $p:p \equiv 1 \pmod 4$ представимо в виде $m^2+k^2$

Это откуда?

[Хорхе]

Оттуда (с)

Есть даже критерий, когда число представимо в виде суммы двух квадратов. Читайте тут, обстоятельно и доходчиво написано.