Автор - Olga8128
(а)
Показателем числа a по модулю m (где a и m взаимно простые) называется наименьшее натуральное число n такое, что aⁿ - 1 делится на m (точнее aⁿ ≡ 1 (mod m)).
Докажем, что у взаимно простых чисел a и m существует показатель. Действительно, пусть его не существует. Тогда есть такие различные числа p и q, что a^p ≡ t (mod m) и a^q ≡ t (mod m). Пусть p < q, тогда a^q : a^p ≡ t : t ≡ 1 (mod m). Деление возможно из-за взаимной простоты a и m. Значит, a^(q-p) ≡ 1 (mod m) и показатель существует.
(б)
Заметим, что 100 ≡ 3 (mod 97), из этого:
100² ≡ 3 * 100¹ ≡ 3 * 3¹ ≡ 3² (mod 97)
100ⁿ ≡ 3 * 100^(n-1) ≡ 3 * 3^(n-1) ≡ 3ⁿ (mod 97)
Кроме того известно, что 3⁰ + 3¹ + ... + 3ⁿ = (3^(n+1) - 1)/2.
Докажем это при помощи метода математической индукции:
База (n = 1):
3⁰ = (3¹ - 1)/2
Переход (от n к n+1):
Пусть мы доказали, что:
3⁰ + 3¹ + ... + 3^(n-1) = (3ⁿ - 1)/2
Докажем тогда, что:
3⁰ + 3¹ + ... + 3ⁿ = (3^(n+1) - 1)/2
По предположению индукции:
(3ⁿ - 1)/2 + 3ⁿ = (3^(n+1) - 1)/2
3ⁿ - 1 + 2 * 3ⁿ = 3^(n+1) - 1
3 * 3ⁿ - 1 = 3^(n+1) - 1
Переход доказан.
Наше число представимо в виде 100⁰ * 19 + 100¹ * 19 + ... + 100ⁿ * 19 ≡ 3⁰ * 19 + 3¹ * 19 + ... + 3ⁿ * 19 ≡ (3^(n+1) - 1)/2 * 19 (mod 97).
Так как 19 и 2 взаимно просты с 97, можно их убрать. Если число 3^(n+1)-1 не делилось на 97, то и при умножении на них делиться не будет.
А теперь заметим, что существует такое n, что 3^(n + 1) - 1 делится на 97 (по первой задаче).
Ответ: существует.