Search for a tool
Modular Multiplicative Inverse

Tool to compute the modular inverse of a number. The modular multiplicative inverse of an integer N modulo m is an integer n such as the inverse of N modulo m equals n.

Results

Modular Multiplicative Inverse -

Tag(s) : Arithmetics

Share
dCode and more

dCode is free and its tools are a valuable help in games, maths, geocaching, puzzles and problems to solve every day!
A suggestion ? a feedback ? a bug ? an idea ? Write to dCode!

Please, check our dCode Discord community for help requests!
NB: for encrypted messages, test our automatic cipher identifier!

Feedback and suggestions are welcome so that dCode offers the best 'Modular Multiplicative Inverse' tool for free! Thank you!

Modular Multiplicative Inverse

Batch InvMod Calculator

What is the modular Inverse? (Definition)

The value of the modular inverse of $a$ by the modulo $n$ is the value $a^{-1}$ such that $a \cdot a^{-1} \equiv 1 \pmod n$

It is common to note this modular inverse $u$ and to use these equations $$u \equiv a^{-1} \pmod n \\ a u \equiv 1 \pmod n$$

If a modular inverse exists then it is unique.

How to calculate a modular inverse?

To calculate the value of the modulo inverse, use the extended euclidean algorithm which finds solutions to the Bezout identity $au + bv = \text{G.C.D.}(a, b)$. Here, the gcd value is known, it is 1: $\text{G.C.D.}(a, b) = 1$, thus, only the value of $u$ is needed.

Example: $3^{-1} \equiv 4 \mod 11$ because $4 \times 3 = 12$ and $12 \equiv 1 \mod 11$

dCode uses the Extended Euclidean algorithm for its inverse modulo N calculator and arbitrary precision functions to get results with big integers.

How to calculate v in au+bv?

Use the Bezout identity, also available on dCode.

What does invmod mean?

The keyword invmod is the abbreviation of inverse modular.

What is a multiplicative inverse?

A multiplicative inverse is the other name of a modular inverse.

Source code

dCode retains ownership of the "Modular Multiplicative Inverse" source code. Except explicit open source licence (indicated Creative Commons / free), the "Modular Multiplicative Inverse" algorithm, the applet or snippet (converter, solver, encryption / decryption, encoding / decoding, ciphering / deciphering, breaker, translator), or the "Modular Multiplicative Inverse" functions (calculate, convert, solve, decrypt / encrypt, decipher / cipher, decode / encode, translate) written in any informatic language (Python, Java, PHP, C#, Javascript, Matlab, etc.) and all data download, script, or API access for "Modular Multiplicative Inverse" are not public, same for offline use on PC, mobile, tablet, iPhone or Android app!
Reminder : dCode is free to use.

Cite dCode

The copy-paste of the page "Modular Multiplicative Inverse" or any of its results, is allowed (even for commercial purposes) as long as you credit dCode!
Exporting results as a .csv or .txt file is free by clicking on the export icon
Cite as source (bibliography):
Modular Multiplicative Inverse on dCode.fr [online website], retrieved on 2024-09-10, https://www.dcode.fr/modular-inverse

Need Help ?

Please, check our dCode Discord community for help requests!
NB: for encrypted messages, test our automatic cipher identifier!