class Integer

@!parse class Integer < Numeric; end

Public Instance Methods

inv(m = nil)

Alias for: inverse

inverse(m = nil) click to toggle source

Returns its inverse.

@overload inverse

@return [Rational] inverse

@overload inverse(m)

@param m [Integer] modulus
@return [Integer] modular multiplicative inverse
@raise [ArgumentError] if +m+ is not coprime to +self+

@example

63.inv        #=> (1/63)
63.inv * 63   #=> (1/1)

63.inv(100)              #=> 27
63.inv(100) * 63         #=> 1701
63.inv(100) * 63 % 100   #=> 1

64.inv(100)   #=> ArgumentError: modulus is not coprime to the receiver

# File lib/numeric_inverse/ext/integer.rb, line 25
def inverse(m = nil)
        return Rational(1, self) if m.nil?

        # extended Euclidean algorithm
        a, b, x, x0 = self, m, 1, 0
        until b.zero?
                a, (q, b) = b, a.divmod(b)
                x, x0 = x0, x - q * x0
        end

        # x is an inverse iff self.gcd(m) == 1
        if a.abs != 1
                raise ArgumentError,
                      "modulus is not coprime to the receiver"
        end

        x = -x if a < 0
        x % m   # 0 <= x < m || m < x <= 0
end

Also aliased as: inv