J, 3 bytes

%m.

J9.05 added the new modular arithmetic primitive, which reserves the monadic form for % and %. for returning the modular inverse. Throws a domain error if the inverse cannot be found.

This produces an adverb. b is the left arg and a is the right arg

APL(NARS), 66 chars

{1≠↑k←{(a b)←⍵⋄b=0:a,1,0⋄(g x y)←∇b,b∣a⋄g,y,x-y×⌊a÷b}⍵:0⋄⍵[2]∣2⊃k}

In input one array of 2 elements: the first is the value to invert as examples. If no solution find it should return 0. Test:

  f←{1≠↑k←{(a b)←⍵⋄b=0:a,1,0⋄(g x y)←∇b,b∣a⋄g,y,x-y×⌊a÷b}⍵:0⋄⍵[2]∣2⊃k}
  f 1 2
1
  f 3 6
0
  f 7 87
25
  f 13 91
0
  f 19 1212393831
701912218
  f 31 73714876143
45180085378
  f 3 73714876143
0

[Pyt], 1 byte

ɯ

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.

Python 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.

Explanation:

To quote the Python 3.8 release notes:

For integers, the three-argument form of the 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 of 38 modulo 137, write:

>>> pow(38, -1, 137)
119
>>> 119 * 38 % 137
1

Modular inverses arise in the solution of linear Diophantine equations. 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.)

Pari/GP, 11 bytes

a->b->1/a%b

Throws an error when there is no inverse.

Try it online!

APL (Dyalog Unicode), 36 38 bytes

{⌈/i×1=⍵|(i←⍳⍵)×⍵|⍺}

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

First iteration:

{((⍵|⍺),⍵){+/⌈/⍵×1=(¯1↑⍺)|⍵×⊃⍺}⍳⍵}

Pyth, 10 bytes

3 bytes saved thanks to @Jakube.

xm%*szdQQ1

Try it here!

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, 15 13 bytes

KEhfq1%*QTKSK

Throws an exception in case no multiplicative inverse exists.

Try it here!

Pyth, 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!

Python 2, 34 bytes

f=lambda a,b:a==1or-~b*f(-b%a,a)/a

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}\$.

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

C (gcc), 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!

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.

Jelly, 27 bytes

²%³
⁴Ç⁹Сx⁸
ÆṪ’BṚçL$P%³×gỊ¥

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.

J, 28 bytes

4 :'(1=x+.y)*x y&|@^<:5 p:y'

Try it online!

Uses Euler's 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

C (gcc), 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!

Extended Euclidean algorithm, recursive version

C (gcc), 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!

Extended Euclidean algorithm, iterative version

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

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)

8th, 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

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

• Saved 1 byte thanks to ETH pointing out an errant, and very obvious, space.

Python 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!

Prints 0 when there is no solution.

Python 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!

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>

Python 3, 49 bytes

lambda a,b:[c for c in range(b)if-~c*a%b==1][0]+1

Try it online!

Python 3, 50 bytes

lambda a,b:[c for c in range(1,b+1)if c*a%b==1][0]

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.

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

Python 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!

Taken from Jelly source code.

Python 3 + gmpy, 23 bytes

I don't think it can get any shorter in Python.

gmpy.invert
import gmpy

Try it online! (won't work if you do not have gmpy installed)

Mathematica, 18 bytes

PowerMod[#,-1,#2]&

input

[31, 73714876143]

Jelly, 2 bytes

æi

Try it online!

This uses a builtin for modular inverse, and returns 0 for no modular inverse.

Jelly, 7 bytes

R×%⁸’¬T

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!

How it Works

×⁴%³’¬ø1#
        #   Get the first
      ø1      one integer
            which meets:
×⁴            When multiplied by a
  %³          And modulo-d by b
    ’         Decrement
     ¬        Is falsy

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..

R + numbers, 15 bytes

numbers::modinv

returns NA for those a without inverses mod b.

R-Fiddle to try it!

R, 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!

Returns integer(0) (an empty list) for those a without inverses mod b.