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

Обернене за модулем щодо цілого число 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.