C++: Modular Inverse

From Wikipedia:

In modular arithmetic, the modular multiplicative inverse of an integer a modulo m is an integer x such that
$a\,x \equiv 1 \pmod{m}.$

Or in other words, such that:

$\exists k \in\mathbf{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.

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.

#include <iostream>
using namespace std;

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) {
cout<<mul_inv(42, 2017)<<endl;
return 0;
}


SOURCE

Content is available under GNU Free Documentation License 1.2.