Question

Найти остаток от деления числа а на m, если а=5*2^145+7*29^11, m=15

Answer 1

Ответ:

3

Объяснение:

5 * 2 ^ 145 + 7 * 29 ^ 11 = 5 * 2 ^ 145 - 7 mod(15)

Рассмотрим остатки при возведении в степень по модулю 15

Степени двойки    По модулю 15

2                              2

4                              4

8                              8  

16                             1

32                            2

Заметим что они циклятся с периодом 4. Строго докажем это. Для этого запишем 2^m как 2 ^ (4*n + k), k >= 0, k < 4.

2^m = 2 ^ ( 4 * n + k) = 2^(4n) * 2^k = 16^n *2 ^ k = 2 ^ k mod(15)

Тогда 2^145 = 2 ^ (36 * 4 + 1 ) = 2 mod (15)

Тогда исходной равно

5 * 2 ^ 145 + 7 * 29 ^ 11 = 5 * 2 - 7 = 3 mod (15)