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

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

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

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

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

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

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

Пояснення

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

Наприклад,

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

породжує

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

Найменший x, що розв'язує цю тотожність це 4: ${\displaystyle 3*4=12\equiv 1{\pmod {11}}}$.

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

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

Див. також

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

Посилання

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