- 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.
Examplesopen allclose all
Basic Examples (2)
Compute the inverse of 3 modulo 5 and check the result:
Plot the sequence with a fixed modulus:
Numerical Manipulation (2)
Compute using integers:
Compute using large integers:
Basic Applications (2)
Two numbers are modular inverses of each other if their product is 1:
Modular computation of a matrix inverse:
First compute the matrix adjoint:
Then compute the modular inverse of a matrix:
Check that the inverse gives the correct result:
Number Theory (2)
Build an RSA-like toy encryption scheme. Start with the modulus:
Find the universal exponent of the multiplication group modulo n:
Encrypt a message:
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