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

Introduced in 2017
(11.1)