простые-числа - Как доказать делимость?

Докажите, что если четырехзначное число не делится на на одно простое число 2 до 97, то -простое.
Докажите, что каждое составное число имеет простой делитель такой, что

делимость составное простые-числа

задан 26 Апр '14 14:57

ambosia_a
365●1●17
100% принятых

EdwardTurJ
50●12●94●191

Во втором пункте явная опечатка.

(26 Апр '14 15:29) falcao

2 ответа

1) Есть такая теорема, что если число $%\ n \ \ \ (n>1)$% не делится ни на одного простое число, не превосходящее число $%\sqrt n ,$% то оно простое.

Так-как число $%P $% четырехзначное, то $%\sqrt p <100.$% Поэтому достаточно проверить, делится число на простые числа от $%2$% до $% 97.$%

2) Самое маленькое простое число- $%\ \ 2 (2^2>2)$%. Не существует простое число $%p$% такое, чтобы $%p^2\le2.$%

ссылка

отвечен 26 Апр '14 16:07

ASailyan
15.7k●1●11●32

$%999< p<10000$%. Если предположить, что $%p$% делится на 98 или 99, то $%p$% делится на 2 или 3 соответственно, чего быть не может по условию. Если у числа есть делитель, отличный от $%p$% и $%1$%, то он не меньше 100. То есть $%p=xy$%, где $%x\geqslant 100$%, $%y\geqslant 100$%. Тогда $%p\geqslant 10000$%, что невозможно. Поэтому $%p$% простое по определению.
Покажем, что каждое составное число $%a$% имеет простой делитель, такой, что $%p^2\leqslant a$%. Пусть $%p$% - самое маленькое простое число, на которое делится $%a$%. Тогда $%a=px$%. Если $%p^2>a$%, то из $%p=a/x$% и предположении о натуральности чисел следует, что $%x^2<a$%, но тогда $%x<p$%. По выбору $%p$% получаем, что $%x=1$% и $%a=p$% - простое число. Полученное противоречие доказывает, что выбранное $%p$% удовлетворяет нужному условию.

ссылка

отвечен 26 Апр '14 15:40

cartesius
9.8k●2●12

Ваш ответ

Если вы не нашли ответ, задайте вопрос.

Математика - это совместно редактируемый форум вопросов и ответов для начинающих и опытных математиков, с особенным акцентом на компьютерные науки.

Присоединяйтесь!

отмечен:

задан
26 Апр '14 14:57

показан
2616 раз

обновлен
17 Янв '15 18:51

по почте:

Зарегистрировавшись, вы сможете подписаться на любые обновления

по RSS:

Ответы

Ответы и Комментарии