Maths Olympiad Prep

Library / /110 of 128

Number theory Difficulty 6.7 National Olympiad Prove it Philippines

Problem:

Two students, Lemuel and Christine, each wrote down an arithmetic sequence on a piece of paper. Lemuel wrote down the sequence 2,9,16,23,2, 9, 16, 23, \ldots, while Christine wrote down the sequence 3,7,11,15,3, 7, 11, 15, \ldots After they have both written out 2010 terms of their respective sequences, how many numbers have they written in common?

Solution

Solution:

Let us first write the general term for each sequence.

Lemuel's sequence: 2,9,16,23,2, 9, 16, 23, \ldots
This is an arithmetic sequence with first term a1=2a_1 = 2 and common difference d=7d = 7.
So the nnth term is an=2+7(n1)=7n5a_n = 2 + 7(n-1) = 7n - 5.

Christine's sequence: 3,7,11,15,3, 7, 11, 15, \ldots
This is an arithmetic sequence with first term b1=3b_1 = 3 and common difference d=4d = 4.
So the mmth term is bm=3+4(m1)=4m1b_m = 3 + 4(m-1) = 4m - 1.

We are to find how many numbers appear in both sequences among the first 2010 terms of each.

A number is in both sequences if 7n5=4m17n - 5 = 4m - 1 for some integers n,mn, m with 1n20101 \leq n \leq 2010 and 1m20101 \leq m \leq 2010.

So 7n5=4m1    7n4m=47n - 5 = 4m - 1 \implies 7n - 4m = 4.

We want integer solutions (n,m)(n, m) with 1n20101 \leq n \leq 2010, 1m20101 \leq m \leq 2010.

Let us solve 7n4m=47n - 4m = 4 for integers n,mn, m.

7n4m=4    7n=4m+4    n=4m+477n - 4m = 4 \implies 7n = 4m + 4 \implies n = \frac{4m + 4}{7}.

We need nn to be integer, so 4m+40(mod7)4m + 4 \equiv 0 \pmod{7}.

4m+40(mod7)    4m4(mod7)    4m3(mod7)4m + 4 \equiv 0 \pmod{7} \implies 4m \equiv -4 \pmod{7} \implies 4m \equiv 3 \pmod{7} (since 43(mod7)-4 \equiv 3 \pmod{7}).

Now, 44 and 77 are coprime, so 44 has an inverse modulo 77.

The inverse of 44 modulo 77 is 22, since 4×2=81(mod7)4 \times 2 = 8 \equiv 1 \pmod{7}.

So m2×3(mod7)    m6(mod7)m \equiv 2 \times 3 \pmod{7} \implies m \equiv 6 \pmod{7}.

So m=7k+6m = 7k + 6 for integer k0k \geq 0.

Now, 1m20101 \leq m \leq 2010.

So 7k+62010    7k2004    k286.285...7k + 6 \leq 2010 \implies 7k \leq 2004 \implies k \leq 286.285...

So kk ranges from 00 to 286286 (inclusive), so k=0,1,2,,286k = 0, 1, 2, \ldots, 286.

Thus, there are 287287 possible values of mm.

Now, for each m=7k+6m = 7k + 6, n=4m+47=4(7k+6)+47=28k+24+47=28k+287=4k+4n = \frac{4m + 4}{7} = \frac{4(7k + 6) + 4}{7} = \frac{28k + 24 + 4}{7} = \frac{28k + 28}{7} = 4k + 4.

We need 1n20101 \leq n \leq 2010.

For k=0k = 0, n=4n = 4.
For k=286k = 286, n=4×286+4=1144+4=1148n = 4 \times 286 + 4 = 1144 + 4 = 1148.

So nn ranges from 44 to 11481148 in steps of 44.

But since kk runs from 00 to 286286, there are 287287 values.

Therefore, the answer is 287\boxed{287}.

Want a route through all this instead of an archive? The track puts 2,000 problems in a working order, from AMC 10 level to the IMO shortlist.

Source: MathNet, licensed CC-BY-4.0. Statement reproduced verbatim; metadata (topic, difficulty) added by this project.