C++: Modular Inverse

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;
}