There's actually a fairly pretty solution. Bezout's identity tells us that for any integers $x$ and $y$ not both zero, there exist integers $a$ and $b$ such that a linear combination gives the greatest common divisor of $x$ and $y$. $$ax + by = gcd(x,y).$$ Matlab actually gives us hooks to compute $a$ and $b$ in it's gcd function:
>> help gcd
GCD Greatest common divisor.
G = GCD(A,B) is the greatest common divisor of corresponding elements
of A and B. The arrays A and B must contain integer values and must be
the same size (or either can be scalar). GCD(0,0) is 0 by convention;
all other GCDs are positive integers.
[G,C,D] = GCD(A,B) also returns C and D so that G = A.*C + B.*D.
These are useful for solving Diophantine equations and computing
Here's my implementation in Matlab:
function xInv = modInv(x,n)
% ModInv(x,n) computes the multiplicative inverse of x modulo n if one
% exists; errors if no such inverse exists
if gcd(x,n) ~= 1
error('x has no inverse modulo n')
[d, a, b] = gcd(x,n);
xInv = mod(a,n);