Need help with a programming problem (writing in Java):

Write a program that prompts the user to enter three positive integers a, b, n. Then, output the general form of solutions to the congruence equation ax b (mod n) if there is such a solution. If there is no solution output NO SOLUTION.

For example, suppose I enter a = 2, b = 3, n = 6 the output should be NO SOLUTION. If on the other hand, I enter a = 2, b = 4, n = 6 then the general solution is x 2 (mod 3) so your program outputs x = 2 (mod 3).

Hint: Recall that we have seen how to solve congruences like ax b (mod n) if gcd(a, n) = 1. Clearly you can check if gcd(a, n) = 1 and if so you know what to do. If that is not the case however, then first show that the equation has a solution iff d|b where d = gcd(a, n) and in this case it is enough to solve the equation (a/d) (b/d) (mod (n/d)). Also convince yourself why gcd(a/d, n/d) = 1. Now use how to solve congruences of the type you have seen in class.