ModularInverse

The $x$ with $a x \equiv 1 \pmod m$, when $a$ is a unit mod $m$.

✓ checked against that system · ! checked, with disagreements (hover a chip)Wolfram LanguageModularInverse!↗

ModularInverse(a, m)the inverse of $a$ modulo $m$, in $[0, m)$

SageMathenumeratio_inverse_mod(a, m)SymPymod_inverse(a, m)Oscarinvmod(ZZ(a), ZZ(m))Juliainvmod(ZZ(a), ZZ(m))Rustmod_inverse(a, m)

ModularInverse(z, m)over the Gaussian integers

SageMathenumeratio_inverse_mod(z, m)SymPymod_inverse(z, m)Oscarinvmod(ZZ(z), ZZ(m))Juliainvmod(ZZ(z), ZZ(m))Rustmod_inverse(z, m)

Typed signatures

Type	Package	Applies
(integer, integer) -> integer	compute-engine	always
(number, number) -> number	number-theoryreplaces compute-engine	always

Domain: Modular arithmetic

Details

• Exists exactly when $\gcd(a, m)$ is a unit; the call is otherwise left unevaluated.
• Read off the Bézout coefficient of ExtendedGCD.
• For Gaussian integers, Wolfram reduces the inverse into $[0, m)$ part by part for a positive rational-integer $m$, and as Mod does otherwise.

Plot

Examples

24 more kept as data, checked against the oracles

Basic #

$3 \cdot 5 = 15 \equiv 1$

live ↗

In$\mathrm{ModularInverse}(3, 7)$Out$5$

live ↗

In$\mathrm{ModularInverse}(2, 11)$Out$6$

$3\cdot2\equiv1 \pmod5$

live ↗

In$\mathrm{ModularInverse}(3, 5)$Out$2$

Scope #

a negative argument: $-3 \cdot 2 = -6 \equiv 1$

live ↗

In$\mathrm{ModularInverse}(-3, 7)$Out$2$

a 21-digit modulus

live ↗

In$\mathrm{ModularInverse}(3, 10^{20}+1)$Out$33\,333\,333\,333\,333\,333\,334$

Listable: threads over a list

live ↗

In$\mathrm{ModularInverse}(\bigl\lbrack2, 3, 4\bigr\rbrack, 11)$Out$\bigl\lbrack6, 4, 3\bigr\rbrack$

$(2 + i)(6 + 4i) = 8 + 14i \equiv 1 \pmod 7$

live ↗

In$\mathrm{ModularInverse}(2+i, 7)$Out$6+4i$

live ↗

In$\mathrm{ModularInverse}(11-7i, 7+4i)$Out$-1+2i$

Negative input is reduced first: $-5\equiv2$, and $2\cdot4\equiv1 \pmod7$

live ↗

In$\mathrm{ModularInverse}(-5, 7)$Out$4$

Enormous power inverted modulo a prime without forming it

live ↗

In$\mathrm{ModularInverse}(10^{100\,000}, \mathrm{NextPrime}(1\,000))$Out$942$

Properties #

the same as PowerMod with exponent $-1$

live ↗

In$\mathrm{ModularInverse}(3, 7)=\mathrm{PowerMod}(3, -1, 7)$Out$\mathrm{True}$

$a \cdot a^{-1} \equiv 1$, modulo the Mersenne prime $2^{61} - 1$

live ↗

In$12\,345\mathrm{ModularInverse}(12\,345, 2^{61}-1)\bmod(2^{61}-1)$Out$1$

Congruent inputs ($2\equiv7$) have the same inverse

live ↗

In$\bigl\lbrack\mathrm{ModularInverse}(2, 5), \mathrm{ModularInverse}(7, 5)\bigr\rbrack$Out$\bigl\lbrack3, 3\bigr\rbrack$

Agrees with PowerMod at exponent $-1$

live ↗

In$\bigl\lbrack\mathrm{ModularInverse}(3, 5), \mathrm{PowerMod}(3, -1, 5)\bigr\rbrack$Out$\bigl\lbrack2, 2\bigr\rbrack$

$5\cdot3=15\equiv1 \pmod7$

live ↗

In$\mathrm{ModularInverse}(5, 7)$Out$3$

A negative modulus gives a result in the negative range

live ↗

In$\mathrm{ModularInverse}(5, -7)$Out$-4$

$7\cdot7=49\equiv1 \pmod{12}$: self-inverse

live ↗

In$\mathrm{ModularInverse}(7, 12)$Out$7$

Inverting twice returns the original residue

live ↗

In$\mathrm{ModularInverse}(\mathrm{ModularInverse}(7, 9), 9)$Out$7$

Possible issues #

$\gcd(2, 4) = 2$: no inverse

live ↗

In$\mathrm{ModularInverse}(2, 4)$Out$\mathrm{ModularInverse}(2, 4)$

$10\cdot19=190\equiv1 \pmod{21}$

live ↗

In$\mathrm{ModularInverse}(10, 21)$Out$19$

Order matters: $21\equiv1 \pmod{10}$, so the inverse is $1$

live ↗

In$\mathrm{ModularInverse}(21, 10)$Out$1$

About

Examples	45
Checked against	Wolfram Language 44 agree1 differSageMath 38 agree7 errorSymPy 18 agree4 differ23 errorOscar 15 agreeJulia 19 agree26 errorRust 19 agree2 differ1 error
Crosswalk	Wolfram LanguageSageMathSymPyOscarJuliaRust

Implementation

mappedoscarpackages/oracle/src/mappings.ts

mappedwolframpackages/oracle/src/mappings.ts

Wolfram's own ModularInverse (not PowerMod[a, -1, m]): PowerMod's negative-exponent path checks invertibility of a mod the NORM of a Gaussian m, not m itself, and wrongly declines some invertible cases ModularInverse gets right — e.g. ModularInverse(11 - 7i, 7 + 4i) = -1 + 2i, where PowerMod[11 - 7I, -1, 7 + 4I] errors because 11 - 7i shares a factor with N(7 + 4i) = 65.

mappedsagepackages/oracle/src/mappings.ts

mappedsympypackages/oracle/src/mappings.ts

SymPy's mod_inverse raises where no inverse exists, and for a negative modulus gives a result in (m, 0] as ours does. It reads a non-integer argument (a Gaussian integer) as an ordinary number rather than reducing it in the Gaussian integers.

mappedjuliapackages/oracle/src/mappings.ts

mappedrustpackages/oracle/src/mappings.ts

See also: PowerMod, ExtendedGCD, PowerModList