Modular inverse

Modular inverse is a draft programming task. It is not yet considered ready to be promoted as a complete task, for reasons that should be found in its talk page.

From Wikipedia:

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

$a^{-1}\equiv x{\pmod {m}}.$

Or in other words, such that

$a\,x\equiv 1{\pmod {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.

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

Java

The BigInteger library has a method for this: <lang java>System.out.println(BigInteger.valueOf(42).modInverse(BigInteger.valueOf(2017)));</lang>

Output:

1969

Perl

The modular inverse is not a perl builtin but there is a CPAN module who does the job.

<lang perl>use Math::ModInt qw(mod); print mod(42, 2017)->inverse</lang>

Output:

mod(1969, 2017)