Школьная задача по простым числам

Irbis-S

Подскажите плз общую идею решения без деталей, дальше сам разберусь.
Никак что-то не пойму как сделать.
Доказать что простых чисел вида 3k+2 бесконечное число

stm7886047

Метод "от противного" и модулярная арифметика по модулю 3

Irbis-S

можно чуть поподробнее, где искать противоречие ?

stm7886047



поподробнее
Исходя из предположения "от противного" сконструировать число, которое ни на одно простое делиться не может. Примерно так же, как доказывается, что простых чисел бесконечно много.

Irbis-S

да, я тоже до этого дошел, но застрял на конструкции примера такого числа
подскажите плз общую идею такой конструкции

stm7886047

Перемножить все простые вида 3k+2. Если их чётное количество, то домножить на одно из них, скажем, на 2.

Irbis-S

в результате должно получится по идее простое число такого же типа, только еще большее.
в этом вроде бы противоречие ?
или в другом ?

stm7886047



е должно получится по идее простое число такого же типа, только еще большее.
в этом вроде бы противоречие ?
или в другом ?
Да, в этом.
Число придумалось?

Irbis-S

никак не могу придумать.
подскажите плз, если знаете

Irbis-S

я думал взять произведение всех простых до максимального такого + какое-то число.
но как доказать, что оно будет такого же типа ?
никак что-то не соображу.
подскажите плз

Irbis-S

произведение всех таких чисел даст 3n+2^p.
как из этого числа можно получить простое число вида 3к+2 ?

griz_a

О, май гад.
Пусть простых чисел вида 3n+2 конечное число.
а) Их четное число. Тогда если их перемножить и прибавить 1, то будет число, дающее остаток 2 при делении на 3 и оно взаимнопросто со всеми предыдущими. Значит оно есть произведение чисел вида 3n+1, но тогда у него остаток был бы 1.
б) Их нечетное число
Перемножим их и умножим на 5, а потом прибавим 1. Далее аналогично

Irbis-S

все, придумал
спасибо за подсказки

incwizitor

все простые числа, большие 3, имеют вид 6k + 1 или 6k - 1
простые числа вида 3n + 2 больше 3, поэтому исходную задачу можно переформулировать так:
доказать, что простых чисел вида 6k - 1 бесконечное количество
доказательство:
допустим, что их конечное кол-во, тогда существует максимальное 6m - 1 (не забываем показать, что такие числа вообще есть: 5, 11, 17)
рассмотрим произведение всех простых чисел, не превосходящих 6m - 1:
2*3*5*7*11*13*17...*(6m - 1) - 1 = 6z - 1
полученное число :
а) простое -> но это не может быть, ибо z > m, противоречит максимальности m
б) составное -> можно представить в виде произведения простых.
среди них нет 2 и 3, т.к. остаток от деления на них равен (-1)
среди них нет ни одного вида 6k - 1, т.к. деление на каждое из них дает остаток (-1 значит 6z - 1 = произведение нескольких простых чисел вида 6k + 1
но произведение (6k+1) * (6l + 1) = 6y + 1. сколько не умножай, а 6z - 1 не получишь
значит, наше допущение о конечности простых чисел вида 6k - 1 неверно
Оставить комментарий
Имя или ник:
Комментарий: