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 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 r 2 (mod 3) so your programi outputs x = 2 (mod 3). Hint: Recall that we have seen how to solve congruences like az b (mod n) if gcd(am)-: 1. Clearly you can check i gcd(am) = 1 and if so you know uhat to do. If that is not the case however, then first show that the equation has a solution iff dlb where d gcd(a,n) and in this case it is enough to solve the equation (a/d) (b/d) (mod (n/d). Also inourhy sd(a/d.n)-. ou to solec rers of the tyht as

Explanation / Answer

Solutiopn:

code:

#include <iostream>

using namespace std;

//Function to return gcd of two numbers

int gcd(int a, int b) {

return b == 0 ? a : gcd(b, a % b);

}

//Main method

int main() {

int a, b, n, x;

cout << "Please enter 'a' value: ";

cin >> a;

cout << "Please enter 'b' value: ";

cin >> b;

cout << "Please enter 'n' value: ";

cin >> n;

int d = gcd(a, n);

//Checking for No solution condition

if ((n % b == 0) || (d % b == 0)) {

cout << "NO SOLUTION" << endl;

} else {

cout << "SOLUTION EXIST" << endl;

//declaring intermediate varibles to process the values

int a1 = a / d;

int b1 = b / d;

int n1 = n / d;

int i = -1;

int q, r, t, t1 = 0, t2 = 1;

//Checking the condition for zero

while (a1 > 0) {

q = n1 / a1;

r = n1 - q * a1;

n1 = a1;

a1 = r;

t = t1 - q * t2;

t1 = t2;

t2 = t;

}

if (n1 == 1)

i = t1;

if (i < 0)

i = i + a;

x = (b1 * i) % (n / d);

cout << "Final Solution is : x =" << x << "+" << n / d<< "k where k is any integer"<<endl;

}

}

Ouput:

1)

Please enter 'a' value: 2
Please enter 'b' value: 4
Please enter 'n' value: 6
SOLUTION EXIST
Final Solution is : x =2+3k where k is any integer

2)

Please enter 'a' value: 2
Please enter 'b' value: 3
Please enter 'n' value: 6
NO SOLUTION

I hope this helps if you find any problem. Please comment below. Don't forget to give a thumbs up if you liked it. :)

Related Questions

Navigate

• Browse (All)
• Browse P
• Subjects

---

---

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