pracma (version 1.1.6)

modinv: Modular Inverse

Description

Computes the modular inverse of n modulo m.

Usage

modinv(n, m)

Arguments

n, m

integer scalars

Value

• a natural number smaller m, if n and m are coprime, else NA.

Details

The modular inverse of n modulo m is the unique natural number 0 < n0 < m such that n * n0 = 1 mod m.

See Also

extGCD

Examples

modinv(5, 1001)  #=> 801, as 5*801 = 4005 = 1 mod 1001

Modinv <- Vectorize(modinv, "n")
mod((1:10)*Modinv(1:10, 11), 11)  #=> 1 1 1 1 1 1 1 1 1 1