Найдите остаток от деления 30 в 99 степени + 61 в 100 степени на 31
Чтобы найти остаток от деления \( 30^{99} + 61^{100} \) на \( 31 \), воспользуемся теоремой Ферма, которая утверждает, что если \( p \) — простое число, а \( a \) — целое число, не делящееся на \( p \), то \( a^{p-1} \equiv 1 \mod p \).
Находим \( 30^{99} \mod 31 \): Поскольку \( 30 \equiv -1 \mod 31 \), мы можем переписать:
\[ 30^{99} \equiv (-1)^{99} \equiv -1 \mod 31 \]
Находим \( 61^{100} \mod 31 \): Сначала вычислим \( 61 \mod 31 \):
\[ 61 \equiv 61 - 31 \times 1 \equiv 30 \mod 31 \]
Теперь найдем \( 30^{100} \mod 31 \):
\[ 30^{100} \equiv (-1)^{100} \equiv 1 \mod 31 \]
Теперь складываем результаты:
\[ 30^{99} + 61^{100} \equiv -1 + 1 \equiv 0 \mod 31 \]
Итак, остаток от деления \( 30^{99} + 61^{100} \) на \( 31 \) равен \( 0 \).
