[Question]
  [
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](https://en.wikipedia.org/wiki/Modular_multiplicative_inverse) 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 < c < 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 < a < 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 -> 1
3, 6 -> Does not exist
7, 87 -> 25
25, 87 -> 7
2, 91 -> 46
13, 91 -> Does not exist
19, 1212393831 -> 701912218
31, 73714876143 -> 45180085378
3, 73714876143 -> Does not exist
```
# Scoring
This is code golf, so the shortest code for each language wins.
[This](https://codegolf.stackexchange.com/questions/129716/compute-the-inverse-of-an-integer-modulo-100000000003) and [this](https://codegolf.stackexchange.com/questions/215/compute-modular-inverse?rq=1) are similar questions, but both ask for specific situations.
  
[Answer]
# Mathematica, 14 bytes
Obligatory Mathematica [builtin](https://reference.wolfram.com/language/ref/ModularInverse.html):
```
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.`.
[Answer]
# JavaScript (ES6), ~~79~~ ~~73~~ ~~62~~ 61 bytes
Returns `false` if the inverse does not exist. 
It uses the extended Euclidean algorithm and solves all test cases almost instantly.
```
f=(a,b,c=!(n=b),d=1)=>a?f(b%a,a,d,c-(b-b%a)/a*d):b<2&&(c+n)%n
```
### Test cases
```
f=(a,b,c=!(n=b),d=1)=>a?f(b%a,a,d,c-(b-b%a)/a*d):b<2&&(c+n)%n
console.log(f(1, 2)) // -> 1
console.log(f(3, 6)) // -> Does not exist
console.log(f(7, 87)) // -> 25
console.log(f(25, 87)) // -> 7
console.log(f(2, 91)) // -> 46
console.log(f(13, 91)) // -> Does not exist
console.log(f(19, 1212393831)) // -> 701912218
console.log(f(31, 73714876143)) // -> 45180085378
console.log(f(3, 73714876143)) // -> Does not exist
```
[Answer]
# [Python 2](https://docs.python.org/2/), 34 bytes
```
f=lambda a,b:a==1or-~b*f(-b%a,a)/a
```
[Try it online!](https://tio.run/##XY7BCsJADETvfkVAhFZSJEltdoX9mCyyKGhbSi9e/PW1Bytrj@8NzMz4mm9Dzzmn8LBnvBoYxouFQMPUvOMxVU08GFp9sjxO936GVBECQ73brywI3cIrKoLTgvm8FQieygKSr/kJj0BMLF6clIEs2ypKrdOOWtm8@EvyBw "Python 2 ‚Äì Try It Online")
Recursive function that gives `True` for `print f(1,2)`, which I believe to be acceptable, and errors for invalid inputs.
We are trying to find \$x\$ in \$a\cdot x\equiv 1\pmod{b}\$.
This can be written as \$a\cdot x-1=k\cdot b\$ where \$k\$ is an integer.
Taking \$\mod{a}\$ of this gives \$-1\equiv k\cdot b\pmod{a}\$. Moving the minus gives \$-k\cdot b\equiv1\pmod{a}\$, where we have to solve for \$k\$.
Seeing how it resembles the initial scenario, allow us to recurse to solve for \$k\$ by calling the function with \$f(-b\%a,a)\$ (works because Python gives positive values for modulo with a negative argument).
The program recurses for until \$a\$ becomes 1, which only happens if the original \$a\$ and \$b\$ are coprime to each other (ie there exists a multiplicative inverse), or ends in an error caused by division by 0.
This value of \$k\$ can be substituted in the equation \$a\cdot x-1=k\cdot b\$ to give \$x\$ as \$\frac{k\cdot b+1}{a}\$.
[Answer]
# [Jelly](https://github.com/DennisMitchell/jelly), 2 bytes
```
√¶i
```
[Try it online!](https://tio.run/##y0rNyan8///wssz/h5frP2paE/n/f7S5joV5rE60sY4ZkIRyjEyhtI6lIZAyNAbRAA "Jelly ‚Äì Try It Online")
This uses a builtin for modular inverse, and returns 0 for no modular inverse.
# [Jelly](https://github.com/DennisMitchell/jelly), 7 bytes
```
R√ó%‚Å∏‚Äô¬¨T
```
[Try it online!](https://tio.run/##y0rNyan8/z/o8HTVR407HjXMPLQm5P/h5Q76j5rWRP7/H22uY2EeqxNtrGMGJKEcI1MorWNpCKQMjUE0AA "Jelly ‚Äì Try It Online")
Outputs empty set (represented as empty string) on no modular inverse. Runs out of memory on TIO for the largest test-cases, but should work given enough memory.
**How it Works**
```
R√ó%‚Å∏‚Äô¬¨T  
R        Generate range of b
 √ó       Multiply each by a
  %‚Å∏     Mod each by b
    ‚Äô    Decrement (Map 1 to 0 and all else to truthy)
     ¬¨   Logical NOT
      T  Get the index of the truthy element.
```
If you want to work for larger test-cases, try this (relatively ungolfed) version, which requires much time rather than memory:
## Jelly, 9 bytes
```
√ó‚Å¥%¬≥‚Äô¬¨√∏1#
```
[Try it online!](https://tio.run/##AR8A4P9qZWxsef//w5figbQlwrPigJnCrMO4MSP///84N/83 "Jelly ‚Äì Try It Online")
**How it Works**
```
√ó‚Å¥%¬≥‚Äô¬¨√∏1#
        #   Get the first
      √∏1      one integer
            which meets:
√ó‚Å¥            When multiplied by a
  %¬≥          And modulo-d by b
    ‚Äô         Decrement
     ¬¨        Is falsy
```
[Answer]
# Mathematica, 18 bytes
```
PowerMod[#,-1,#2]&
```
**input**
> 
> [31, 73714876143]
> 
> 
> 
[Answer]
# [R](https://www.r-project.org/) + [numbers](https://cran.r-project.org/web/packages/numbers/numbers.pdf), 15 bytes
```
numbers::modinv
```
returns `NA` for those `a` without inverses mod `b`.
[R-Fiddle to try it!](http://www.r-fiddle.org/#/fiddle?id=l01inC73&version=1)
# [R](https://www.r-project.org/), 33 bytes (non-competing)
This will fail on very large `b` since it actually creates a vector of size `32*b` bits.
```
function(a,b)which((1:b*a)%%b==1)
```
[Try it online!](https://tio.run/##K/qfZvs/rTQvuSQzP08jUSdJszwjMzlDQ8PQKkkrUVNVNcnW1lDzf5qGuY6FueZ/AA "R ‚Äì Try It Online")
Returns `integer(0)` (an empty list) for those `a` without inverses mod `b`.
[Answer]
# [Japt](https://github.com/ETHproductions/japt/), ~~9~~ 8 bytes
Takes the inputs in reverse order. Outputs `-1` for no match. Craps out as the bigger integer gets larger.
```
√á*V%U√Éb1
```
[Test it](https://ethproductions.github.io/japt/?v=1.4.5&code=xypWJVXDYjE=&input=ODcsNw==)
* Saved 1 byte thanks to ETH pointing out an errant, and very obvious, space.
[Answer]
# [Python 3](https://docs.python.org/3/) + [gmpy](https://pypi.python.org/pypi/gmpy/1.17), 23 bytes
I don't think it can get any shorter in Python.
```
gmpy.invert
import gmpy
```
[Try it online!](https://tio.run/##K6gsycjPM/6fZhvzPz23oFIvM68staiEKzO3IL@oRAEk9L@gKDOvRCNNw1zHwlxT8z8A "Python 3 ‚Äì Try It Online") (won't work if you do not have gmpy installed)
[Answer]
# [Python 3](https://docs.python.org/3/), 49 bytes
```
lambda a,b:[c for c in range(b)if-~c*a%b==1][0]+1
```
[Try it online!](https://tio.run/##K6gsycjPM/6fZhvzPycxNyklUSFRJ8kqOlkhLb9IIVkhM0@hKDEvPVUjSTMzTbcuWStRNcnW1jA22iBW2/B/QVFmXolGmoa5joW5piYXjGukY2mIxDXWMdPU/A8A "Python 3 ‚Äì Try It Online")
# [Python 3](https://docs.python.org/3/), 50 bytes
```
lambda a,b:[c for c in range(1,b+1)if c*a%b==1][0]
```
[Try it online!](https://tio.run/##K6gsycjPM/6fZhvzPycxNyklUSFRJ8kqOlkhLb9IIVkhM0@hKDEvPVXDUCdJ21AzM00hWStRNcnW1jA22iD2f0FRZl6JRpqGuY6FuaYmF4xrpGNpiMQ11jHT1PwPAA "Python 3 ‚Äì Try It Online")
This throws `IndexError: list index out of range` in case there is no modular multiplicative inverse, as it is allowed by the rules.
[Answer]
# [Python 2](https://docs.python.org/2/), ~~51~~ ~~49~~ ~~54~~ ~~53~~ ~~51~~ 49 bytes
-1 byte thanks to officialaimm  
-1 byte thanks to Shaggy  
```
a,b=input()
i=a<2
while(a*i%b-1)*b%a:i+=1
print+i
```
[Try it online!](https://tio.run/##K6gsycjPM/r/P1EnyTYzr6C0REOTK9M20caIqzwjMydVI1ErUzVJ11BTK0k10SpT29aQq6AoM69EO/P/f3MdC3MA "Python 2 ‚Äì Try It Online")
Prints `0` when there is no solution.
[Answer]
# [8th](http://8th-dev.com/), 6 bytes
**Code**
```
invmod
```
**Explanation**
`invmod` is a 8th word that calculates the value of the inverse of `a`, modulo `b`. It returns `null` on overflow or other errors.
**Usage and test cases**
```
ok> 1 2 invmod .
1
ok> 3 6 invmod .
null
ok> 7 87 invmod .
25
ok> 25 87 invmod .
7
ok> 2 91 invmod .
46
ok> 13 91 invmod .
null
ok> 19 1212393831 invmod .
701912218
ok> 31 73714876143 invmod .
45180085378
ok> 3 73714876143 invmod .
null
```
[Answer]
# [J](http://jsoftware.com/), 28 bytes
```
4 :'(1=x+.y)*x y&|@^<:5 p:y'
```
[Try it online!](https://tio.run/##TYsxCoNAFAV7T/GqqBEi7//Vv7sqeJCQFCES0sTShdx9I1aBYWCKeee8YIpwiGXFaWsuqT5vSKfvfBtjhzWmsiiej9cHd0E1LG19BSFQ9DB4g3SHEQjq4QAKRYN6JXZMjc5bT6f79lc5/wA "J ‚Äì Try It Online")
Uses [Euler's theorem](https://en.wikipedia.org/wiki/Modular_multiplicative_inverse#Using_Euler.27s_theorem). Returns 0 if the inverse does not exist.
## Explanation
```
4 :'(1=x+.y)*x y&|@^<:5 p:y'  Input: a (LHS), b (RHS)
4 :'                       '  Define an explicit dyad - this is to use the special
                              form `m&|@^` to perform modular exponentiation
                          y   Get b
                      5 p:    Euler totient
                    <:        Decrement
             x                Get a
                   ^          Exponentiate
               y&|@             Modulo b
       x+.y                   GCD of a and b
     1=                       Equals 1
            *                 Multiply
```
[Answer]
# [Pyth](https://pyth.readthedocs.io), 10 bytes
*3 bytes saved thanks to [@Jakube](https://codegolf.stackexchange.com/users/29577/jakube)*.
```
xm%*szdQQ1
```
**[Try it here!](https://pyth.herokuapp.com/?code=xm%25%2aszdQQ1&input=3%0A6&test_suite=1&test_suite_input=87%0A7%0A%0A6%0A3%0A%0A87%0A25%0A&debug=0&input_size=3)**
Returns `-1` for no multiplicative inverse.
### Code Breakdown
```
xm%*szdQQ1      Let Q be the first input.
 m      Q       This maps over [0 ... Q) with a variable d.
   *szd         Now d is multiplied by the evaluated second input.
  %    Q        Now the remained modulo Q is retrieved.
x        1      Then, the first index of 1 is retrieved from that mapping.
```
# [Pyth](https://pyth.readthedocs.io), ~~15~~ 13 bytes
```
KEhfq1%*QTKSK
```
Throws an exception in case no multiplicative inverse exists.
**[Try it here!](https://pyth.herokuapp.com/?code=KEhfq1%25%2aQTKSK&input=3%0A6&test_suite=1&test_suite_input=7%0A87%0A%0A3%0A6%0A%0A25%0A87%0A&debug=0&input_size=3)**
# [Pyth](https://pyth.readthedocs.io), 15 bytes
```
Iq1iQKEfq1%*QTK
```
This adds lots of bytes for handling the case where no such number exists. The program can be shortened significantly if that case would not need to be handled:
```
fq1%*QTK
```
**[Try it here!](https://pyth.herokuapp.com/?code=Iq1iQKEfq1%25%2aQTK&input=7%0A87&test_suite=1&test_suite_input=7%0A87%0A%0A3%0A6%0A%0A25%0A87%0A&debug=0&input_size=3)**
[Answer]
# [Pari/GP](http://pari.math.u-bordeaux.fr/), 11 bytes
```
a->b->1/a%b
```
Throws an error when there is no inverse.
[Try it online!](https://tio.run/##K0gsytRNL/ifpmCr8D9R1y5J185QP1E16X9BUWZeiUaahrGhpoa5sbmhiYW5maGJsabmfwA "Pari/GP ‚Äì Try It Online")
[Answer]
# [C (gcc)](https://gcc.gnu.org/), 115 bytes
```
#define L long long
L g(L a,L b,L c,L d){return a?g(b%a,a,d-b/a*c,c):b-1?0:d;}L f(L a,L b){return(g(a,b,1,0)+b)%b;}
```
[Try it online!](https://tio.run/##bVHLbsIwEDzHX7ECIdllQ@OYEsAt/ECkHntoOdjOo5bSUIVwivzrTU1E2iL1sI9Z73pmbROWxvT9NMsLW@eQQnWsy8GRFEqagsIUtDfjLWNdk7fnpga1L6meKVSYhfpe3Rk0bKtDvo@2mXQpFOPkOEFLqlAjx4jNNZtp6fqprU11znJ4PLWZPS7ed4TYuoUPZWvKoCPBqW3OpoXuV5S/FLQEB@3rAZ4uPUEHHCEGh0MuEFZjniCskxHEDzcIYcNHwMUN2iDwmMdiI9bipyo8SSISvlwnK74Uf@j@qUYIETgSOEmC4tgAvaxlvd5IeuH2sFAS7Hw@7Bh8Nv60oJNZVWUIFw/hbohv9QSv/deo0b/sbYUxT@K5rh8TSeL6L1NUqjz14XPchy@qqr4B "C (gcc) ‚Äì Try It Online")
Extended Euclidean algorithm, recursive version
# [C (gcc)](https://gcc.gnu.org/), 119 bytes
```
long long f(a,b,c,d,t,n)long long a,b,c,d,t,n;{for(c=1,d=0,n=b;a;a=t)t=d-b/a*c,d=c,c=t,t=b%a,b=a;return b-1?0:(d+n)%n;}
```
[Try it online!](https://tio.run/##bVFNb8IwDD23v8JiQmpXlzUNo2VZ2E/YkcPGIR@URcrCVMKp6l9fFyrYQNrF9nux9Z4dle@UGga7dzsYQ5MIlKhQo0eX/vFXLOuafZsoTlDzAh2XTDDBfeq5zuWDuA9tXKHiHj2X0zDIBWu3/tg6kDl5KZ4Snbl06lg/3Bmn7FFv4fngtdnPPlZxbJyHT2FckkIXRwffHpWHDq6tgGTQg3/bAD/1RB0QhBJ6HGuKsLjUFUJdXUD5eIMQluQCCL1BSwRSkpIuaU1/WRpEKlqReV0tyJxeyf3DFggF9HHUszgK54LktJYJfgsWjJvNTDAwWTbuGH214bVJJlNrNcIpQr4a87ub4Ln/nCWGP7pl0jSIBK3zkQsW98O3aqzYHYb8tRzytbD2Bw "C (gcc) ‚Äì Try It Online")
Extended Euclidean algorithm, iterative version
[Answer]
# [C (gcc)](https://gcc.gnu.org/), ~~48 110~~ 104 bytes
```
#define f(a,b)g(a,b,!b,1,b)
long g(a,b,c,d,n)long a,b,c,d,n;{a=a?g(b%a,a,d,c-(b-b%a)/a*d):!--b*(c+n)%n;}
```
[Try it online!](https://tio.run/##fY1NDoIwEIX3nKJgSFqcRociBYnxAhzBTVt@QoLVGHeEsyNo4ooyi0ne@2beM7w1Zpp2Vd10tiYNVaBZu2zwNeAsvP5hW/KzDFRg2df4y2JQF3VtqQ4VqNkwnGo@C3ZQUcXOPuc6omZvWWiLcbqrzlI2eM9XZ98NDcK@r242gLkZIWaEFWtIQOpCEjLpYvFpC0KOLoZiAwrA4zLu7xwIxhiLXGTCHYNApJCYZDLFRJSlu2/lbpw@ "C (gcc) ‚Äì Try It Online")
This should work with all inputs (that fit within a long) within 60 seconds.
Edit. I'm already abusing the `n` variable so I might as well assume that gcc puts the first assignment in `%rax`.
[Answer]
# [APL (Dyalog Unicode)](https://www.dyalog.com/), 36 38 bytes
```
{‚åà/i√ó1=‚çµ|(i‚Üê‚ç≥‚çµ)√ó‚çµ|‚ç∫}
```
[Try it online!](https://tio.run/##SyzI0U2pTMzJT///v/pRT4d@5uHphraPerfWaGQ@apvwqHczkK15eDpI5FHvrtr/aWDRvkd9Uz39H3U1H1pv/KhtIpAXHOQMJEM8PIMV/hsqpCkYcRkDSTMucyBpYc5lZAqlgZSlIZehMYQGAA "APL (Dyalog Unicode) ‚Äì Try It Online")
Explanation:
```
                   ‚çµ|‚ç∫} ‚çù Get ‚ç∫ mod ‚çµ
             (i‚Üê‚ç≥‚çµ)√ó     ‚çù Multiply the result by all numbers up to ‚çµ
          ‚çµ|            ‚çù Take result mod ‚çµ
     i√ó1=                ‚çù Find all numbers (1,‚çµ) where the mod is 1
{‚åà/                      ‚çù And take the largest
```
Much thanks to Adam in the APL Orchard chatroom for the help with this one!
Formula obtained from [this site](https://www.geeksforgeeks.org/multiplicative-inverse-under-modulo-m/)
First iteration:
```
{((‚çµ|‚ç∫),‚çµ){+/‚åà/‚çµ√ó1=(¬Ø1‚Üë‚ç∫)|‚çµ√ó‚äÉ‚ç∫}‚ç≥‚çµ}
```
[Answer]
# [Python 3.8](https://docs.python.org/3.8/), 22 bytes
```
lambda a,b:pow(a,-1,b)
```
Obligatory Python 3.8+ builtin. Outputs the result, or gives the error `ValueError: base is not invertible for the given modulus` if there is no result.
[Try it online.](https://tio.run/##TY1BCsIwFET3niJ0ZeC7@Pm1SQruvEXtItEWC5qENKA9fUyli27mMTMwE5b09I5UiHm83PLLvO3DMAO2Df5zNHBCsDyPPq4ZmxzrOgTRQ0fQFJWgZIE4bwSNBUgbNaBAQZoUrZ4QJEmslWywpv/I3vftgbEUlzbEyaVybmFclfOSD9/7ENKuqq5@mJnzqVTTnCqefw)
**Explanation:**
To quote the [Python 3.8 release notes](https://docs.python.org/3.8/whatsnew/3.8.html#other-language-changes):
> 
> For integers, the three-argument form of the [pow()](https://docs.python.org/3.8/library/functions.html#pow) function now
> permits the exponent to be negative in the case where the base is
> relatively prime to the modulus. It then computes a modular inverse to
> the base when the exponent is -1, and a suitable power of that inverse
> for other negative exponents. For example, to compute the [modular
> multiplicative inverse](https://en.wikipedia.org/wiki/Modular_multiplicative_inverse) of 38 modulo 137, write:
> 
> 
> 
> ```
> >>> pow(38, -1, 137)
> 119
> >>> 119 * 38 % 137
> 1
> 
> ```
> 
> Modular inverses arise in the solution of [linear Diophantine equations](https://en.wikipedia.org/wiki/Diophantine_equation). For example, to find integer solutions for `4258ùë• + 147ùë¶ = 369`, first rewrite as `4258ùë• ‚â° 369 (mod 147)` then solve:
> 
> 
> 
> ```
> >>> x = 369 * pow(4258, -1, 147) % 147
> y = (4258 * x - 369) // -147
> 4258 * x + 147 * y
> 369
> 
> ```
> 
> (Contributed by Mark Dickinson in [bpo-36027](https://bugs.python.org/issue36027).)
> 
> 
> 
[Answer]
# [Pyt], 1 byte
```
…Ø
```
[Try it online!](https://tio.run/##K6gs@f//5Pr//y0NuQyNAQ "Pyt ‚Äì Try It Online")
Takes inputs in the order `b a` (on separate lines). Outputs `None` if there is no such multiplicate inverse. Gotta love built-ins.
[Answer]
# [Python 2](https://docs.python.org/2/) + sympy, 74 bytes
```
from sympy import*
def f(a,m):i,_,g=numbers.igcdex(a,m);return g==1and i%m
```
[Try it online!](https://tio.run/##TY/BCoMwGIPvPkUuA5WfQVtn1eGTjDHcrK6HtlIrzKd3KkN2ykcCCRnm8HaWL0vnncE4m2GGNoPzIY1a1aGLGzJJpelBfW0n81R@POv@1arPnly9CpO36OuaNbaFPpklqDGMqHGLGYEnhFgQ8k0loZAb8MtBhJJtwMRBJYFxxkUpCrE7Yi2SQrKskDnLxK/y37lHUec8NLTFvl9h8NqG9UCqk@UL "Python 2 ‚Äì Try It Online")
[Taken from Jelly source code.](https://github.com/DennisMitchell/jelly/blob/master/jelly.py#L467-L469)
[Answer]
# Axiom, 45 bytes
```
f(x:PI,y:PI):NNI==(gcd(x,y)=1=>invmod(x,y);0)
```
0 for error else return z with x\*z Mod y =1
[Answer]
# [Python 2](https://docs.python.org/2/), 52 bytes
*-3 bytes thanks to Mr. Xcoder.*
```
f=lambda a,b,i=1:i*a%b==1and i or i<b and f(a,b,i+1)
```
[Try it online!](https://tio.run/##PY3BCsIwEETv/Yq5CEndy6ZotbhfIh4SanBB09Lm4tdHU8HTvIHhzfzOjym5UqI8/SuMHp4CqfCgrd8FEfZphGJaoJeAWqLZJnu2Jd/XvEJwNUxwlmA6wrFmTzj1FdzhT4QzV@DuR7emidULTdhMA@ZFU/4@tGrLBw "Python 2 ‚Äì Try It Online")
Outputs `False` on no solution and errors out as `b` gets larger.
## Embedded TIO
I'm just testing out iframes in Stack Snippets and they work absolutely fantastic.
```
html,body{height:100%;}iframe{height:100%;width:100%;border:none;}
```
```
<iframe src="https://tio.run/##PY3BCsIwEETv/Yq5CEndy6ZotbhfIh4SanBB09Lm4tdHU8HTvIHhzfzOjym5UqI8/SuMHp4CqfCgrd8FEfZphGJaoJeAWqLZJnu2Jd/XvEJwNUxwlmA6wrFmTzj1FdzhT4QzV@DuR7emidULTdhMA@ZFU/4@tGrLBw"></iframe>
```
[Answer]
# JavaScript (ES6), ~~42~~ ~~41~~ ~~39~~ 38 bytes
Outputs `false` for no match. Will throw a overflow error as the second number gets to be too large.
```
x=>y=>(g=z=>x*z%y==1?z:z<y&&g(++z))(1)
```
[Answer]
# [Jelly](https://github.com/DennisMitchell/jelly), 27 bytes
```
¬≤%¬≥
‚Å¥√á‚Åπ√ê¬°x‚Å∏
√Ü·π™‚ÄôB·πö√ßL$P%¬≥√óg·ªä¬•
```
[Try it online!](https://tio.run/##AUsAtP9qZWxsef//wrIlwrMK4oG0w4figbnDkMKheOKBuArDhuG5quKAmULhuZrDp0wkUCXCs8OXZ@G7isKl////NzM3MTQ4NzYxNDP/MzE "Jelly ‚Äì Try It Online")
Uses Euler's theorem with modular exponentiation. Since Jelly doesn't have a builtin to perform modular exponentiation, it had to be implemented, and it took most of the bytes.
[Answer]
# Axiom, 99 bytes
```
w(a,b,x,u)==(a=0=>(b*b=1=>b*x;0);w(b rem a,a,u,x-u*(b quo a)));h(a,b)==(b=0=>0;(b+w(a,b,0,1))rem b)
```
it use the function h(); h(a,b) return 0 if error [not exist inverse] otherwise
it return the z such that a\*z mod b = 1
This would be ok even if arguments are negative...
this would be the general egcd() function that retunr a list of int (so they can be negative too)
```
egcd(aa:INT,bb:INT):List INT==
   x:=u:=-1   -- because the type is INT
   (a,b,x,u):=(aa,bb,0,1)
   repeat
      a=0=>break
      (q,r):=(b quo a, b rem a)
      (b,a,x,u):=(a,r,u,x-u*q)
   [b,x, (b-x*aa)quo bb]
```
this is how use it
```
(7) -> h(31,73714876143)
   (7)  45180085378
                                                    Type: PositiveInteger
```
i find the base algo in internet from <https://pastebin.com/A13ybryc>
]