function ainv = ModInvSym(a,n)
% ainv = ModInvSym(a,n)
% Modification of the ModInv function (using rhw gcdSym function) that
% has symbolic functionality.
%Input:  a = an integer mod n, and n, an integer modulus
%Output: ainv = the multiplicative inverse of a mod n, if this inverse
%exists, otherwise will produce an error message.
[d x y] = gcdSym(a,n);
if d ~= 1, error('The number given is not relatively prime to the modulus.'), end
ainv = mod(x,n);

function [g,c,d] = gcdSym(a,b)
% [g,c,d] = gcdSym(a,b)
% Modification of MATLAB's gcd function (extended Euclidean algorithm) that
% has symbolic functionality.
%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 non-negative
%   integers 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.

if ~isequal(round(a),a) || ~isequal(round(b),b)
    error('MATLAB:gcd:NonIntInputs', 'Requires integer input arguments.')
end
 
for k = 1:length(a)
   u = [1 0 abs(a(k))];
   v = [0 1 abs(b(k))];
   while v(3) ~= 0
       q = floor( u(3)/v(3) );
       t = u - v*q;
       u = v;
       v = t;
   end
 
   %c(k) = u(1) * sign(a(k));
   %d(k) = u(2) * sign(b(k)); %sign is not defined for symbolic objects
   if a(k)^2 - abs(a(k))*a(k) ~= 0 %this means a(k) is negative
       c(k) = -u(1);
   else
       c(k) = u(1);
   end
   if b(k)^2 - abs(b(k))*b(k) ~= 0 %this means b(k) is negative
       d(k) = -u(2);
   else
       d(k) = u(2);
   end
   g(k) = u(3);
end