Как найти остаток от деления 54^124 на 17? Задача простенькая, если знать малую теорему Ферма. Можно конечно и без неё вполне решить.

Предыдущий
вопрос Следующий
вопрос

Для начала найдем остаток от деления 54 на 17:
54 = 3 (mod 17).

После этого воспользуемся свойством остатков при умножении:

(54^124) mod 17 = (3^124) mod 17.

Теперь применим малую теорему Ферма, которая гласит следующее: если p - простое число, а a - целое число, не делящееся на p, то a^(p-1) mod p = 1.

В данном случае p = 17, поэтому:

3^16 mod 17 = 1.

Теперь найдем остаток от деления 124 на 16:

124 = 7*16 + 12.

Следовательно:

(3^124) mod 17 = (3^(716 + 12)) mod 17 = ((3^16)^7 3^12) mod 17 = (1^7 * 3^12) mod 17 = 3^12 mod 17.

Теперь снова применим малую теорему Ферма:

3^12 mod 17 = 3^(716+5) mod 17 = ((3^16)^7 3^5) mod 17 = (1^7 * 3^5) mod 17 = 243 mod 17 = 13.

Ответ: остаток от деления 54^124 на 17 равен 13.