Integers Shared by Arithmetic Sequences

We note that numbers in $A_1$ are of the form $7k+2$ and numbers in $A-2$ are of the form $9k+3$ . Using the Chinese Remainder Theorem, We know that the common numbers must be of the form $63k + 30$ .

Considering the range of the sequences, we must have $2 \leq 63k + 30 \leq (1000-1) \times 7 +2$ . This gives that $0 \leq k \leq 110$ . Thus, the total number of common numbers is $110 -0 + 1 = 111$ .

General term of $A_{1} \ = \ 7n \ - \ 5$

$A_{2}$ = $9m \ - \ 6$

Thus $7n \ - \ 5 \ = \ 9m \ - \ 6$

$1 \ + \ 7n \equiv \ 0 \ (mod \ 9 )$

$n$ is of the form $5 \ + \ 9k$

There are $111$ such whole number $k \ < \ 1000$

Since, $A_{2}$ can always achieve the same terms with lesser term indicators, thus the answer is $\boxed{111}$

$A_1$ has integers equivalent to $2 \pmod{7}$ and $A_2$ has integers equivalent to $3 \pmod{9}$ . We look for all numbers in $A_1$ that are equivalent to $3 \pmod{9}$ which is the same as looking for numbers in $A_2$ equivalent to $2\pmod{7}$ . Checking the first few terms of $A_1$ we see that $30 \equiv 3\pmod{9}$ and this repeats every $9$ terms. Thus the numbers of the form $30 + 63(k-1)$ will appear in both arithmetic progressions as long as $2 \leq 30 + 63 (k-1) \leq 2 + (1000-1) \times 7 \Rightarrow 1 \leq k \leq 111$ . Thus $111$ integers appear in both arithmetic progressions.

Since the first common term is 30 the other common terms will be the L.C.M of A1 & A2 i.e 63. So the series of common terms is 30, 93, 156,..., nth term now Tn= a + (n-1)d = 30+ (n-1)63 now this equation should be less than (1000-1)*7 + 2 as the common terms would not exceed it Thus, 30 + (n-1)63 ≤ 6995 → (n-1)63 ≤6965 → (n-1) ≤ 6965/63 → (n-1) ≤110.5 → n ≤ 111.5 which is approx. 111
Hence the answer is 111.

series $A_1=2,9,16,23,30,37,44,51,58,65,72,79,86,93,100 \ldots , 6995$ series $A_2=3,12,21,30,39,48,57,66,75,84,93,102, \ldots 8994$ . If you clearly observe both series, the $5,14, \ldots$ terms in the series 1 are matching with the $4,11, \ldots$ terms in the series 2. Since the LCM for 7 and 9 is 63 (7 and 9 are the common differnces for both series),so integers in both series match after every 63 from 30.(like 93,156,219.....). This corresponds to the $5,14,23,32,41, \ldots$ terms of series 1. Since total terms in series 1 is 1000, the terms that match are $5,14,23.32,41.50, \ldots 995$ , we will get 111 terms.

Relevant wiki: Bezout's Identity

I referred to Bezout's identity, noticing :

• $7$ and $9$ are coprimes, and

• $2+k\times7=3+l\times9$ can be written $k\times7-l\times9=1$ .

We know that if we find a solution $(k,l)$ , the solutions will be the couples $(k+9n;l+7n)$ .

A particular solution can be easily found : $(4,3)$ since $4\times7-3\times9=1$ . Then the solutions are the couples $(4+9n;3+7n)$ .

As $4+9n\leq999$ , then $n\leq110$ . Thus there are $111$ solutions.

5th ,14th , 23rd... terms match from A1 . Numbers of terms in A1 are 1000 except 1st term all terms match after 9 terms . so total terms that match are (1000-5)/9 = 110 (not taking remainder) + 1 term which we left in start=111

class MyClass {

public static void main(String[ ] args) {


int sum=0;


    for(int a=1;a<=1000;a++)


    {


       for(int b=1;b<=1000;b++){


        if(7*a-5==9*b-6){


           sum+=1; 


        } 


          } 


       }


       System.out.println(""+sum); 


    }


}

OUTPUT=111