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.