In the first 1000 natural numbers, how many integers exist such that they leave a remainder 4 when divided by 7, and a remainder 9 when divided by 11?	Choose one
A) 11
B) 14
C) 12
D) 13
E) 10
Explanatory Answer   Step 1: Find the first number common to both the sequences.   The first sequence: Numbers leaving a remainder of 4 when divided by 7: 4, 11, 18, 25, 32, 39, 46, 53, 60, 67, ....   The second sequence: Numbers leaving a remainder of 9 when divided by 11: 9, 20, 31, 42, 53, 64, .....   From the listing of the two sequences we can identify the first number that is a part of the both the sequences is 53.   Step 2: Compute common difference of terms common to both sequences and find number of terms.   The common difference of the first sequence is 7 and that of the second sequence is 11.   Elements common to both the sequences will have a common difference that is the LCM of 7 and 11.   77 is the LCM of 7 and 11.   Every 77th number after 53 will satisfy both the conditions.   The terms that are common to both the arithmetic sequences can be expressed as 77k + 53.   Because we are interested in the first 1000 natural numbers, k will take values from 0 to 12.   i.e., a total of 13 values.   Choice 13 is the correct answer.
<result>D</result>
In the first 1000 natural numbers, how many integers exist such that they leave a remainder 4 when divided by 7, and a remainder 9 when divided by 11?