3х сравнимо с 5 по модулю 34

Задача: решить 3x ≡ 5 (mod 34). Пошагово это можно сделать так: 1) Проверяем взаимную простоту: gcd(3, 34) = 1, значит 3 имеет обратный элемент по модулю 34 и уравнение имеет единственное решение модуль 34. 2) Найдём обратный элемент к 3 по модулю 34. Используем расширенный алгоритм Евclid: - 34 = 3·11 + 1 - 1 = 34 - 3·11 Это значит, что 1 ≡ -11·3 (mod 34) ⇒ 3·(-11) ≡ 1 (mod 34). Следовательно, обратный элемент к 3 по модулю 34 равен -11, который эквивалентен 23 (потому что -11 ≡ 23 mod 34). 3) Умножаем обе стороны уравнения на обратный элемент 3: x ≡ 23 · 5 (mod 34) = 115 (mod 34). 4) Упрощаем 115 по модулю 34: 34·3 = 102, 115 − 102 = 13. Итак, x ≡ 13 (mod 34). Ответ: все решения задаются как x = 13 + 34k, где k — любое целое число. Проверка: 3·13 = 39 ≡ 5 (mod 34).