Методика решения уравнений в алгебре вычетов

Решение уравнений с вычетами типа ax + b = c (mod n) легко свести к виду ax d (mod n), и получить ответ, умножив на a^-1.

Пример: 3x

8 (mod 14).

x	0	1	2	3	4	5	6	7	8	9	10	11	12	13
3x	0	3	6	9	12	1	4	7	10	13	2	5	8	11

Ответ: x

12 (mod 14).

Пример: 3x

4 (mod 5).

Находим a=3 в левом столбце. В строке находим d=4, и считываем ответ над этой цифрой в первой строке. x

3 (mod 5).

Пример: 3x

8 (mod 14).
3x = 8 +14y
x = (8 +14y)/3 = (6+2 + 12y+2y)/3 = 2+4y + (2+2y)/3 Обозначаем дробь целой переменной (2+2y)/3 = z

x = 2+4y + z
2+2y = 3z
2y = 3z -2
y = (3z -2)/2 = z - 1+ (z)/2
Обозначаем (z)/2 = u

y = z - 1+ u
z = 2u - решение в целых числах. Выражаем все через u.
y = z - 1+ u = 3u - 1.
x = 2+4y + z = 2 + 4(3u-1) + 2u = 14u - 2.
x

-2

12 (mod 14).

Пример: 3x

8 (mod 14).
Z*(14) = {1, 3, 5, 9, 11, 13}.

(n) = |Z*₁₄| = 6
3^-1 = 3⁵ = 9*9*3 =(70+11)*3

11*3 = 33

5 (mod 14).
Умножим обе части исходного сравнения на обратный вычет 3^-1.
x

5*8 = 40

12 (mod 14).