Решить систему линейного сравнения. 5x=14(mod12) 7x=2(mod8)

Предыдущий
вопрос Следующий
вопрос

Для решения данной системы линейных сравнений воспользуемся расширенным алгоритмом Евклида.

1) Решим уравнение 5x ≡ 14 (mod 12):

12 = 52 + 2
5 = 22 + 1
1 = 5 - 22 = 5 - 2(12 - 52) = 55 - 212 = -712 + 35*5

Отсюда получаем, что x ≡ -7 ≡ 5 (mod 12).

2) Решим уравнение 7x ≡ 2 (mod 8):

8 = 71 + 1
1 = 8 - 71 = 8 - 78 = 18 - 7*8

Отсюда получаем, что x ≡ 1*2 ≡ 2 (mod 8).

Таким образом, решение системы линейных сравнений 5x ≡ 14 (mod 12) и 7x ≡ 2 (mod 8) будет x ≡ 5 (mod 12) и x ≡ 2 (mod 8), что можно записать как x ≡ 29 (mod 24).