({{, (RefLink[ModularInverse, paclet:ref/ModularInverse])[k,n] 
gives the modular inverse of k modulo n.}})

OpenersNotesSection(Spacer1)Details

(RefLink[ModularInverse, paclet:ref/ModularInverse])[k,n] gives the number r such that (RefLink[Mod, paclet:ref/Mod])[r k,n]==1.

If k and n are not coprime, so no modular inverse exists, (RefLink[ModularInverse, paclet:ref/ModularInverse])[k,n] remains unevaluated.

OpenersPrimaryExamplesSection(Spacer1)Examples  (9)

OpenersExampleSection0(Spacer1)Basic Examples  (1)

Find the modular inverse of 3 modulo 5:

ModularInverse[3,5]

Check the result:

Mod[2 3,5]

OpenersExampleSection1(Spacer1)Scope  (2)

Compute the multiplicative inverse of 3 modulo 7:

ModularInverse[3,7]

Check the result:

Mod[3 5,7]

(RefLink[ModularInverse, paclet:ref/ModularInverse]) works with Gaussian as well as ordinary integers:

ModularInverse[3-I,5+2I]

Check the result:

Mod[(-1-I)(3-I),5+2I]

OpenersExampleSection3(Spacer1)Properties & Relations  (5)

(RefLink[ModularInverse, paclet:ref/ModularInverse]) is a special case of (RefLink[PowerMod, paclet:ref/PowerMod]) wherein the exponent is -1:

ModularInverse[3,5]

PowerMod[3,-1,5]

(RefLink[ModularInverse, paclet:ref/ModularInverse]) can also be computed by extracting a multiplier from (RefLink[ExtendedGCD, paclet:ref/ExtendedGCD]):

ModularInverse[3,5]

ExtendedGCD[3,5][[2,1]]

For prime p, every nonzero integer k has modular inverse modulo p, unless k is a multiple of p:

ModularInverse[12,7]

ModularInverse[14,7]

For nonzero integers k and n, (RefLink[ModularInverse, paclet:ref/ModularInverse])[k,n] exists if and only if k and n are coprime:

CoprimeQ[10,21]

ModularInverse[10,21]

ModularInverse[21,10]

However, 10 and 22 are not coprime:

CoprimeQ[10,22]

ModularInverse[10,22]

ModularInverse[22,10]

(RefLink[MultiplicativeOrder, paclet:ref/MultiplicativeOrder])[k,n] gives the smallest integer m such that (k^m)==1 mod n:

MultiplicativeOrder[7,108]

Therefore, (RefLink[Mod, paclet:ref/Mod])[(k^(m-1)),n] coincides with (RefLink[ModularInverse, paclet:ref/ModularInverse])[k,n]:

Mod[7^17,108]

ModularInverse[7,108]

OpenersExampleSection4(Spacer1)Possible Issues  (1)

Modular inverses may not exist:

ModularInverse[2,6]

({{DocumentationFooterIconsRelatedFunction.png, ({{See Also}, {(RefLink[PowerMod, paclet:ref/PowerMod])  ▪  (RefLink[Mod, paclet:ref/Mod])  ▪  (RefLink[Power, paclet:ref/Power])  ▪  (RefLink[PowerModList, paclet:ref/PowerModList])  ▪  (RefLink[ExtendedGCD, paclet:ref/ExtendedGCD])  ▪  (RefLink[MultiplicativeOrder, paclet:ref/MultiplicativeOrder])  ▪  (RefLink[EulerPhi, paclet:ref/EulerPhi])  ▪  (RefLink[PrimitiveRoot, paclet:ref/PrimitiveRoot])}})}})

({{DocumentationFooterIconsRelatedGuide.png, ({{Related Guides}, {▪(RefLinkPlain[Number Theory, paclet:guide/NumberTheory])}, {▪(RefLinkPlain[Number Theoretic Functions, paclet:guide/NumberTheoreticFunctions])}, {▪(RefLinkPlain[Numerical Functions, paclet:guide/NumericalFunctions])}, {▪(RefLinkPlain[Integer Functions, paclet:guide/IntegerFunctions])}})}})