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.

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

Content is available under GNU Free Documentation License 1.2.