Обернене за модулем число

Обернене за модулем щодо цілого число a за модулем m — це ціле x, таке що

$a^{-1} \equiv x \pmod{m}.$

Тобто, це обернене число в кільці цілих за модулем m. Тотожно до

$ax \equiv aa^{-1} \equiv 1 \pmod{m}.$

Обернене за модулем число щодо a по модулю m існує тоді і тільки тоді, коли a і m взаємно прості (тобто, якщо НСД(a, m) = 1). Якщо обернене за модулем число щодо a по модулю m існує, операцію ділення на a за модулем m можна визначити як множення на обернене, яке по суті є тією самою концепцією, що і ділення в полі дійсних чисел.

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

Пояснення

Коли обернене існує, воно завжди єдине в $\mathbb{Z}_m$, де m це модуль. Отже x, вибраний як обернене за модулем зазвичай член $\mathbb{Z}_m$.

Наприклад,

$3^{-1} \equiv x \pmod{11}$

породжує

$3x \equiv 1 \pmod{11}$

Найменший x, що розв"язує цю тотожність це 4. Легко знайти інші, наприклад, 15 = 4 + 11.