p|x^2+1

[rightways]

Что-то скучно стало...

Задача:

Не используя малую теорему Ферма и квадратичные законы вычетов докажите, что если натуральное $n=3(mod 4)$ тогда $x^2+1$ не делится на $n$ для целых $x$.


После вашего доказательства я еще затрону одну задачу на этот метод.

[nnosipov]

У $n \equiv 3 \pmod{4}$ найдется простой делитель $p \equiv 3 \pmod{4}$. На него число вида $x^2+1$ делиться не может, поскольку любой простой делитель суммы двух квадратов сам является суммой двух квадратов (Эйлер; при доказательстве, насколько помню, не используется малая теорема Ферма). Но равенство $p=a^2+b^2$ невозможно по модулю $4$.

[rightways]

Чтото длинное решение тогда будет. Решение которое я знаю очень короткое.

[Slav-27]

Мы хотим доказать, что $-1$ не является квадратом по модулю $n$. Если бы оно было квадратом по модулю $n$, то было бы и по модулю $p$, где $p$ -- любой простой делитель. Это значит, что в мультипликативной группе поля из $p$ элементов был бы элемент порядка $4$. Эта группа -- циклическая порядка $p-1$, поэтому наличие элемента порядка 4 влечёт $p-1\;\vdots\; 4$. То есть все простые делители $n$ дают остаток $1$ при делении на $4$, значит, $n$ тоже.

[nnosipov]

Как я понял, ТС запретил пользоваться даже малой теоремой Ферма (и тем более, я подозреваю, теоремой Лагранжа и ее следствиями). А утверждение о цикличности мультипликативной группы конечного поля на порядок сложнее самой задачи.

Видимо, речь идет о каком-то экзотическом рассуждении.

[xagiwo]

Можно считать, что $0 < x < n$, т.к. можно вместо $x$ взять $x \mod n$. И можно считать, что $x \vdots 2$, иначе вместо $x$ возьмём $n-x$.
Дальше спуском, поскольку $x^2 + 1 \equiv_4 1$, то $\frac{x^2 + 1}n < n$ и имеет вид $4k+3$, и $x^2 + 1$ делится также и на него.

[rightways]

xagiwo в сообщении #1509985 писал(а):

Можно считать, что $0 < x < n$, т.к. можно вместо $x$ взять $x \mod n$. И можно считать, что $x \vdots 2$, иначе вместо $x$ возьмём $n-x$.
Дальше спуском, поскольку $x^2 + 1 \equiv_4 1$, то $\frac{x^2 + 1}n < n$ и имеет вид $4k+3$, и $x^2 + 1$ делится также и на него.

Да, именно это решение я имел в виду. Спасибо.
По моему этот метод доказательства самый красивый.

[rightways]

У меня возник следующий вопрос, можно ли этим же методом спуска, желательно без символов Якоби, доказать следующее обобщение:

Число $x^2+n$ не делится на натуральное число $m$, где $m\equiv -1 \pmod {4n}$

[nnosipov]

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

Да, именно это решение я имел в виду.

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

[rightways]

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

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

[xagiwo]

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

Автор : Keith Conrad
Proofs by descent

По первой ссылке из гугла https://kconrad.math.uconn.edu/ross2007/descent.pdf этого нет.

[rightways]

Странно, у меня есть, и там побольше страниц

Нужно написать в гугл так:
keith conrad proofs by descent

[xagiwo]

rightways
Может, дадите ссылку? Я нашёл только доказательство того, что если простое $p \, |\, x^2+1$, то $p$ – сумма двух квадратов.

[rightways]

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

У меня возник следующий вопрос, можно ли этим же методом спуска, желательно без символов Якоби, доказать следующее обобщение:

Число $x^2+n$ не делится на натуральное число $m$, где $m\equiv -1 \pmod {4n}$

У кого нибудь получилось?

[nnosipov]

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

У кого нибудь получилось?

Я не думал, так как сам вопрос мне не кажется интересным. Лучше я подумаю вот над этим сюжетом topic145331.html, который мне кажется весьма симпатичным.