Задача
Решите сравнения:
а) 8x ≡ 3 (mod 13);
б) 17x ≡ 2 (mod 37);
в) 7x ≡ 2 (mod 11);
г) 80x ≡ 17 (mod 169).
Решение
а) 8x ≡ 16 (mod 13), поэтому x ≡ 2 (mod 13). б) Первый способ. –20x ≡ 2 (mod 37) ⇒ 10x ≡ 36 (mod 37) ⇒ 5x ≡ 18 ≡ 55 (mod 37) ⇒ x ≡ 11 (mod 37).
Второй способ. Решим уравнение 17x – 37y = 2 в целых числах.
17(x – 2y) – 3y = 2; сделав замену z = x – 2y, получим 3(5z – y) = 2(1 – z). Отсюда 1 – x = 3t, 5z – y = 2t, z = 1 – 3t, y = 5z – 2t = 5 – 17x,
x = 2y + z = 11 – 37t. в) 7x ≡ 35 (mod 11), поэтому x ≡ 5 (mod 11). г) Первый способ. 80x ≡ 186 (mod 169) ⇒ 40x ≡ 93 ≡ 262 (mod 169) ⇒ 20x ≡ 300 (mod 169) ⇒ x ≡ 15 (mod 169).
Второй способ. 80x ≡ 17 (mod 169) ⇒ 2x ≡ 4 (mod 13) ⇒ x ≡ 2 (mod 13), то есть x = 13n + 2. 80(13n + 2) ≡ 17 (mod 169) ⇒ 80n + 11 ≡ 0 (mod 13) ⇒ 2n ≡ 2 (mod 13) ⇒ n = 13k + 1 ⇒ x ≡ 15 (mod 169).
Ответ
а) x ≡ 2 (mod 13); б) x ≡ 11 (mod 37); в) x ≡ 5 (mod 11); г) x ≡ 15 (mod 169).
Чтобы оставлять комментарии, войдите или зарегистрируйтесь