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)
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)