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

Матеріал з Вікіпедії — вільної енциклопедії.
Перейти до: навігація, пошук

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

Див. також[ред.ред. код]