<font color=blue><b>!!!</b></font>
Здравствуйте, 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 является простым, в чем можно убедиться, <font color=blue> !!! 10¹⁰⁰ - 3 составное число, оно делится на 13</font>
например, применив следующую теорему теории сравнений:
"Пусть (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. <font color=blue> !!! 10⁴ - 3 = 9997 = 13*769 </font>

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 <font color=blue> !!! 10¹⁰⁰ - 7 делится на 3</font>
(число 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.

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

С уважением.<p><fieldset style=‘background-color:#EFEFEF; width:80%; border:blue 1px solid; padding:10px;‘ class=fieldset><font color=blue><i></i>
-----
</font><font color=#777777 size=1><b>• Отредактировал: <a href=http://rusfaq.ru/info/user/118729 target=_blank>Агапов Марсель</a></b> (Профессор)
<b>• Дата редактирования:</b> 08.06.2008, 22:03 (MCK)</font></fieldset>