15.11.2018, 18:49 [+3 UTC]
в нашей команде: 3 110 чел. | участники онлайн: 11 (рекорд: 16)

:: РЕГИСТРАЦИЯ

:: задать вопрос

:: все разделы

:: правила

:: новости

:: участники

:: доска почёта

:: форум

:: блоги

:: поиск

:: статистика

:: наш журнал

:: наши встречи

:: наша галерея

:: отзывы о нас

:: поддержка

:: руководство

Версия системы:
7.55 (06.11.2018)

Общие новости:
24.09.2018, 16:49

Форум:
08.11.2018, 13:36

Последний вопрос:
15.11.2018, 16:52

Последний ответ:
15.11.2018, 14:53

Последняя рассылка:
15.11.2018, 18:45

Писем в очереди:
0

Мы в соцсетях:

Наша кнопка:

RFpro.ru - здесь вам помогут!

Отзывы о нас:
29.12.2011, 23:20 »
Тарас
Огромное спасибо! Ваш сайт очень полезен, откровенен и очень полезный, самое главное правдивый, Вы помогаете людям, и самое главное не отступить от этих принципов !
18.03.2012, 08:59 »
comden
Как всегда на высоте [вопрос № 185613, ответ № 270252]

РАЗДЕЛ • Математика

Консультации и решение задач по алгебре, геометрии, анализу, дискретной математике.

[администратор рассылки: Лысков Игорь Витальевич (Старший модератор)]

Лучшие эксперты в этом разделе

Гордиенко Андрей Владимирович
Статус: Мастер-Эксперт
Рейтинг: 2854
Лангваген Сергей Евгеньевич
Статус: Академик
Рейтинг: 158
Лысков Игорь Витальевич
Статус: Старший модератор
Рейтинг: 130

Перейти к консультации №:
 

Консультация онлайн # 139391
Раздел: • Математика
Автор вопроса: S@ZaN
Отправлена: 07.06.2008, 02:40
Поступило ответов: 1

hi dear expers!!!
помогите с двумя задачками.
1 требуется найти такое минимальное натуральное число k, что число (10 в степени 100 )– k является простым.
2 как определить простое число или нет.
заранее благодарен

Состояние: Консультация закрыта

!!!
Здравствуйте, S@ZaN!

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

1. Применим перебор значений k:
k = 1, число 10^100 - 1 не является простым, поскольку делится на число (10 - 1) = 9;
k = 2, число 10^100 - 2 не является простым, поскольку 10^100 - 2 = (2*5)^100 - 2 = 2*((2^99)*(5^100) - 1) делится на 2;
k = 3, число 10^100 - 3 является простым, в чем можно убедиться, !!! 10100 - 3 составное число, оно делится на 13
например, применив следующую теорему теории сравнений:
"Пусть (m, 10) = 1, P(m) (10) = k и N записано в системе счисления с основанием 10. Число N делится на m тогда и только тогда, когда на m делится сумма чисел, которые получаются при разбиении справа налево цифровой записи числа N на грани по k цифр в каждой грани".

Примечание. Через P(m) обозначено P с нижним индексом m.

К сожалению, данный способ требует проверки делимости числа 10^100 - 3 на большое количество простых чисел. Полагаю, что проще по индукции воспользоваться тем фактом, что:
- число 10^1 - 3 является ближайшим простым числом, меньшим 10^1,
- число 10^2 - 3 является ближайшим простым числом, меньшим 10^2,
- число 10^3 - 3 является ближайшим простым числом, меньшим 10^3,
..., следовательно, число 10^100 - 3 является ближайшим простым числом, меньшим 10^100, и k = 3. !!! 104 - 3 = 9997 = 13*769

2. Можно воспользоваться способом, известным как решето Эратосфена, основанным на следующей теореме:
"1) Если в множестве натуральных чисел 2, 3, 4, ..., N зачеркнуть числа, кратные первым r простым числам 2, 3, ..., p(r), то первое (наименьшее) незачеркнутое число будет простым.
2) Если вычеркнуть все числа, кратные всем простым числам до sqrt N, то есть выбрать r так, что p(r) <= sqrt N < p(r+1), то оставшиеся числа будут совпадать с множеством всех простых чисел, таких, что sqrt N < p <= N".

Можно воспользоваться теоремой Вильсона: "Число p является простым тогда и только тогда, когда оно является делителем числа (p - 1)! + 1".

Весь вопрос в том, насколько эти критерии подходят для практических вычслений...

Примечание. Через p(r) обозначено число p с нижним индексом r.

Поделюсь следующим соображением. Обе задачи, по существу, сводятся к факторизации чисел n, то есть к их представлению в каноническом виде. Общий метод факторизации заключается в том, что n пробуют делить последовательно на простые числа 2, 3, 5, ..., p(r) <= sqrt n до тех пор, пока не найдется простое число p, такое, что n делится на p. Если такое число не найдется, то n - простое число.

Стало быть, применительно к задаче 1, необходимо факторизовать число 10^100 - 3. Если его удастся факторизовать, то оно не является простым, и следует перейти к числу 10^100 - 7 !!! 10100 - 7 делится на 3
(число 10^100 - 5 не является простым, поскольку
10^100 - 5 = (2*5)^100 - 2 = 5*((5^99)*(2^100) - 1) делится на 5) и так далее. Для факторизации необходимо число 10^100 - k делить на простые числа 3, 7, ..., p(r) < 10^50.

Конечно, профессиональный математик дал бы более рациональный ответ...

С уважением.


-----
• Отредактировал: Агапов Марсель (Профессор)
• Дата редактирования: 08.06.2008, 22:03 (MCK)


Консультировал: Гордиенко Андрей Владимирович (Мастер-Эксперт)
Дата отправки: 08.06.2008, 20:51

Рейтинг ответа:

0

[подробно]

Сообщение
модераторам

Отправлять сообщения
модераторам могут
только участники портала.
ВОЙТИ НА ПОРТАЛ »
регистрация »

Возможность оставлять сообщения в мини-форумах консультаций доступна только после входа в систему.
Воспользуйтесь кнопкой входа вверху страницы, если Вы зарегистрированы или пройдите простую процедуру регистрации на Портале.

Яндекс Rambler's Top100

главная страница | поддержка | задать вопрос

Время генерирования страницы: 0.41494 сек.

© 2001-2018, Портал RFPRO.RU, Россия
Калашников О.А.  |  Гладенюк А.Г.
Версия системы: 7.55 от 06.11.2018