Найдите остаток от деления 30^99+61^99 на 31. Найдите остаток от деления 30^99+61^99 на 31.

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

Для того чтобы найти остаток от деления выражения (30^{99} + 61^{99}) на 31, можно воспользоваться малой теоремой Ферма.

По малой теореме Ферма для любого простого числа (p) и любого целого числа (a), не делящегося на (p), верно:

[ a^{p-1} \equiv 1 \pmod{p} ]

В данном случае (p = 31) - простое число. Тогда (30^{30} \equiv 1 \pmod{31}) и (61^{30} \equiv 1 \pmod{31}).

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

[ 30^{99} + 61^{99} ]

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

[ 30^{99} \equiv 30^{3} \equiv 27 \pmod{31} ]

[ 61^{99} \equiv 61^{3} \equiv 1 \pmod{31} ]

[ 30^{99} + 61^{99} \equiv 27 + 1 \equiv 28 \pmod{31} ]

Таким образом, остаток от деления выражения (30^{99} + 61^{99}) на 31 равен 28.