Расчет Pow (45,60) мод 61

Question

Это вопрос домашнего задания.

Мне нужно вычислить 45 ^ 60 mod 61. Я хочу знать о любом быстром способе получения результата программно или вручную, в зависимости от того, что быстрее.

Answer 1

Результат будет 1 из-за маленькой теоремы Ферма

, если p простое число.

61 - простое число, поэтому ap-1 при делении на p даст 1 в качестве остатка.

Однако, если p не является простым, обычный трюк повторяется в квадрате.

Answer 2

45^60 =
2025^30 = (33*61 + 12)^30 = 12^30 =
144^15 = (2*61 + 22)^15 = 22^15 =
10648^5 = ( 174*61 + 34)^5 = 34^5 =
45435424 = 744843 * 61 + 1 = 1

Здесь равенство означает = (мод 61)

Answer 3

Я бы сказал, что лучше всего использовать маленькую теорему Ферма.

Маленькая теорема Ферма

, где р = 61 и р-1 = 60.

Надеюсь, что поможет

Answer 4

45^2         = 2025 = 12
45^4  = 12^2 = 144  = 22
45^8  = 22^2 = 484  = 57
45^16 = 57^2 = 3249 = 16
45^32 = 16^2 = 256  = 12

45^60 = 45^(4+8+16+32) = 22 * 57 * 16 * 12 = 1

Answer 5

Wolfram Alpha

Всегда имейте под рукой Wolfram Alpha : D