Problem with solving Ax+B mod M = 0

[GonlyG]

I'm given A, B, M and have to solve for x in several equations. My output is constantly incorrect and I can't figure out why. Any help would be appreciated.

#include <iostream>
#include <algorithm>  
using namespace std;
int inverse(int a, int b)
{
	int inv = -1;
	int q, r, r1 = a, r2 = b, t, t1 = 0, t2 = 1;

	while (r2 > 0)
	{
	    /*A * x + B = 0
    A * x = -B
    x = -B/A
    x = -B * inv(A)
*/
		q = r1 / r2;
		r = r1 - q * r2;
		r1 = r2;
		r2 = r;

		t = t1 - q * t2;
		t1 = t2;
		t2 = t;
	}

	if (r1 == 1)
		inv = t1;

	if (inv < 0)
		{inv = inv + a;}

	return inv;
}

int gcd(int a, int b) {
   if (b == 0)
   return a;
   return gcd(b, a % b);
}
int main(){
    int a;
    cin>> a;
    for (int i=0; i<a; i++){
        //cout<<" in loop ";
        int m; int a; int b;
        cin>>m>>a>>b;
        
        int d = gcd (a,m);
        if (d != 1){
            cout <<"-1 ";
        }
        else{
		    
            int inv = inverse(m, a);
            int x0 = b * (inv % m);
            while(x0<0){x0+=m;}
            cout<<x0<<" ";
        }
        
   }
   return 0;
}

input: 26
91545 35168 31961
80015 16909 67464
86976752 55357536 31202059
977976526 370509909 927951880
323456 192517 203892
5156 4195 738
604113229 296653391 258126842
269281 207788 69923
15663 9536 5986
820074852 184699680 567228886
86168668 4344592 54863971
429273239 251362335 48835933
18073993 13449180 14065520
557798 513701 90377
41259 24315 16220
36094224 23560401 31249598
2615247 648228 1235605
47361 7776 36536
214639 87604 37443
99369210 28638314 39399505
3328 583 1352
956681 543211 719366
1571187 227866 296748
7977756 435951 277463
30321 15381 4274
67138245 61251401 7410108

output: 984302917 120355776 -1 1695138680 992563940 2688534 497042510 360542079 91723478 -1 -1 1229998694 12266424 232917 -1 -1 -1 -1 2052849918 -1 4314232 407206 340223812 -1 -1 49078494

expected: 80468 66799 -1 148672054 3996 2898 167166067 219142 14713 -1 -1 24799627 10915233 153603 -1 -1 -1 -1 172117 -1 2184 694193 626940 -1 -1 18239187

[helios]

It looks like inverse(a, b) calculates the multiplicative inverse of a modulo b via the extended Euclidean algorithm. Then you appear to be calling it incorrectly on line 54. You're calling it with the parameters swapped.

[GonlyG]

I switched the parameters but my output's still incorrect... any insight?

[helios]

Also line 55 implies you're doing this:
A*x + B = 0
A*x = B (!!!)
x = B * (1/A)
You never flip the sign of B. The correct transformation would be
A*x + B = 0
A*x = M - B
x = (M - B) * (1/A)

[GonlyG]

I tried changing the else statement to:

   int inv = inverse(a, m);
            int x0 = (m-b)*inv;
            while(x0<0){x0+=m;}
            cout<<x0<<" ";

but it still isn't correct... muse be something else going on here...

[helios]

You'll have to debug then. Have you checked that the return value from inverse() is actually the multiplicative inverse?

[lastchance]

Why do you suppose that A will have a multiplicative inverse mod M? The integers aren't a field; nor are they in mod M unless M happens to be prime.

What do you think that the multiplicative inverse of 4 is in mod 12?
i.e for what A does
4A (mod 12) = 1

Unless M is prime, your equation may have many or no solutions in integers.

[GonlyG]

I checked that gcd(a,m) == 1 ensuring they are coprime...