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>usingnamespace std;
intmul_inv(int a, int b)
{
int b0 = b, t, q;
int x0 =0, x1 =1;
if (b ==1) return1;
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;
}
intmain(void) {
cout<<mul_inv(42, 2017)<<endl;
return0;
}