Problem Statement

From Wikipedia: In modular arithmetic,   the modular multiplicative inverse of an integer   a   modulo   m   is an integer   x   such that Or in other words, such that: It can be shown that such an inverse exists   if and only if   a   and   m   are coprime,   but we will ignore this for this task.

Either by implementing the algorithm, by using a dedicated library or by using a built-in function in your language,   compute the modular inverse of   42 modulo 2017.

Let's start with the solution:

modInverse: function [a,b][
    if b = 1 -> return 1

    b0: b   x0: 0   x1: 1
    z: a

    while [z > 1][
        q: z / b        t: b
        b: z % b        z: t
        t: x0           x0: x1 - q * x0
        x1: t
    ]
    (x1 < 0) ? -> x1 + b0 
               -> x1
]

print modInverse 42 2017