Для решения сравнения 91x = 1 (mod 132) с помощью цепных дробей, мы будем использовать алгоритм Евклида расширенный.
Найдем наибольший общий делитель (НОД) для 91 и 132:
91 = 132 * 0 + 91 91 = 91 * 1 + 0
НОД(91, 132) = 91
Теперь мы будем решить систему сравнений:
91 * x = 1 (mod 132) 91 * x = 132 * y + 1
Используем алгоритм Евклида расширенный для нахождения x и y:
Переходим к следующему шагу:
132 = 91 * 1 + 41 91 = 41 * 2 + 10 41 = 10 * 4 + 1
Теперь находим обратные числа:
1 = 41 - 10 * 4 1 = 41 - 10 * (91 - 41 * 2) 1 = 3 * 41 - 10 * 91 1 = 3 * (132 - 91) - 10 * 91 1 = 3 * 132 - 13 * 91
Таким образом, x = -13 (mod 132).
Теперь найдем x в пределах от 0 до 131:
x = -13 + 132 * k, где k - целое число
x = 119 + 132 * k
Таким образом, решением сравнения 91x = 1 (mod 132) является x = 119 + 132 * k, где k - целое число.
Для решения сравнения 91x = 1 (mod 132) с помощью цепных дробей, мы будем использовать алгоритм Евклида расширенный.
Найдем наибольший общий делитель (НОД) для 91 и 132:
91 = 132 * 0 + 91
91 = 91 * 1 + 0
НОД(91, 132) = 91
Теперь мы будем решить систему сравнений:
91 * x = 1 (mod 132)
91 * x = 132 * y + 1
Используем алгоритм Евклида расширенный для нахождения x и y:
91 = 132 * 0 + 91
91 = 91 * 1 + 0
Переходим к следующему шагу:
132 = 91 * 1 + 41
91 = 41 * 2 + 10
41 = 10 * 4 + 1
Теперь находим обратные числа:
1 = 41 - 10 * 4
1 = 41 - 10 * (91 - 41 * 2)
1 = 3 * 41 - 10 * 91
1 = 3 * (132 - 91) - 10 * 91
1 = 3 * 132 - 13 * 91
Таким образом, x = -13 (mod 132).
Теперь найдем x в пределах от 0 до 131:
x = -13 + 132 * k, где k - целое число
x = 119 + 132 * k
Таким образом, решением сравнения 91x = 1 (mod 132) является x = 119 + 132 * k, где k - целое число.