# 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:

Then compute the modular inverse of a matrix:

Check that the inverse gives the correct result:

### Number Theory(2)

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_2024_modularinverse, author="Wolfram Research", title="{ModularInverse}", year="2017", howpublished="\url{https://reference.wolfram.com/language/ref/ModularInverse.html}", note=[Accessed: 18-July-2024 ]}

#### BibLaTeX

@online{reference.wolfram_2024_modularinverse, organization={Wolfram Research}, title={ModularInverse}, year={2017}, url={https://reference.wolfram.com/language/ref/ModularInverse.html}, note=[Accessed: 18-July-2024 ]}