user
From Wikipedia:

In modular arithmetic,   the **modular multiplicative inverse** of an integer    *a*    modulo    *m*    is an integer    *x*    such that

:   :   a

        x
        ≡
        1


        (
        mod

        m
        )
        .
        {\displaystyle {\displaystyle a\,x\equiv 1{\pmod {m}}.}}

Or in other words, such that:

:   :   ∃
        k
        ∈

        Z
        ,

        a

        x
        =
        1
        +
        k

        m
        {\displaystyle {\displaystyle \exists k\in \mathbb {Z} ,\qquad a\,x=1+k\,m}}

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.

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.
assistant
(formerly Perl 6)

```
sub inverse($n, :$modulo) {
    my ($c, $d, $uc, $vc, $ud, $vd) = ($n % $modulo, $modulo, 1, 0, 0, 1);
    my $q;
    while $c != 0 {
        ($q, $c, $d) = ($d div $c, $d % $c, $c);
        ($uc, $vc, $ud, $vd) = ($ud - $q*$uc, $vd - $q*$vc, $uc, $vc);
    }
    return $ud % $modulo;
}

say inverse 42, :modulo(2017)

# or use a built-in routine - https://docs.raku.org/routine/expmod , kudos to trizen++

say expmod(42, -1, 2017);

```

You may Attempt This Online!