Множество простых вида 4n-1

[C0rWin]

Задача: Нужно доказать что множество _простых_ чисел вида 4*n-1 является бесконечным.

[maxal]

Аналогично доказательству Евклида.
Пусть их конечное число: $q_1, ..., q_k$.

Рассмотри число $4 q_1 \dots q_k - 1$. Это число имеет вид 4n-1, а поэтому должно иметь как минимум один простой делитель такого же вида. Но оно не делится ни на одно из $q_1, ..., q_k$. Противоречие.

[Руст]

Этот приём работает и для простых вида 3n-1. Однако для простых вида 4n+1 или 3n+1 требуется немного модернизировать. Вопрос как?

[bot]

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

Однако для простых вида 4n+1 или 3n+1 требуется немного модернизировать. Вопрос как?

Проще всего через символ Лежандра.

[Руст]

Можно школьными методами.

[bot]

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

Можно школьными методами.

Кажется где-то даже видел, но длинновато. По сути это была просто адаптация, устраняющая символ Лежандра.
Для доказательства простых вида $4k \pm 1$ Эйлер рассматривал ряды с членами, обратными простым числам каждого из двух указанным видов. Их расходимость и указывала на бесконечность нужного множества.

[Руст]

Вообщем я имел в виду рассмотрение простого делителя:
$r^2+1,r=2p_1*\dots *p_k, q^2+q+1,q=3p_1*\dots *p_k$,
соответственно для случая 4n+1 и 3n+1.

[bot]

Я тоже.
Чтобы установить случаи разрешимости сравнений
$x^2+1\equiv 0 (mod p)$ и $x^2+1\equiv 0 (mod p)$ проще всего воспользоваться символом Лежандра.
ЗЫ. Вместо 3n+1 лучше уж сразу 6n+1

[C0rWin]

Из всего вышесказанного я если честно ничего не понял... Так как я слабо вижу связь между сказанным и доказательством того, что есть бесконечное множество ПРОСТЫХ (именно простых) чисел вида 4*n-1. Если можно, то обратите к нужной теореме или к ссылке на книгу или если можно просто строго по пунктам, из чего нужно исходить и к чему следует придти.

[juna]

Предлагаю такое школьное решение.
1.Заметим, что числа вида 4n-1 и 4n+3 сравнимы по модулю 4, т.е. задают одинаковую последовательность только со сдвигом. Значит достаточно доказать, что простых 4n+3 бесконечно.
2. Любое простое число представимо в виде 4n+1 или 4n+3 или является 2. Мы знаем, что простых чисел бесконечно много. Предположим, что простых 4n+3 – конечное число, значит простых 4n+1 – бесконечно.
3. Легко видеть, что произведение любого нечетного количества простых вида 4n+3 снова дает число вида 4n+3, а четного количества дает число вида 4n+1. Произведение числа вида 4n+1 на число 4n+3 дает 4n+3, а на 4n+1 дает 4n+1.
4. Заметим, что для любого n числа вида 4n+3 и 4(n+1)+3 =4n+7 взаимнопросты.
5. Из сказанного следует, что любое составное вида 4n+3 должно содержать в своем разложении нечетное количество простых вида 4n+3, ну или как минимум одно такое число, т.е. существует как минимум одно простое число вида 4n1+3. Тогда согласно п.4 числа 4n1+3 и 4(n1+1)+3 – взаимнопросты. Значит существует как минимум еще одно простое число вида 4n2+3. Согласно п.3 произведение нечетного количества чисел 4n1+3 и 4n2+3 снова даст число такого же вида – пусть это 4a+3=(4n1+3)(4n1+3)(4n2+3). Согласно п.4 числа 4a+3 и 4(a+1)+3 взаимнопросты, значит существует еще одно простое 4n3+3. Это рассуждение можно продолжить до бесконечности, что указывает на бесконечность простых вида 4n+3, а значит и 4n-1.
Используя указанный алгоритм, можно доказать также бесконечность количества простых вида 3n+2, 6n+5.
Самый общий результат в этом направлении - это теорема Дирихле - для любого n простых чисел вида na+b – бесконечно много, если a, b – взаимнопросты. Но здесь доказательство уже нетривиально.

[C0rWin]

А можно ли пояснить выражение "п.3 лекго видеть"? А то увидеть то я увидел, а вот как формально доказать?

[juna]

Если доказать формально, то так – если ${k}\equiv {1} mod 2$, то ${3^k}\equiv{3}mod 4$, если ${k}\equiv {0} mod 2$, то ${3^k}\equiv{1}mod 4$

[C0rWin]

Весьма признателен за лекбез.

[C0rWin]

Кстати, а как доказывается сама малая теорема Ферма? Или где об этом почитать...

[Amigo]

Цитата:

Из всего вышесказанного я если честно ничего не понял... Так как я слабо вижу связь между сказанным и доказательством того, что есть бесконечное множество ПРОСТЫХ (именно простых) чисел вида 4*n-1. Если можно, то обратите к нужной теореме или к ссылке на книгу или если можно просто строго по пунктам, из чего нужно исходить и к чему следует придти.

