Modular arithmetic is a form of arithmetic (a calculation technique involving the concepts of addition and multiplication) which is done on numbers with a defined equivalence relation called congruence.

For any positive integer 



p


{\displaystyle p}

 called the congruence modulus,
two numbers 



a


{\displaystyle a}

 and 



b


{\displaystyle b}

 are said to be congruent modulo p whenever there exists an integer 



k


{\displaystyle k}

 such that:





a
=
b
+
k

p


{\displaystyle a=b+k\,p}


The corresponding set of equivalence classes forms a ring denoted 






Z


p

Z






{\displaystyle {\frac {\mathbb {Z} }{p\mathbb {Z} }}}

.

Addition and multiplication on this ring have the same algebraic structure as in usual arithmetics, so that a function such as a polynomial expression could receive a ring element as argument and give a consistent result.

The purpose of this task is to show, if your programming language allows it,
how to redefine operators so that they can be used transparently on modular integers.
You can do it either by using a dedicated library, or by implementing your own class.

You will use the following function for demonstration:





f
(
x
)
=

x

100


+
x
+
1


{\displaystyle f(x)=x^{100}+x+1}


You will use 



13


{\displaystyle 13}

 as the congruence modulus and you will compute 



f
(
10
)


{\displaystyle f(10)}

.

It is important that the function 



f


{\displaystyle f}

 is agnostic about whether or not its argument is modular; it should behave the same way with normal and modular integers.
In other words, the function is an algebraic expression that could be used with any ring, not just integers.




Module Module1
 
    Interface IAddition(Of T)
        Function Add(rhs As T) As T
    End Interface
 
    Interface IMultiplication(Of T)
        Function Multiply(rhs As T) As T
    End Interface
 
    Interface IPower(Of T)
        Function Power(pow As Integer) As T
    End Interface
 
    Interface IOne(Of T)
        Function One() As T
    End Interface
 
    Class ModInt
        Implements IAddition(Of ModInt), IMultiplication(Of ModInt), IPower(Of ModInt), IOne(Of ModInt)
 
        Sub New(value As Integer, modulo As Integer)
            Me.Value = value
            Me.Modulo = modulo
        End Sub
 
        ReadOnly Property Value As Integer
        ReadOnly Property Modulo As Integer
 
        Public Function Add(rhs As ModInt) As ModInt Implements IAddition(Of ModInt).Add
            Return Me + rhs
        End Function
 
        Public Function Multiply(rhs As ModInt) As ModInt Implements IMultiplication(Of ModInt).Multiply
            Return Me * rhs
        End Function
 
        Public Function Power(pow_ As Integer) As ModInt Implements IPower(Of ModInt).Power
            Return Pow(Me, pow_)
        End Function
 
        Public Function One() As ModInt Implements IOne(Of ModInt).One
            Return New ModInt(1, Modulo)
        End Function
 
        Public Overrides Function ToString() As String
            Return String.Format("ModInt({0}, {1})", Value, Modulo)
        End Function
 
        Public Shared Operator +(lhs As ModInt, rhs As ModInt) As ModInt
            If lhs.Modulo <> rhs.Modulo Then
                Throw New ArgumentException("Cannot add rings with different modulus")
            End If
            Return New ModInt((lhs.Value + rhs.Value) Mod lhs.Modulo, lhs.Modulo)
        End Operator
 
        Public Shared Operator *(lhs As ModInt, rhs As ModInt) As ModInt
            If lhs.Modulo <> rhs.Modulo Then
                Throw New ArgumentException("Cannot multiply rings with different modulus")
            End If
            Return New ModInt((lhs.Value * rhs.Value) Mod lhs.Modulo, lhs.Modulo)
        End Operator
 
        Public Shared Function Pow(self As ModInt, p As Integer) As ModInt
            If p < 0 Then
                Throw New ArgumentException("p must be zero or greater")
            End If
 
            Dim pp = p
            Dim pwr = self.One()
            While pp > 0
                pp -= 1
                pwr *= self
            End While
            Return pwr
        End Function
    End Class
 
    Function F(Of T As {IAddition(Of T), IMultiplication(Of T), IPower(Of T), IOne(Of T)})(x As T) As T
        Return x.Power(100).Add(x).Add(x.One)
    End Function
 
    Sub Main()
        Dim x As New ModInt(10, 13)
        Dim y = F(x)
        Console.WriteLine("x ^ 100 + x + 1 for x = {0} is {1}", x, y)
    End Sub
 
End Module