p|x^2+1

[xagiwo]

А я думал, но так ничего и не придумал :(

[mathematician123]

nnosipov в сообщении #1510208 писал(а):

Рассказал сегодня своим школьникам. Очень понравилось. Это народное творчество или есть автор?

rightways в сообщении #1510212 писал(а):

Имя Автора не знаю, я даже не помню откуда я знаю это доказательство, но я его точно где то прочитал, кажется тут:

Незнаю как отправить файл
Автор : Keith Conrad
Proofs by descent

В "Арифметических исследованиях" Гаусса этот метод применяется для классификации простых, для которых $-1, \pm 2, \pm 3, \pm 5, \pm 7$ является квадратичным вычетом или невычетом. Также Гаусс ссылается на Эйлера, Лагранжа и Ферма. Возможно, что идея спуска принадлежит кому-то из них. Затем Гаусс даёт первое доказательство квадратичного закона взаимности - доказательство по индукции. Его рассуждение использует те же методы, которые были использованы при анализе частных случаев, но содержит разбор большого количества случаев, а также опирается на такое вспомогательное утверждение: для любого простого $a \equiv 1 \pmod{4}$ найдётся простое $p < a$, такое что $a$ есть квадратичный невычет по модулю $p$.

Недавно я заметил, что некоторые частные случаи закона взаимности могут быть доказаны с помощью уравнения Пелля. Пусть $p \equiv q \equiv 3 \pmod{4}$ - простые числа. Пусть $x_0^2 - pqy_0^2 = 1$, причём $x_0, y_0$ минимально возможные. Рассмотрением по модулю 4 получаем $2 \mid y_0$.

$$\frac{x_0 - 1}{2}\frac{x_0 + 1}{2} = pq\left(\frac{y_0}{2}\right)^2$$

Числа $\frac{x_0 - 1}{2}$ и $\frac{x_0 + 1}{2}$ взаимнопросты и равны $u^2, pqv^2$ либо $pu^2, qv^2$. В первом случае $u^2 - pqv^2 = \pm 1$, что невозможно. Во втором случае $pu^2 - qv^2 = \pm 1$. Рассматривая это равенство по модулям $p$ и $q$, получаем $(\frac{p}{q})(\frac{q}{p}) = -1$.
Похожими рассуждениями можно разобрать случай, когда $p \equiv 5 \pmod{8}$ и $q \equiv 3 \pmod{4}$. Вполне ожидаемо, если одно из чисел $p, q$ даёт остаток 1 при делении на 8, возникают трудности. Может быть, этот случай можно разобрать с помощью упомянутого выше вспомогательного утверждения Гаусса.