def inverse(n)
      raise ArgumentError, '0 has no multiplicative inverse.' if n.zero?

      # For every i, we make sure that num * s[i] + prime * t[i] = r[i].
      # Eventually r[i] will equal 1 because gcd(num, prime) is always 1.
      # At that point, s[i] is the multiplicative inverse of num in the field.

      remainders = [n, prime]
      s = [1, 0]
      t = [0, 1]
      arrays = [remainders, s, t]
      while remainders.last > 0
        quotient = remainders[-2] / remainders[-1]
        arrays.each do |array|
          array << array[-2] - quotient * array[-1]
        end
      end

      raise 'Inversion bug: remainder is not 1.' if remainders[-2] != 1
      mod s[-2]
    end
def inverse(n)
      raise ArgumentError, '0 has no multiplicative inverse.' if n.zero?

      # For every i, we make sure that num * s[i] + prime * t[i] = r[i].
      # Eventually r[i] will equal 1 because gcd(num, prime) is always 1.
      # At that point, s[i] is the multiplicative inverse of num in the field.

      remainders = [n, prime]
      s = [1, 0]
      t = [0, 1]
      arrays = [remainders, s, t]
      while remainders.last > 0
        quotient = remainders[-2] / remainders[-1]
        arrays.each do |array|
          array << array[-2] - quotient * array[-1]
        end
      end

      raise 'Inversion bug: remainder is not 1.' if remainders[-2] != 1
      mod s[-2]
    end
Computes the multiplicative inverse of a field element using the
 [Extended Euclidean Algorithm](http://en.wikipedia.org/wiki/Extended_Euclidean_algorithm).

 @param n (Integer)
 @return (Integer) integer `inv` such that `(inv * num) % prime` is one.