Question

Какой остаток имеет 92! при делении на 97? Какой остаток имеет 69^7^39 при делении на 66? (69 в степени 7, которая в степени 39)

Answer 1

Ответ:

остаток равен 5

Пошаговое объяснение:

97:92=2 ( остаток 5)

Answer 2

Остаток от деления 92! на 97 можно найти с помощью малой теоремы Ферма. По этой теореме, если p - простое число, а a - целое число, не делящееся на p, то a^(p-1) при делении на p дает остаток 1. То есть, a^(p-1) ≡ 1 (mod p).

В данном случае, p = 97, исходное число a = 92!. Так как 97 - простое число и 92 не делится на 97, то можно использовать малую теорему Ферма.

Так как 97 - простое число, то (97-1) = 96 делится на 97. То есть, 92!^(97-1) ≡ 1 (mod 97).

Теперь найдем остаток от деления 92! на 97:

92!^(97-1) ≡ 1 (mod 97)

92!^96 ≡ 1 (mod 97)

Так как 92! больше 97, левую часть уравнения удобно разбить на несколько множителей, чтобы их степени упростились. Для этого воспользуемся китайской теоремой об остатках.

92!^96 ≡ 1 (mod 97)

92! ≡ a (mod 97)

a^96 ≡ 1 (mod 97)

Подберем значение a (1 ≤ a ≤ 96), для которого a^96 ≡ 1 (mod 97).

Попробуем a = 2. Для этого значения:

2^96 ≡ 57 (mod 97)

Поэтому 92! ≡ 2 (mod 97).

Таким образом, остаток от деления 92! на 97 равен 2.

Теперь рассмотрим остаток от деления 69^(7^39) на 66.

69^(7^39) ≡ (69^6)^(7^39/6) (mod 66)

Так как 69 и 66 не взаимно простые, нам нужно использовать другую теорему, чтобы помочь упростить выражение.

Теорема Эйлера: если a и n - взаимно простые числа, то a^(φ(n)) ≡ 1 (mod n), где φ(n) - функция Эйлера, равная количеству взаимно простых чисел с n, меньших n.

Расчитаем значение функции Эйлера для 66:

66 = 2 * 3 * 11

φ(66) = φ(2) * φ(3) * φ(11) = 1 * 2 * 10 = 20

По теореме Эйлера:

69^(20) ≡ 1 (mod 66)

Теперь разложим показатель степени 7^39 на множители:

7^39 = 7^(20 * 1 + 19)

Теперь упростим выражение:

69^(7^39) ≡ (69^(20))^1 * (69^19) ≡ 1 * (69^19) (mod 66)

Теперь нас интересует остаток от деления 69^19 на 66. По аналогичным расчетам, остаток от деления 69^19 на 66 равен 45.

Таким образом, остаток от деления 69^(7^39) на 66 равен 45.