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.

C

<lang c>#include <stdio.h>

int mul_inv(int a, int b) { int b0 = b, t, q; int x0 = 0, x1 = 1; if (b == 1) return 1; while (a > 1) { q = a / b; t = b, b = a % b, a = t; t = x0, x0 = x1 - q * x0, x1 = t; } if (x1 < 0) x1 += b0; return x1; }

int main(void) { printf("%d\n", mul_inv(42, 2017)); return 0; }</lang>

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>