ModularInverse

ModularInverse[k,n]

gives the modular inverse of k modulo n.

Details

  • ModularInverse is also known as modular multiplicative inverse.
  • Integer mathematical function, suitable for both symbolic and numerical manipulation.
  • Typically used in modular arithmetic and cryptography.
  • ModularInverse[k,n] gives the number r such that the remainder of the division of r k by n is equal to 1.
  • If k and n are not coprime, no modular inverse exists and ModularInverse[k,n] remains unevaluated.

Examples

open allclose all

Basic Examples  (2)

Compute the inverse of 3 modulo 5 and check the result:

Plot the sequence with a fixed modulus:

Scope  (2)

Numerical Evaluation  (2)

Compute using integers:

Gaussian integers:

Compute using large integers:

Applications  (4)

Basic Applications  (2)

Two numbers are modular inverses of each other if their product is 1:

Modular computation of a matrix inverse:

First compute the matrix adjoint:

Then compute the modular inverse of a matrix:

Check that the inverse gives the correct result:

Number Theory  (2)

Build an RSA-like toy encryption scheme. Start with the modulus:

Find the universal exponent of the multiplication group modulo n:

Private key:

Public key:

Encrypt a message:

Decrypt it:

Create a random number generator that uses the current time as a seed:

Choose modulus parameters:

Compute 20 random numbers between 0 and 1:

Properties & Relations  (6)

ModularInverse is a periodic function:

ExtendedGCD returns modular inverses:

Compute using PowerMod:

The results have the same sign as the modulus:

If and are coprime, then is invertible modulo :

Computing ModularInverse twice yields the original argument:

Possible Issues  (1)

For nonzero integers k and n, ModularInverse[k,n] exists if and only if k and n are coprime:

However, 10 and 22 are not coprime:

Interactive Examples  (1)

Visualize inverses modulo varying prime numbers:

Neat Examples  (2)

Visualize when a number is invertible modulo 12:

Modular inverses of sums of two squares:

Wolfram Research (2017), ModularInverse, Wolfram Language function, https://reference.wolfram.com/language/ref/ModularInverse.html.

Text

Wolfram Research (2017), ModularInverse, Wolfram Language function, https://reference.wolfram.com/language/ref/ModularInverse.html.

CMS

Wolfram Language. 2017. "ModularInverse." Wolfram Language & System Documentation Center. Wolfram Research. https://reference.wolfram.com/language/ref/ModularInverse.html.

APA

Wolfram Language. (2017). ModularInverse. Wolfram Language & System Documentation Center. Retrieved from https://reference.wolfram.com/language/ref/ModularInverse.html

BibTeX

@misc{reference.wolfram_2025_modularinverse, author="Wolfram Research", title="{ModularInverse}", year="2017", howpublished="\url{https://reference.wolfram.com/language/ref/ModularInverse.html}", note=[Accessed: 21-February-2025 ]}

BibLaTeX

@online{reference.wolfram_2025_modularinverse, organization={Wolfram Research}, title={ModularInverse}, year={2017}, url={https://reference.wolfram.com/language/ref/ModularInverse.html}, note=[Accessed: 21-February-2025 ]}