WOLFRAM

Wolfram Language & System Documentation Center

ModularInverse[k,n]

gives the modular inverse of k modulo n.

Details
Details and Options Details and Options
Examples  
Basic Examples  
Scope  
Numerical Evaluation  
Applications  
Basic Applications  
Number Theory  
Properties & Relations  
Possible Issues  
Interactive Examples  
Neat Examples  
See Also
Related Guides
Related Links
History
Cite this Page

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 all close all

Basic Examples  (2)

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

Wolfram Language code: ModularInverse[3, 5]

Plot the sequence with a fixed modulus:

Wolfram Language code: DiscretePlot[ModularInverse[k, 17], {k, 1, 16}]

Scope  (2)

Numerical Evaluation  (2)

Compute using integers:

Wolfram Language code: ModularInverse[3, 7]
Wolfram Language code: ModularInverse[-5, 7]

Gaussian integers:

Wolfram Language code: ModularInverse[3 - I, 5 + 2I]

Compute using large integers:

Wolfram Language code: ModularInverse[10 ^ 100000, NextPrime[1000]]

Applications  (4)

Basic Applications  (2)

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

Wolfram Language code: frame = If[# == 1, Style[#, Red], #]&;
Wolfram Language code: p = Prime[5]; g = Range[1, p - 1]; t = Table[frame[Mod[a b, p]], {a, g}, {b, g}];
Wolfram Language code: TableForm[t, TableHeadings -> {g, g}]

Modular computation of a matrix inverse:

Wolfram Language code: A = {{3, 4}, {2, 5}};

First compute the matrix adjoint:

Wolfram Language code: MinorMatrix[Mat_List ? MatrixQ] := Map[Reverse, Minors[Mat], {0, 1}] CofactorMatrix[Mat_List ? MatrixQ] := MapIndexed[#1 (-1) ^ (Plus@@#2)&, MinorMatrix[Mat], {2}] MatrixAdjoint[Mat_] := Transpose[CofactorMatrix[Mat]];

Then compute the modular inverse of a matrix:

Wolfram Language code: ModularInverseMatrix[Mat_, m_] := Mod[ModularInverse[Det[Mat], m]MatrixAdjoint[Mat], m]; ModularInverseMatrix[A, 13]

Check that the inverse gives the correct result:

Wolfram Language code: Mod[A.%, 13]

Number Theory  (2)

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

Wolfram Language code: {p, q} = Prime[RandomInteger[{10 ^ 4, 10 ^ 5}, {2}]]; n = p q

Find the universal exponent of the multiplication group modulo n:

Wolfram Language code: λ = CarmichaelLambda[n]

Private key:

Wolfram Language code: d = NestWhile[#1 + 1& , Round[n / 3], GCD[λ, #1] =!= 1&]

Public key:

Wolfram Language code: e = ModularInverse[d, λ]

Encrypt a message:

Wolfram Language code: PowerMod[ToCharacterCode["RSA in Mathematica"], e, n]

Decrypt it:

Wolfram Language code: FromCharacterCode[PowerMod[%, d, n]]

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

Wolfram Language code: x[0] = UnixTime[]; x[k_] := If[x[k - 1] == 0, a, Mod[a ModularInverse[x[k - 1], m] + c, m]]

Choose modulus parameters:

Wolfram Language code: m = 2147483647; a = 16807; c = 1891423;

Compute 20 random numbers between 0 and 1:

Wolfram Language code: Histogram[Table[x[i] / m, {i, 0, 20}], 10]

Properties & Relations  (6)

ModularInverse is a periodic function:

Wolfram Language code: {ModularInverse[2, 5], ModularInverse[2 + 5, 5]}

ExtendedGCD returns modular inverses:

Wolfram Language code: {g, {a, b}} = ExtendedGCD[3, 5]
Wolfram Language code: ModularInverse[3, 5] == a

Compute using PowerMod:

Wolfram Language code: {ModularInverse[3, 5], PowerMod[3, -1, 5]}

The results have the same sign as the modulus:

Wolfram Language code: ModularInverse[5, 7]
Wolfram Language code: ModularInverse[5, -7]

If and are coprime, then is invertible modulo :

Wolfram Language code: CoprimeQ[7, 12]
Wolfram Language code: ModularInverse[7, 12]

Computing ModularInverse twice yields the original argument:

Wolfram Language code: ModularInverse[ModularInverse[7, 9], 9]

Possible Issues  (1)

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

Wolfram Language code: CoprimeQ[10, 21]
Wolfram Language code: ModularInverse[10, 21]
Wolfram Language code: ModularInverse[21, 10]

However, 10 and 22 are not coprime:

Wolfram Language code: CoprimeQ[10, 22]
Wolfram Language code: ModularInverse[10, 22]
Wolfram Language code: ModularInverse[22, 10]

Interactive Examples  (1)

Visualize inverses modulo varying prime numbers:

Wolfram Language code: Manipulate[ ArrayPlot[Table[If[ModularInverse[a, Prime[n]] == Mod[b, Prime[n]], 1, 0], {a, 1, Prime[n] - 1}, {b, 1, Prime[n] - 1}]], {n, 2, 20, 1}]

Neat Examples  (2)

Visualize when a number is invertible modulo 12:

Wolfram Language code: ArrayMesh[Boole[Table[NumberQ[ModularInverse[a + b ^ 2 + c ^ 3, 12]]//Quiet, {a, 10}, {b, 10}, {c, 10}]]]

Modular inverses of sums of two squares:

Wolfram Language code: ArrayPlot[Table[ModularInverse[a ^ 2 + b ^ 2, Prime[200]], {b, 100}, {a, 100}], ColorFunction -> "Pastel"]
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_2026_modularinverse, author="Wolfram Research", title="{ModularInverse}", year="2017", howpublished="\url{https://reference.wolfram.com/language/ref/ModularInverse.html}", note=[Accessed: 13-June-2026]}

BibLaTeX

@online{reference.wolfram_2026_modularinverse, organization={Wolfram Research}, title={ModularInverse}, year={2017}, url={https://reference.wolfram.com/language/ref/ModularInverse.html}, note=[Accessed: 13-June-2026]}