/*                                                      */
/*      axbm.c--solves a*x = b mod m                    */
/*                                                      */
/*      returns x as value of function                  */
/*                                                      */
/*      returns -m if congruence is 0 = 0               */
/*               1 if congruence is (0) = (<>0)         */
/*               g = gcd(a,m) if g does not divide b    */
/*                                                      */
long axbm(ainput,binput,minput)
long ainput,binput,minput;
{

	long a, b, m, n1, n2, n3, q, r, sgn, t, x;

	a = ainput % minput;
	if (a < 0L)
		a += minput;
	if ( a == 0L )
	{
		if ( (binput % minput) == 0L )
		{
			/*      congruence is 0 = 0     */
			return(-minput);
		}
		else
		{
			/*      error--congruence is (0) = (<>0)        */
			printf("\nerror--zero is not zero\n");
			return(-1L);
		}
	}

	m = minput;
	a = ainput % m;
	q = m / a;
	r = m % a;
	n1 = 0L;
	n2 = 1L;
	sgn = 1L;
	while (r != 0L)
	{
		sgn = -sgn;
		n3 = n2 * q + n1;
		n1 = n2;
		n2 = n3;
		m = a;
		a = r;
		q = m / a;
		r = m % a;
	}

	b = binput / a;
	t = binput % a;
	if (t != 0L)
	{
		/*      error--gcd(a,m) does not divide b       */
		printf("\nerror--gcd does not divide b\n");
		return(-a);
	}
	else
	{
		/*      real solution   */
		x = (b*n2) % minput;
		if(sgn == -1L)
			x = -x;
		if(x < 0L)
			x += minput;
		return(x);
	}
}