Question

Найти остаток от деления 431^386 на 85

Пожалуйста помогите((((((

Answer 1

Ответ:

36

Объяснение:

Я не буду разбивать 85 на делители 5 и 17, так как здесь будет только пара действий.

           431  |_85_

       -   425 | 5

      -----------

                6

431¹≡6¹≡6 (mod 85)

431²≡6²≡36 (mob 85)

Дальше возводить в степень не имеет смысла, так как остаток получится больше делителя и придётся от него отнимать делитель 85, пока остаток не будет меньше делителя. Но мы здесь легко можем увидеть, что количество остатков будет только два.

Наибольший делитель 386, из взятых показателей степени (1 и 2), является 2 ⇒ остаток от деления 431³⁸⁶ на 85 будет 36:

431³⁸⁶≡36 (mod 85)