First common term in two different A.P's

general
, ,
1

Let a1 and a2 be first terms and d1 and d2 be common differences of two different arithmetic progressions (A.P.).

We need to find the first term, which is common to both AP’s. If it is not possible that such a term exists, print “-1”.

e.g for a1=2, d1=3 and a2=3, d2=4.

The first common term will be 11.

Solving normally, I got n1d1 - n2d2 = (a2-d2) - (a1-d1) (=c say)

How can we solve this further?

1 Like
2

This is known as “first intersection of two Arithmetic Progressions”

There is a very detailed and nicely written answer Here

Go through it and if you do not understand, i will try my best to explain it to you :slight_smile:

Feel free to comment for any doubts

Happy coding!

1 Like
3

Just a few doubts, (I myself had tried to solve this using extended euclidean earlier):

  1. While calling the extended euclidean for the first time, can we write this,
    extended_euclidean(d1,-1*d2,&n1,&n2)? Are we allowed to send a negative value to it?
    What are things that will change?

  2. If the RHS<0, then the base call needs to be : extended_euclidean(-*d1,d2,&n1,&n2)?
    Is there way this could be avoided?

4

what gcd(a,b) does is check what numbers divides both a and b. Say, a number is divisible by 2, then its obvious negative of that number will also be divisible by 2. So it doesn’t matter you can do your computation with positives of those numbers

5

If I do it with positive numbers, it will be like solving

ax+by=gcd(a,b)

and not ax-by=gcd(a,b)

Correct me if I am wrong.

If what I am saying is correct, then the main problem was that negative sign. How could I take that into consideration?

6

first we check, if (a2 - a1) is divisible by gcd(|d1|,|d2|) if no, answer is -1. next we solve -d1x + d2y = gcd(|d1|,|d2|)

7

you take out the (x,y) u get from extended euclidean, your answer is (n1,n2) = (RHSx + td2)/(gcd(d1,d2) , (RHSy + td1)/(gcd(d1,d2)). Now choose smallest value of t such that n1 and n2 are positives

8

also read here: divisibility - Greatest common Divisor of negative numbers - Mathematics Stack Exchange

9

1 last thing, t= max( floor((RHS/d2)*x) +1 , floor((RHS/d1)*y) +1 )

10

Excellently explained. Learnt a lot from this. Thanks a lot!!!

11

I am glad to be of some help to you :slight_smile: