Здравствуйте, barhat!
Задача Б. Чтобы вычислить 66/71 = 66[$149$]71^-1 необходимо найти элемент кольца, обратный к 71 по умножению. То есть надо найти такое x, что 71[$149$]x [$8801$] 1 (mod 85). Обратный элемент существует, если элемент заимно прост с модулем кольца. В нашем случае верно, что 71 [$8869$] 85.

Вариант 1. Уравнение 71[$149$]x [$8801$] 1 (mod 85) можно расписать как:
71x - 85y = 1, при целых x и y
Такое уравнение можно решить с помощью расширенного алгоритма Евклида. Алгоритм даёт решение: x = 6, y = 5, значит 71^-1 = 6 в кольце Z₈₅. Таким образом 66/71 = 66[$149$]6 = 56 (mod 85)

Вариант 2. Обратный элемент можно найти используя теорему Эйлера:
71^-1 = 71^{[$966$](85) - 1}, где [$966$](n) - функция Эйлера
[$966$](n) = [$8719$]p_i^[$945$](p_i - 1), где p_i - простой множитель числа n со степенью [$945$].
Так как 85 = 5[$149$]17, то [$966$](85) = 4[$149$]16 = 64. Значит 71^-1 = 71⁶³ = 6 (mod 85)

Вариант 3. Если заметить, что 71⁶ = 66 (mod 85), то выражение упрощается:
66[$149$]71^-1 = 71⁶[$149$]71^-1 = 71⁵ = 56 (mod 85)

Ответ: 66/71 = 56 в кольце по модулю 85.

Здравствуйте, barhat!



С уважением.

Здравствуйте, barhat!

а) Для решения этой задачи используем следующую теорему:

Если D и Q - натуральные числа, причём D не является квадратом и D > Q[sup]2[/sup], то число [$8730$]D/Q разлагается в периодическую цепную дробь вида [a[sub]0[/sub];(a[sub]1[/sub],a[sub]2[/sub],...,a[sub]k-1[/sub],2a[sub]0[/sub])].

Для x = [$8730$]315 имеем D = 315, Q = 1. Найдем разложение в цепную дробь:











Так как a[sub]3[/sub] = 2a[sub]0[/sub], то [$8730$]315 = [17; (1, 2, 1, 34)]. Найдём последовательность подходящих дробей:
[17; 1] = 18;
[17; 1, 2] = 17 2/3 [$8776$] 17.6667;
[17; 1, 2, 1] = 17 3/4 [$8776$] 17.75;
[17; 1, 2, 1, 34] = 17 104/139 [$8776$] 17.7482;
[17; 1, 2, 1, 34, 1] = 17 107/143 [$8776$] 17.74825;
[17; 1, 2, 1, 34, 1, 2] = 17 318/425 [$8776$] 17.74824.

Таким образом, [$8730$]315 [$8776$] 17.7482.

б) Частное будет решением сравнения 71x [$8801$] 66 (mod 85). Так как НОД(71,85) = 1 (71 и 85 - взаимно простые числа), то существует единственное решение. Оно равно 56 (71·56 = 3976 = 85·46 + 66).