given a modular equation k = ax mod b where we know k and a and b find the smallest possible integer number for x
example (15 = 8x mod 25) , here the set of x that satisfy it up to the smallest integer are [1.875 , 3.75 , 5] but the smallest integer number is 5 how do i find the smallest integer number that satisfies the equation in o(1) or o(logb) anything thats not o(b) and above
searched alot and all i was able to find is the usage of EEX but i dont think its what iam looking for also modular inverse doesnt necessarily work since b (the mod) might not coprime with a or k
First, for it to have solution, gcd(a,b) should be a factor of k. Then, you can find x and y and ax + by = gcd(a,b) (Bezout's identity) and gcd using euclid's algorithm. Then, multiply x by (k / gcd(a,b)