Алёна посчитала обратные для остатков k и 3k по модулю 6k−1, перемножила полученные остатки и получила число, дающее остаток 1 по модулю 6k−1. Найдите остаток, обратный 5k по модулю 6k−1.
Arnfinn ответил на вопрос 03.07.2023
1 Ответ
Для решения задачи воспользуемся теоремой Эйлера:
φ(n) = φ(p_1^{a_1} * p_2^{a_2} * … * p_k^{a_k}) = p_1 — 1 * p_2 — 1 … * p_k — 1 = (p_1 — 1) * (p_2 — 1)…(p_k — 1),
где φ(n) — количество чисел от 1 до n, взаимно простых с n.
Тогда φ(6k-1) = (6-1)*(k-1).
Так как φ(n) взаимно просто с n, то:
6k — 1 и φ(6k — 1) взаимно просты.
Значит, φ(6k − 1) является обратным к 6k − 1 по модулю φ(6k − 1).
Таким образом, чтобы найти остаток, обратный 5k по модулю 6k-1, нужно умножить φ(6k − 1) на 5k и взять остаток по модулю 6k − 1.
Arnfinn ответил на вопрос 03.07.2023