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).