numbers (version 0.7-1)

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

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

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