use java

Comp 2700 (Discrete Structures) Fall 2018. Programming Assignment 2 Submissions: This assignment is due at 11:59 PM on the 29th of October, 2018. Each student must submit his or her own assignment. This is a programming assignment. You have to submit code that can be run on a computer. You can use Java, C, C++ or Python to write code. In any case, your submission should be a zipped file containing your code (not compiled code), any relevant instructions to compile or run your code in a separate README file, and any test cases you used to test your code. The input/output format for each proble is specified with the problem. For th input format, you may assume the format will be absolutely as specified, e., you do not need to check for errors in the input format For the output, your oode must output its results on the standard output in the strict format desired of it (and nothing else) Academic Integrity: You are encouraged to work in groups, but everyone must write his/her own code. Absolutely no copying is allowed. Please refer to the course policies and schedules about this. If you have worked with other students on the assignment or referred to external sources, please mention all names and sources on your assignment Problem 1[50 pts]: Write a program that prompts the user to enter two positive integers named a and b. Then, output the Bezout coefficients of , b Recall that the Bezout coefficients are (any) integers s, t such that: as +bt- ged(a, b) Problem 2[50 pts: 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 az b (mod n) if there is such a solution. If there is no solution output "NO SOLUTION For example, suppose l enter a = 2, b = 3 n-6 the output should be "NO SOLUTION". If on the other hand, I enter 2,b 4, n-6 then the general solution isz 2 (mod 3) so your program ontputs 2 (mod 3). Hint: We have seen how to solve congruences like az b (mod n) ifged(a. n) = 1 Clearly you can check if gcd(a n) = 1 and i so you knou what to do. I that is not the case however, then we saw that the equation has solution d b where d = ged(a, n) and in this case it is enough to solve the equation (a/d) (b/d) (mod (n/d). Cont ince yourself trhy gcd(a/dn/d) = 1. This then reduces to the previous case