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

Обернене за модулем щодо цілого число 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: $3*4=12\equiv 1{\pmod {11}}$.

Можна розв'язати це рівняння і по іншому:

$x={\frac {1}{3}}={\Big (}1\equiv 12{\pmod {11}}{\Big )}={\frac {12}{3}}=4.$

Див. також

• Обернене число
• Розширений алгоритм Евкліда

Посилання

• Weisstein, Eric W. Обернене за модулем число(англ.) на сайті Wolfram MathWorld.