Необходимое условие простоты числа

[Побережный Александр]

Уважаемые софорумники, прошу оценить мой маленький вклад в теорию простых чисел. :)
Итак, необходимое условие простоты числа.
Пусть имеется натуральное нечетное число N больше трех, которое НЕ делится на 3 (три).
Тогда, если число N-1 не делится на 4 (четыре), то число N - простое.

[12d3]

$N=35$

[gris]

существование близнецов как бы опровергает.
Но необходимый признак формулируется в виде: если число простое, то ...
А у Вас?

[Bulinator]

$N=17$

[Побережный Александр]

Спасибо за аргументы! Схема не доработана.

-- Вт янв 04, 2011 13:01:36 --
Новая редакция!
Необходимое условие простоты числа.
Пусть имеется натуральное нечетное число N больше трех, которое НЕ делится на простые вида 2^k +1.
Тогда, если число N-1 не делится на 4 (четыре), то число N - простое.

[Someone]

Побережный Александр в сообщении #395098 писал(а):

Пусть имеется натуральное нечетное число N больше трех, которое НЕ делится на простые вида 2^k +1.
Тогда, если число N-1 не делится на 4 (четыре), то число N - простое.

Простых чисел вида $2^k+1$ известно очень мало: для $k=0,1,2,4,8,16$, то есть, $2,3,5,17,257,65537$.
Контрпримером к Вашему утверждению служит, например, $N=91=7\cdot 13$, $N-1=90=2\cdot 3^2\cdot 5$. Это число не настолько велико, чтобы Вы не могли найти его самостоятельно.

Нечётные числа $N$, для которых $N-1$ не делится на $4$, имеют вид $N=4k+3$.

Побережный Александр в сообщении #395098 писал(а):

Необходимое условие простоты числа ... если ..., то число N - простое.

Вам уже писали, что Вы употребляете неправильный термин. То, что Вы пытаетесь сформулировать, называется достаточным условием.

[Побережный Александр]

Спасибо за конструктивную критику. Со всеми замечаниями полностью согласен.
Можно ли утверждать следующее?

Пусть имеется натуральное нечетное число N больше трех, которое НЕ делится на простые вида 2^k +1.
Тогда, если число N-1 не делится на 4 (четыре), то число N либо простое число, либо составное, один из делителей которого является простым числом Софи Жермен.

[12d3]

$N=91=7\cdot 13$
Просто выдумывать различные утверждения, авось окажется правильным - слегка некоструктивно.

[Побережный Александр]

Но ведь 7 - число Софи Жермен!

[gris]

с утра осенило. Если число $N$ не делится на простые числа $p$, удовлетворяющие условию $2\ln p\leqslant \ln N$, то $N$ — простое.

[Побережный Александр]

Прошу прощения, неправильно трактовал простые числа Софи Жермен.

[hurtsy]

12d3 в сообщении #395526 писал(а):

$N=91=7\cdot 13$
Просто выдумывать различные утверждения, авось окажется правильным - слегка некоструктивно.

Что да то да. Но все же, Побережный Александр, в чем разница Вашей необходимости и достаточности, о которой говорят gris и Someone? С уважением,

[Побережный Александр]

Хочу объяснить логику моих рассуждений.
Пусть есть составное числоN=P*Q=(2*p+1)(2*q+1)=4pq+2(p+q)+1.
Я зацепился за случай, когда p,q-нечетные, соответственно N-1 обязано делится на 4.
И сделал вывод, что для нечетных p,q, если N-1 не делится на 4, то число N-простое.
Но p,q могут быть разной четности или оба одновременно быть четными.
ТогдаN=P*Q=(p*2^k+1)(q*2^m+1), где p,q также нечетные.
Так как простых вида(2^k+1) мало, то я их исключаю из рассмотрения и соответственно p,q не равны единице.
N=P*Q=(p*2^k+1)(q*2^m+1)=pq*2^(k+m)+(p*2^k+q*2^m)+1
За скобки выносим минимальную степень и получаем
N=P*Q=(p*2^k+1)(q*2^m+1)=pq*2^(k+m)+2^k(p+q*2^(m-k))+1=2^k*(pq*2^m+(p+q*2^(m-k)))+1
А так как не учел, что k может равнятся единице, сделал поспешный вывод о делимости на 4 составного N-1.
Все контраргументы были именно с k=1.
Хотелось бы услышать конструктивные замечания по поводу моих рассуждений.

[Someone]

Побережный Александр в сообщении #396192 писал(а):

Пусть есть составное число N=P*Q=(2*p+1)(2*q+1)=4pq+2(p+q)+1.
Я зацепился за случай, когда p,q-нечетные, соответственно N-1 обязано делится на 4.
И сделал вывод, что для нечетных p,q, если N-1 не делится на 4, то число N-простое.

Согласно Вашим же рассуждениям, случай, когда $p$ и $q$ оба нечётные, а $N-1$ не делится на $4$, невозможен. Поэтому рассуждать об этом случае совершенно бессмысленно.

Побережный Александр в сообщении #396192 писал(а):

Все контраргументы были именно с k=1.

Вы сами этого потребовали, когда написали, что $N-1$ не делится на $4$, так что и удивляться нечего.

P.S. Согласно правилам форума,
1) формулы следует окружать знаками доллара: $N=PQ=(2p+1)(2q+1)=4pq+2(p+q)+1$;
2) нельзя использовать "*" в качестве знака умножения; если знак умножения позарез нужен, используется либо точка посередине строки "$\cdot$" (код \cdot), либо косой крест "$\times$" (код \times; обычно его пишут при переносе части формулы на другую строку).
При соблюдении этих правил процитированная формула будет выглядеть так: $N=PQ=(2p+1)(2q+1)=4pq+2(p+q)+1$.
Чтобы показатель степени в выражении $2^(k+m)$ изображался правильно, его нужно окружать не круглыми скобками, а фигурными: 2^{k+m}; получится $2^{k+m}$.
Подробнее можно прочесть в темах http://dxdy.ru/topic8355.html и http://dxdy.ru/topic183.html. Увидеть код формулы в чужом сообщении можно, если навести на него курсор мыши.