Equation problem

Given two integers ‘n1’ and ‘n2’, select two integers ‘a’ and ‘b’, such as to solve the equation (n1 * a + n2 * b = x). But there is a catch, ‘x’ is the smallest positive integer which satisfies the equation.

-10^7 <= a, b <= 10^7
0 <= n1, n2 <= 10^7

how it can be solved
i assume that it is a gcd problem like gcd(n1,n2)=x so it give correct answer for all test cases?

1 Like

I think that’s correct, Can you provide the link to the problem?

1 Like

i dont have a link because it is codevita problem

i am providing test case for this problem
eg
Given n1 = 34818 and n2 = 45632, if we choose a = 3553 and b = -2711, we get
=> n1 * a + n2 * b = x
=> 34818 * 3553 + 45632 * (-2711)
=> 2

This will help: https://en.wikipedia.org/wiki/Diophantine_equation#Linear_Diophantine_equations

1 Like

ohh this means that gcd is a correct answer for this

1 Like

Learn Extended Euclidean Theorem Then Learn Chinese Remainder and the Diophantine equation

1 Like

For Equation to be solvable It is compulsion That x should be divisible by The GCD of(n1,n2) It is rule. And X should be minimum as given in condition x must be GCD(n1,n2) so it is always be divisble.

Eg.170 x - 455 y = 625;
First we check whether it is solvable or not. As it is solvable because GCD of(170,455) divides 625 that is 5. GCD=5 NOW;

By assumption or hit trial we find putting x=1 and y=-1 satisfies this equation Now let x1=1 and y1=-1;

Now solutions of this equations are x = (x1 - (b/GCD)*T)

AND Y=(y1 +(a/GCD)*T) are yours solution;;;;Hope I am able to clear;
Where T is integer!! Thanks For Asking!!!1

1 Like