Problem 2[50 pts: Write a program that prompts the user to enter three positive

Question

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 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 is2 (mod 3) so your program outputs 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 ifdb 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 hou to solve congruences of the type you have seen in class.

Explanation / Answer

import java.util.Scanner;

class code
{
   public static int find_gcd(int number1, int number2)
   {
        if(number2 == 0)
            return number1;
      
        return find_gcd(number2, number1%number2);
    }

   public static void main(String args[])
   {
       Scanner sc=new Scanner(System.in);
      
        int a, b, n;
       
       System.out.print("Enter value for a: ");
          a = sc.nextInt();
         
          System.out.print("Enter value for b: ");
          b = sc.nextInt();
         
          System.out.print("Enter value for n: ");
          n = sc.nextInt();
      
        int gcd = find_gcd(a, n);
      
        if(b%gcd!=0)
           System.out.println("NO SOLUTION");
        else
        {
           int o1;
           for(o1=0;o1<n;o1++)
           {
               if((a*o1)%n == b)
                   break;
           }
          
           int o2 = n / gcd;
           o1 = o1%o2;
          
           System.out.println("x = "+o1+" (mod "+o2+")");
        }
    }
}  

Related Questions

Navigate

• Browse (All)
• Browse P
• Subjects

---

---

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.