модулярная арифметика

Ответ от Ѓдачник[гуру]
1) Степени тройки: 3^1 = 3 3^2 = 9 3^3 = 27 3^4 = 81 3^5 = 243 3 в 5 степени заканчивается на 3. Дальше круг повторяется: 3, 9, 7, 1, 3. 3^25 = (3^5)^5 - заканчивается, так же как 3^5, то есть на 3. 2) Найти обратный элемент по модулю - это значит, решить в целых числах уравнение 7x + 5y = 1 Решаем по известному алгоритму ax + by = 1 1. r = a mod b, то есть r = остатку от деления 7 на 5, r = 2. 2. Поскольку r не = 0, то заменяем пару (a, b) на пару (b, r) и возвращаемся к п. 1. 3. Когда r станет = 0, принимаем x = b x = 3, y = -4 7*3 - 5*4 = 21 - 20 = 1 Ответ: 3 3) Целые решения 5x + 2y = 3 Расширенный алгоритм Евклида ax + by = d 1. Если b = 0, то выводим d = a, x = 1, y = 0 2. Пусть x1 = 0, y1 = 1, x2 = 1, y2 = 0 3. Пока b > 0, делать: 3.1. a = b*q + r, где r - остаток от деления a / b. 3.2. x = x2 - q*x1, y = y2 - q*y1 3.3. Замена a = b, b = r, x2 = x1, x1 = x, y2 = y1, y1 = y 3.4. Возвращаемся к 3.1. с новыми значениями переменных. 4. Выводим d = a, x = x2, y = y2. Ответ: x = 1, y = -1