# coding: utf-8

class ZpZ:
    def __init__(self, p):
        self._p = p
    def __repr__(self):
        return "Z/{}Z".format(self._p)
    def __call__(self, x):
        return ZpZ_elt(x, self._p)
    
class ZpZ_elt:
    def __init__(self, x, p):
        self._p = p
        self._x = x % p
    def __repr__(self):
        return "{} (mod {})".format(self._x, self._p)
    def __neg__(self):
        return self.__class__((-self._x)%self._p, self._p)
    def __add__(self, other):
        if self._p != other._p:
            raise ValueError("Eléments de corps différents.")
        return self.__class__((self._x + other._x) % self._p, self._p)
    def __sub__(self, other):
        return self + (-other)
    def __mul__(self, other):
        if self._p != other._p:
            raise ValueError("Eléments de corps différents.")
        return self.__class__((self._x * other._x) % self._p, self._p)
    def __eq__(self, other):
        return self._p == other._p and self._x == other._x
    def inverse(self):
        if self._x == 0:
            raise ZeroDivisionError("0 n'est pas inversible !")
        r0 = self._p
        r1 = self._x
        u0 = v1 = 1
        u1 = v0 = 0
        while r1 > 1:
            q = r0 // r1
            r0, r1 = r1, r0 - q * r1
            u0, u1 = u1, u0 - q * u1
            v0, v1 = v1, v0 - q * v1
        return self.__class__(v1 % self._p, self._p)
    def __truediv__(self, other):
        return self * other.inverse()
    def field(self):
        return ZpZ(self._p)