Тест простоты

[Gts]

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

Цитата:

Как узнать, будет ли $ N $ простое или составное число? Способ состоит в следующем: найдя предварительно $\sqrt{N}$, выписывают все простые числа, меньшие этого корня. Если $ N $ не разделить ни на одно из этих чисел, то можно утверждать, не производя дальнейших делений, что $ N $ - число простое. Действительно, так как $ N = \sqrt{N} \cdot \sqrt{N}$, то очевидно, что от деления $ N $ на числа, большие $\sqrt{N}$, должны получаться частные, меньше $\sqrt{N}$; поэтому если бы число $N$ могло могло разделиться на какое-нибудь число, большее $\sqrt{N}$, то оно разделилось бы и на число меньшее $\sqrt{N}$.

Почему применяется именно квадратный корень? Почему ни один из делителей не превосходит $ \sqrt{N} $, каким образом это определили?

Например, с корнем 4-степени такой номер уже не проходит:
$1331 = 11^3$
$\sqrt[4]{1331} \approx 6 $
Ряд простых чисел, меньше 6: 2, 3, 5. И сюда не входит 11, на которое делится 1331.


И я не могу понять как слова

Цитата:

Если бы число $N$ могло могло разделиться на какое-нибудь число, большее $\sqrt{N}$, то оно разделилось бы и на число меньшее $\sqrt{N}$

объясняют суть метода.

Пожалуйста, помогите разобраться.

[Cash]

Очень просто.
Пусть $N$ - составное.
Значит $N=d_1d_2$, где $d_1 \leqslant d_2$
Найдите отсюда оценку сверху для $d_1$

[ИСН]

"Неудачная метафора подобна котенку с дверцей." То же самое касается и просто употребления слов. Вы, Gts, почему говорите

Gts в сообщении #823075 писал(а):

Почему ни один из делителей не превосходит $ \sqrt{N} $

когда вот же, например, число 8 и его делитель 4 (превосходит $ \sqrt N$)? Вы что имели в виду на самом деле?

[Gts]

Цитата:

Очень просто.
Пусть $N$ - составное.
Значит $N=d_1d_2$, где $d_1 \leqslant d_2$
Найдите отсюда оценку сверху для $d_1$

Я учился в ВУЗе, там нам что-то про лимиты рассказывали. Оценка сверху это предел?
Просто я читаю учебник по арифметике и хотелось разобраться в материале используя только арифметику. Это возможно?

Цитата:

когда вот же, например, число 8 и его делитель 4 (превосходит $ \sqrt N$)? Вы что имели в виду на самом деле?

Согласен, это я маху дал. Имелись ввиду простые делители.

[iifat]

Gts в сообщении #823280 писал(а):

Оценка сверху это предел?

Нет, оценка сверху — это неравенство $d_1\le\cdots$ Попытайтесь из двух неравенств вывести третье такого вида.

[Cash]

Gts в сообщении #823280 писал(а):

Имелись ввиду простые делители

И это не совсем удачно. Например, 10 и его простой делитель 5.

[Gts]

Цитата:

Например, 10 и его простой делитель 5.

Так ведь $\sqrt{10} \approx 3$. То есть по алгоритму мы должны рассмотреть простые делители меньше 3. Это будет 2. Из чего мы заключаем, что 10 составное число.

[ИСН]

Ну да, всё так. А вопрос-то в чём?

[Gts]

Я не могу понять доказательство этого метода.

Сейчас читаю про неравенства, чтобы понять вот эти слова.

Цитата:

Нет, оценка сверху — это неравенство $d_1\le\cdots$ Попытайтесь из двух неравенств вывести третье такого вида.

И понять где взять второе неравенство...

[ИСН]

Сформулируйте словами факт, который Вы хотите доказать (ну, или понять доказательство).

[Gts]

Цитата:

Сформулируйте словами факт, который Вы хотите доказать (ну, или понять доказательство).

Дано число $N$. Для того, чтобы определить простое ли оно, нужно взять его квадратный корень и взять ряд простых чисел меньших этого корня. И если $N$ нельзя будет разделить без остатка ни на одно число из этого ряда, число $N$ будет простым.

Вопрос: как узнали, что нужно брать квадратный корень числа? Как это можно доказать?

[nikvic]

Gts в сообщении #823333 писал(а):

Вопрос: как узнали, что нужно брать квадратный корень числа? Как это можно доказать?

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

[ИСН]

Как бы это сказать-то... Я просил факт, а Вы что говорите? "Как узнали". Узнали потому, что верно некое утверждение (возможно, неравенство), в котором как-то фигурируют какие-то делители и какой-то корень. А что за утверждение?

[Someone]

Gts в сообщении #823333 писал(а):

Дано число $N$. Для того, чтобы определить простое ли оно, нужно взять его квадратный корень и взять ряд простых чисел меньших этого корня.

Неточность. Нужно проверять простые числа $p\leqslant\sqrt{N}$.

[Gts]

ИСН, я понимаю, что Вы хотите подвести меня к ответу на мой вопрос, но просветления пока не наступило.
Попробую еще раз.
Дано $N$. Пусть $N$ составное число с делителями $d_1$ и $d_2$. $N = d_1 \cdot d_2$, причем $d_1 \leqslant d_2$. Меньший делитель будет меньше или равен квадратному корню произведения делителей. $d_1 \leqslant \sqrt{d_1 \cdot d_2}$ или $d_1^2 \leqslant d_1 \cdot d_2$
Вот этот факт я хочу понять/доказать.