Problem Statement

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: The corresponding set of equivalence classes forms a ring denoted

Z

p

Z

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

. When p is a prime number, this ring becomes a field denoted

F

p

{\displaystyle \mathbb {F} _{p}}

, but you won't have to implement the multiplicative inverse for this task. Addition and multiplication on this ring have the same algebraic structure as in usual arithmetic, 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: 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.

Let's start with the solution:

// Semi-abstract though we can define a 'pow' method in terms of the other operations.
class Ring {
    +(other) {}
    *(other) {}
    one      {}

    pow(p) {
        if (p.type != Num || !p.isInteger || p < 0) {
            Fiber.abort("Argument must be non-negative integer.")
        }
        var pwr = one
        while (p > 0) {
            pwr = pwr * this
            p = p - 1
        }
        return pwr
    }
}

class ModInt is Ring {
    construct new(value, modulo) {
        _value = value
        _modulo = modulo
    }

    value  { _value }
    modulo { _modulo }

    +(other) {
        if (other.type != ModInt || _modulo != other.modulo) {
            Fiber.abort("Argument must be a ModInt with the same modulus.")
        }
        return ModInt.new((_value + other.value) % _modulo, _modulo)
    }

    *(other) {
        if (other.type != ModInt || _modulo != other.modulo) {
            Fiber.abort("Argument must be a ModInt with the same modulus.")
        }
        return ModInt.new((_value * other.value) % _modulo, _modulo)
    }

    one { ModInt.new(1, _modulo) }

    toString { "Modint(%(_value), %(_modulo))" }
}

var f = Fn.new { |x|
    if (!(x is Ring)) Fiber.abort("Argument must be a Ring.")
    return x.pow(100) + x + x.one
}

var x = ModInt.new(10, 13)
System.print("x^100 + x + 1 for x = %(x) is %(f.call(x))")