Having gcd() in the math module has been nice.  Here is another number theory basic that I've needed every now and then:


    def multinv(modulus, value):
        '''Multiplicative inverse in a given modulus

            >>> multinv(191, 138)
            18
            >>> 18 * 138 % 191
            1

            >>> multinv(191, 38)
            186
            >>> 186 * 38 % 191
            1

            >>> multinv(120, 23)
            47
            >>> 47 * 23 % 120
            1

        '''
        # https://en.wikipedia.org/wiki/Modular_multiplicative_inverse
        # http://en.wikipedia.org/wiki/Extended_Euclidean_algorithm
        x, lastx = 0, 1
        a, b = modulus, value
        while b:
            a, q, b = b, a // b, a % b
            x, lastx = lastx - q * x, x
        result = (1 - lastx * modulus) // value
        if result < 0:
            result += modulus
        assert 0 <= result < modulus and value * result % modulus == 1
        return result