Утверждение:Простых чисел вида 4*n-1-бесконечно.
Мало того: Между любым простым числом вида 4*n-1 и числом
A=4*(2*3*..*p(4*n-1))+d, (где d={0,1,..} а перед числом
4*n-1 выписанны произведения всех простых чисел
меньших 4*n-1), cуществует хотябы одно простое число тогоже
вида.

Доказательство
Предположим количество простых чисел вида 4*n-1 -конечно.
Тогда существует наибольшее простое число указанного вида
т.е 4*n1-1 , где n1 из N. Рассмотрим последовательность
всех простых чисел p1,p2,..,pl где Pi<4*n1-1.
Сформируем число A=4*p1*p2*..*pl(4*n1-1)-1.Если это число
простое то теорема доказанна.Пусть это число не простое,тогда
- это число не может делится ни на одно из чисел p1,p2,..,pl,4*n1-1
т.к первое слагаемое
в правой части на это число делится, а второе еденица-нет.
Предположим однако,что число А делится на некоторое ПРОСТОЕ число
4*n1-1<K1<A(оно может конечно делится и на составое но лишь
в том случае если это число не имеет общих множителей с
числами p1,p2,..,pl,(4*n1-1) )
, тогда имеем A=K1*K ,где K1 и K не имеют общих
множителей с числом,b=p1*p2*..*pl(4*n1-1) и K>4*n1-1.
Положим
K=k2*K3*..Kr (где K2,...,Kr ПРОСТЫЕ числа, большие 4*n1-1 и входят в разложение
числа K в ПЕРВОЙ степени т.е среди чисел K2,...,Kr возможно существование одинаковых)
тогда:
K1=4*n1-1+C1
K2=4*n1-1+C2
........
Kr=4*n1-1+Cr

,где C1,C2,..,Cr>1(числа C1,C2,..,Cr обязанны быть чётными т.к
в противом случае числа K1,K также были бы чётными, что приводит
к противоречию с отсутствием общих множителий с числом b)
Тогда

4*b-1=K1*K2*..*Kr
4*b=1+(4*n1-1+C1)*(4*n1-1+C2)*..*(4*n1-1+Cr)
4*b=(4*n1-1)*(4*n1-1)*..*(4*n1-1) + A1*(4*n1-1)*..*(4*n1-1)+..+C1*C2*..*Cr+1
4*b=(4*n1)^r+..+(-1)^r+ A1*(4*n1-1)*..*(4*n1-1)+..+C1*C2*..*Cr+1

Взависимости от чётности числа r получим 2-а различных выражения:
а)4*b=(4*n1)^r+..+4*n1+ A1*(4*n1-1)*..*(4*n1-1)+..+C1*C2*..*Cr(если r-нечётно)
б)4*b=(4*n1)^r+..+(-1*4*n1)+ A1*(4*n1-1)*..*(4*n1-1)+..+C1*C2*..*Cr+2 (если r-чётно)
Заметим, что все коэффициенты Ai-могут быть найденны из теоремы Виетта.
для первого из них емеем:A1=C1+C2+..+Cr,что же касается остальных
то нам важно лишь то , что все они делятся на 4(ибо их отдельные слагаемые состоят
из произведений 2-х или более чётных чисел)
Разберём отдельно случай а) имеем:
число слева делится на 4 значит должно делится и число справа,
что возможно лишь если A1=C1+C2+..+Cr, делится на 4, если бы
не одно из чисел C1,C2,..,Cr не дилилось бы на 4 то после сокращения
на 2 мы бы получили нечётную сумму нечётных чисел (так как r-нечётно)
которая очивидно является числом нечётным ,что противоречит тому
что А1-делится на 4.Следовательно хотябы одно из чисел C1,C2,..,Cr делится на 4.
Пусть например это число с1 тогда его можно записать ввиде с1=4*m, где m из N.
подставим его в вырыжение для K1 имеем:K1=4*n1-1+4*m или K1=4*(n1+m)-1;
число K1 простое и большее 4*n1-1. В этом случае теорема доказана.
Случай б):
В этом случае если бы число A1=C1+C2+..+Cr делилось на 4
то мы получили бы противоречие ибо 2 на 4 не делится.
Запишем C1,C2,..,Cr ввиде С1=2*h1, C2=2*h2,.., Cr=2*hr имеем:
A1=C1+C2+..+Cr=2*(h1+h2+..+hr), все числа h1,h2,..,hr немогут
быть одновременно Нечётными так как сумма чётного числа(r-чётно), нечётных
чисел чётна и значит число А1 делится на 4,что невозможно.
Следовательно хотябы одно число из h1,h2,..,hr -чётно.Пусть
например это число h1, тогда h1=2*m, где m из N,следовательно
с1=4*m и K1=4*n1-1+4*m или K1=4*(n1+m)-1
число K1 имеет требуемый вид,простое и большее 4*n1-1. Значит и в этом случае
теорема доказана.