How many numbers between 111 and 100100100 (inclusive) are divisible by 333 and 101010?
2 answers:
You might be interested in
I'm assuming writing "one digit on the both sides of 57" means you write the same digit to either side, like in 1571?
Given a number
with 
digits, prepending and appending the same digit 
, 
(omit 0 because it doesn't change the starting number), is the same as multiplying by 10 and adding 
. We have 
, so we're looking for such that
8 and 9 are coprime, so we can use the Chinese remainder theorem.
which simplifies to
Now we apply the CRT. We want some number such that, taken modulo 8, returns a remainder of 6, but taken modulo 9, returns a remainder of 3. So we could try
Modulo 8, the second term vanishes, and
. However, modulo 9, the first term vanishes but 
, whereas we only want 3. So we multiply the second term by the inverse of 2 modulo 9.
To find the inverse, notice that
, so 
, and so we multiply the second term by 5. Now,
and
so we find that
. In particular, the smallest positive solution is 30, which is larger than 9 so there are no single-digit choices of that makes the new number divisible by 72.
Given a number
8 and 9 are coprime, so we can use the Chinese remainder theorem.
which simplifies to
Now we apply the CRT. We want some number
Modulo 8, the second term vanishes, and
To find the inverse, notice that
and
so we find that