Modular multiplicative inverse Your task is to given two integer numbers, a and b calculate the modular multiplicative inverse of a modulo b, if it exists.

The modular inverse of a modulo b is a number c such that ac ≡ 1 (mod b). This number is unique modulo b for any pair of a and b. It exists only if the greatest common divisor of a and b is 1.

The Wikipedia page for modular multiplicative inverse can be consulted if you require more information about the topic.

Input and Output

Input is given as either two integers or a list of two integers. Your program should output either a single number, the modular multiplicative inverse that is in the interval 0 &lt; c &lt; b, or a value indicating there is no inverse. The value can be anything, except a number in the range (0,b), and may also be an exception. The value should however be the same for cases in which there is no inverse.

0 &lt; a &lt; b can be assumed

Rules


The program should finish at some point, and should solve each test case in less than 60 seconds
Standard loopholes apply


Test cases

Test cases below are given in the format, a, b -> output

1, 2 -&gt; 1
3, 6 -&gt; Does not exist
7, 87 -&gt; 25
25, 87 -&gt; 7
2, 91 -&gt; 46
13, 91 -&gt; Does not exist
19, 1212393831 -&gt; 701912218
31, 73714876143 -&gt; 45180085378
3, 73714876143 -&gt; Does not exist


Scoring

This is code golf, so the shortest code for each language wins.

This and this are similar questions, but both ask for specific situations.
Mathematica, 14 bytes

Obligatory Mathematica builtin:

ModularInverse


It's a function that takes two arguments (a and b), and returns the inverse of a mod b if it exists. If not, it returns the error ModularInverse: a is not invertible modulo b..