простые числа вида n^2+1

[BanmaN]

Здравствуйте.

Подскажите, пожалуйста, конечно ли множество простых чисел вида $n^2 + 1$ (с доказательством, разумеется)?

Спасибо

[Cave]

Согласно онлайн энциклопедии последовательностей бесконечность множества ещё не доказана.

[maxal]

Это так называемая 4-я проблема Ландау, сформулированная им ещё в 1912 году. До сих пор нерешена.

[age]

Данная гипотеза эквивалентна следующему утверждению:
Для любого сколь угодно большого чётного числа $2k$ не найдётся ни одной четверки попарно различных чисел $a,b,c,d$ такой что справедлива система:
$\begin{cases} ab+cd=2k\\ ad-bc=1 \end{cases}$


Для сколь угодно большого числа количество его представлений видом $ab+cd$ неуклонно растёт. Таких представлений существует порядка $\dfrac k4<\varphi$. Поэтому представить, что среди них не найдётся ни одного, что $ad-bc=1$ - довольно сложно. Поэтому, скорее всего, их количество конечно.

[Руст]

age в сообщении #422309 писал(а):

Данная гипотеза эквивалентна следующему утверждению:
Для любого сколь угодно большого чётного числа $2k$ не найдётся ни одной четверки попарно различных чисел $a,b,c,d$ такой что справедлива система:
$\begin{cases} ab+cd=2k\\ ad-bc=1 \end{cases}$

Почему эквивалентно?

Цитата:

Для сколь угодно большого числа количество его представлений видом $ab+cd$ неуклонно растёт. Таких представлений существует порядка $\dfrac k4<\varphi$. Поэтому представить, что среди них не найдётся ни одного, что $ad-bc=1$ - довольно сложно. Поэтому, скорее всего, их количество конечно.

Представить легко. Вывод скорее всего гипотеза верна.

[age]

Всякое простое число $n^2+1$ есть квадратичная форма (причём $n=2k$), поэтому для него справедливо тождество: $(ac+bd)^2+(ad-bc)^2=(a^2+b^2)(c^2+d^2)=(ad+bc)^2+(ac-bd)^2$.
Если число не простое, т.е. состоит из простых делителей, то каждый из них имеет вид $a^2+b^2$, а поэтому существуют как минимум два различных представления данного числа суммой квадратов:
$\begin{cases} (ac+bd)^2+(ad-bc)^2\\ (ad+bc)^2+(ac-bd)^2 \end{cases}$
И только если число простое и не может быть разложено на простые делители, то одна сумма квадратов обязательно единица: $a^2+b^2=1$, откуда, либо $a$, либо $b$ есть $0$.
Для этого случая получаем:
$\begin{cases} ac+bd=ac-bd=a,\ b=0\\ ad+bc=ad-bc=b,\ a=0 \end{cases}$
Но т.к. не может быть, что
$\begin{cases} ac-bd=2k\\ ad+bc=1 \end{cases}$
Откуда и получаем требуемое с точностью до перестановки букв:
$\begin{cases} ab+cd=2k\\ ad-bc=1 \end{cases}$
Однако, если все числа $a,b,c,d$ попарно различны, то очевидно, что:
$\begin{cases} ac+bd\neq ac-bd\\ ad+bc\neq ad-bc \end{cases}$
т.е. число как минимум двумя различными способами может быть представлено как сумма квадратов. А это означает, что оно не простое. Противоречие.
Поэтому для попарно различных $a,b,c,d$ для простого числа не должно быть ни одного такого представления.

-- Вс мар 13, 2011 12:25:53 --

Руст в сообщении #422337 писал(а):

Представить легко. Вывод скорее всего гипотеза верна.

Одним из самых серьёзных кандидатов на то, что гипотеза верна (число бесконечно) являются простые числа Ферма. Т.к. если хоть одно из них $m>4$ окажется простым, то окажется что ни для одного разложения $2k=\sqrt{F_m-1}=ab+cd$ не найдётся ни одного $ad-bc=1$. Но все известные $F_m,\ m>4$ составные.

[Руст]

Спасибо. Только можно было проще объяснить, а именно Гауссово целое число $1+in$ разлагается на множители:
$1+in=(a+bi)(c+di)$ Соответственно
$1+n^2=(1+in)(1-in)=(a+bi)(c+di)(a-bi)(c-di)=(a+bi)(c-di)(a-bi)(c+di)$.
Произведение первых двух является комплексно сопряженным произведению двух последних, т.е. по крайней мере два представления в виде суммы квадратов натуральных чисел.

age в сообщении #422347 писал(а):

Одним из самых серьёзных кандидатов на то, что гипотеза верна (число бесконечно) являются простые числа Ферма. Т.к. если хоть одно из них $m>4$ окажется простым, то окажется что ни для одного разложения $2k=\sqrt{F_m-1}=ab+cd$ не найдётся ни одного $ad-bc=1$. Но все известные $F_m,\ m>4$ составные.

