Bored!
Find the number of integers 1 ≤ n ≤ 1 0 0 0 such that 7 ∣ a b ,where a ≡ n ( m o d 3 ) , 0 ≤ a ≤ 2 and b ≡ n ( m o d 5 ) , 0 ≤ b ≤ 4 .
The answer is 199.
This section requires Javascript.
You are seeing this because something didn't load right. We suggest you, (a) try
refreshing the page, (b) enabling javascript if it is disabled on your browser and,
finally, (c)
loading the
non-javascript version of this page
. We're sorry about the hassle.
1 solution
Are you guys punishing me or something? why don't you solve the question.
Log in to reply
I got it wrong because I forgot about 0 0 :(
Log in to reply
Henry, I am sure you got the main idea correct though
Log in to reply
@A Former Brilliant Member – I did, and it raised the question about "How many two-digit multiples of some number (here 7) can be written by using only a subset of the possible digits in some base (here 10)?"
For example, 3 multiples of 7 ( 0 , 1 4 , 2 1 ) can be written by using the 4 digits { 0 , 1 , 2 , 4 } , but with these digits we can also write a fourth multiple, 42. So, we need only 3 digits to write 3 multiples, 1 4 , 2 1 , 4 2 .
But actually, we can write 0 , 7 , 7 0 , 7 7 using only 2 digits.
| Number of digits | 1 | 2 | 3 | 4 | … |
| Maximum number of two-digit multiples of 7 using this number of digits | 2 (7,77) | 4 (00,07,70,77) | ≥ 4 | … | … |
Log in to reply
@Henry U – Cool Henry, you always go further than required, unlike me :D
Can you please explain Chinese remainder theorem with example?(I am confused by reading it's wiki)
Since a b is a two digit number and it should be a multiple of 7 and 0 ≤ a ≤ 2 and 0 ≤ b ≤ 4 . Therefore, a b can only be either of the following integers { 0 0 , 1 4 , 2 1 } . For each possible a b , we should solve the system
n ≡ a ( m o d 3 )
n ≡ b ( m o d 5 )
using Chinese remainder theorem. for each of the possibilities { 0 0 , 1 4 , 2 1 } , n ≡ 0 , 4 , 1 1 ( m o d 1 5 ) respectively. So, in the set { 1 , 2 , 3 , … , 1 5 } , there are exactly 3 integers, that contribute to the final answer. Since 1 0 0 0 = 6 6 × 1 5 + 1 0 , there would be 6 6 × 3 + 1 = 1 9 9 such integers.