Problem 144 Modular Inverse - sometimes solutions exist
Back to Problem Solutions forum
In program statement there is line:
Answer should give value x for each case or -1 (not valid value) if solution do not exist.
Second example is M=57, A=42, B=30 with answer -1.
But solutions set of 42 * x + 30 = 0 (mod 57) is not empty, there are 3 solutions: x=2, x=21 and x=40. So why -1?
Hi, Andrey! Thank you for pointing this out!
Hm... That's embarrasing - looks like a bug. :( I'll go and investigate it right now!
UPD I see my fault. If gcd(A, M) > 1 then there is no modular inverse, but there still can
exist solution if B is divisible by this gcd. I'll try to improve the checker to handle this -
thanks a lot once more!
Fixed
I've slightly updated the problem so that such cases are not generated (cheating!) as the problem is about inverse, not about equation :)
As a sidenote, after some meditation it seems to me that:
- equation has solutions only when
B % gcd(A, M) == 0; - there are exactly
gcd(A, M)different solutions.
Perhaps we can have a separate problem for this, but I'm not sure it is interesting...