21.07.2018, 07:04 [+3 UTC]
в нашей команде: 2 884 чел. | участники онлайн: 1 (рекорд: 21)

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

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

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

:: правила

:: новости

:: участники

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

:: форум

:: блоги

:: поиск

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

:: наш журнал

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

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

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

:: поддержка

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

Версия системы:
7.47 (16.04.2018)

Общие новости:
13.04.2018, 10:33

Форум:
20.07.2018, 12:27

Последний вопрос:
20.07.2018, 13:35

Последний ответ:
19.07.2018, 14:46

Последняя рассылка:
21.07.2018, 00:45

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

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

Наша кнопка:

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

Отзывы о нас:
27.05.2010, 01:43 »
Sfera
Спасибо ОГРОМНОЕ за помощь!!! Вы меня очень сильно выручили! [вопрос № 178606, ответ № 261695]
01.10.2010, 10:21 »
Спиридонов Данил Сергеевич
Спасибо за помощь. [вопрос № 180103, ответ № 263274]

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

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

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

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

Гордиенко Андрей Владимирович
Статус: Модератор
Рейтинг: 2902
epimkin
Статус: Практикант
Рейтинг: 152
CradleA
Статус: Профессор
Рейтинг: 103

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

Консультация онлайн # 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.13217 сек.

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