Modular inverse
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 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)
Python
Implementation of this pseudocode with this. <lang python>>>> def extended_gcd(aa, bb):
a, b = abs(aa), abs(bb) x, lastx, y, lasty = 0, 1, 1, 0 while b: a, (quotient, b) = b, divmod(a, b) x, lastx = lastx - quotient*x, x y, lasty = lasty - quotient*y, y return a, lastx * (-1 if aa < 0 else 1), lasty * (-1 if bb < 0 else 1)
>>> def modinv(a, m): g, x, y = extended_gcd(a, m) if g != 1: raise ValueError return x % m
>>> modinv(42, 2017) 1969 >>> </lang>