Я тут ничего не понял. Ясно, что $F_m=1+2^{2^m}=1+(2^{2^m-1}})^2=1+(F_{m-1})^2$. Поэтому из бесконечности простых чисел Ферма следует справедливость гипотезы. Однако, их та скорее всего конечное число. Только каким образом из того, что простых чисел Ферма не пять, а 6 следует справедливость гипотезы Ландау?

[age]

Руст в сообщении #422446 писал(а):

Ясно, что $F_m=1+2^{2^m}=1+(2^{2^m-1}})^2=1+(F_{m-1})^2$.

Т.к. $2^m$ уже само по себе число чётное, то достаточно $F_m=1+2^{2k}=1+(2^k)^2=1+n^2$.

Руст в сообщении #422446 писал(а):

Только каким образом из того, что простых чисел Ферма не пять, а 6 следует справедливость гипотезы Ландау?

Никоим. Просто если их бесконечность - то следует.

[Батороев]

Рассмотрим последовательный ряд четных чисел $n$.
Квадраты этих чисел имеют остаток $(-1)$ только по основанию простых чисел $p\equiv 1\pmod 4$. Для каждого из этих простых на интервале от $1$ до $p$ остаток $(-1)$ имеет всего лишь квадрат одного четного числа.
Таким образом, для каждого простого $p\equiv 1\pmod 4$ количество четных чисел, квадраты которых не имеют остаток $(-1)\pmod p$, равно $\dfrac {(p-1)}{2}$. Попутно отметим, что двух подряд идущих четных чисел, имеющих остаток $n^2\equiv (-1)\pmod p$, не существует.

Отсюда очевидно, что для доказательства бесконечности простых вида $p=n^2+1$ можно применить алгоритм доказательства Эвклида для всех простых, но с незначительными изменениями:

Пусть число указанных простых конечно. Тогда существует некоторое четное число $N$, удовлетворяющее сравнению: $N^2\equiv (-1)\pmod {p_i}$, где $p_i\equiv 1\pmod 4$ - любое простое из конечного ряда. В этом случае следующее число $(N+2)^2+1$ не делится ни на одно простое число $p_i$. Следовательно, это число - простое, но превышающее любое $p_i$. Противоречие.

[Руст]

Батороев в сообщении #422749 писал(а):

Пусть число указанных простых конечно. Тогда существует некоторое четное число $N$, удовлетворяющее сравнению: $N^2\equiv (-1)\pmod {p_i}$, где $p_i\equiv 1\pmod 4$ - любое простое из конечного ряда. В этом случае следующее число $(N+2)^2+1$ не делится ни на одно простое число $p_i$. Следовательно, это число - простое, но превышающее любое $p_i$. Противоречие.

Ничего не следует. Так можно доказать только бесконечность простых вида $p=1+4k$.
Например число $13\not =1+n^2$ ни при каком $n$, но $13|8^2+1$.

[Батороев]

Руст в сообщении #422764 писал(а):

Ничего не следует. Так можно доказать только бесконечность простых вида $p=1+4k$.
Например число $13\not =1+n^2$ ни при каком $n$, но $13|8^2+1$.

Ну, что ж самостоятельное доказательство бесконечности простых вида $p=1+4k$. Тоже неплохо для одного дня!

Согласен с Вами, что число $(N+2)^2+1$ может быть и не простым, а может состоять из простых чисел $p=1+4k$. Меня самого простота "собственного доказательства", откровенно говоря, смущала.

[Sonic86]

(Оффтоп)

Батороев, искренне желаю удачи, вот только боюсь, что алгоритм Евклида там не прокатит. И формула включений-исключений тоже, если что (это чтоб Вы зря не мучились).

[Руст]

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

Батороев, искренне желаю удачи, вот только боюсь, что алгоритм Евклида там не прокатит. И формула включений-исключений тоже, если что (это чтоб Вы зря не мучились).

Алгоритм Евклида проходит. Если $p_1,...,p_k$ все простые вида $4k+1$, то достаточно взять $N=4(p_1...p_k)^2+1$. Простое число вида $p=3\mod 4$не может делить это число, а все вида $ p=1\mod 4$ так же не может - противоречие.

[Sonic86]

Руст писал(а):

Алгоритм Евклида проходит. Если $p_1,...,p_k$ все простые вида $4k+1$, то достаточно взять $N=4(p_1...p_k)^2+1$. Простое число вида $p=3\mod 4$не может делить это число, а все вида $ p=1\mod 4$ так же не может - противоречие.

Ааа! Вы про $4k+1$? Тогда я извиняюсь, я думал про $n^2+1$...
Я вот про это:

Батороев писал(а):

Отсюда очевидно, что для доказательства бесконечности простых вида $p=n^2+1$ можно применить алгоритм доказательства Эвклида для всех простых, но с незначительными изменениями:

[yk2ru]

Если число делит сумму двух квадратов, то оно само сумма двух квадратов. Пример выше с числом $13$.