Question

98 БАЛЛОВ! ЗАДАЧА ДЛЯ 5-7 КЛАССОВ. Помогите решить задачи в ДВЕ СТРОЧКИ! Заранее спасибо решившему! а). Если целые числа a и m взаимно-просты, то найдется такое натуральное n, что аⁿ - 1 делится на m. Докажите это. б). Также нужно определить, существует ли число вида 1919...1919, которое делится на 97. Ответ, кажется, положительный.

Answer 1

(а)

Показателем числа 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 (по первой задаче).

Ответ: существует.

Answer 2

а). Для доказательства этого утверждения, мы можем воспользоваться малой теоремой Ферма, которая гласит, что если p - простое число, а a - целое число, не кратное p, то a^(p-1) ≡ 1 (mod p). Здесь "≡" обозначает "конгруэнтно".

Так как a и m взаимно-просты, то a не кратно m, и мы можем использовать малую теорему Ферма для a: a^(m-1) ≡ 1 (mod m). Теперь возьмем n = m-1, тогда aⁿ - 1 = a^(m-1) - 1 ≡ 1 - 1 ≡ 0 (mod m), что означает, что aⁿ - 1 делится на m.

б). Для этой задачи, давайте рассмотрим число вида 1919...1919 с n цифрами "19". Обозначим это число как N = 1919...1919. Тогда мы можем записать это число следующим образом:

N = 19 * 10^(n-1) + 19 * 10^(n-2) + ... + 19 * 10 + 19.

Мы можем вынести общий множитель 19:

N = 19 * (10^(n-1) + 10^(n-2) + ... + 10 + 1).

Теперь давайте рассмотрим числовой ряд в скобках:

10^(n-1) + 10^(n-2) + ... + 10 + 1.

Это геометрическая прогрессия с первым членом a = 1 и знаменателем r = 10. Сумма первых n членов геометрической прогрессии задается формулой:

S_n = (a * (r^n - 1)) / (r - 1).

Подставим значения:

S_n = (1 * (10^n - 1)) / (10 - 1) = (10^n - 1) / 9.

Таким образом, число вида 1919...1919 равно:

N = 19 * ((10^n - 1) / 9) = (2 * 97) * ((10^n - 1) / 9) = (2 * 10^n - 2) / 9.

Теперь нам нужно проверить, делится ли (2 * 10^n - 2) на 97. Для этого достаточно убедиться, что (10^n - 1) делится на 97, потому что 2 и 97 взаимно-просты.

Мы знаем, что 10^(p-1) ≡ 1 (mod p) для любого простого p, не делящего 10. В данном случае p = 97, поэтому:

10^(97-1) ≡ 1 (mod 97).

Таким образом, 10^96 - 1 делится на 97. Мы также знаем, что 10^n - 1 является делителем 10^96 - 1 для любого n, являющегося делителем 96. Следовательно, (2 * 10^n - 2) делится на 97.

Таким образом, число вида 1919...1919 действительно делится на 97.