# How many numbers of $8$ digits and $9$ digits are there which are multiples of $11$?

How many numbers of $8$ digits and $9$ digits are there which are multiples of $11$?

Is there any way to solve this without brute-forcing?

I am trying to use the divisibility property of $11$ which is difference of the sum of even placed digits and the odd positioned digits is either $0$ or a multiple of $11$ but can't really see a solution yet.

-
Why don't you have to worry about end effects? –  Robert Israel Sep 28 '11 at 0:47
@RobertIsrael: because 10^9-10^7 is a multiple of 11 –  Ross Millikan Sep 28 '11 at 0:53

Hint: each multiple of 11 is $11 k$ for some $k$. What are the least and greatest $k$ for which $11 k$ has 8 or 9 digits?

-

Hint: how many 8 and 9 digit numbers are there? Every eleventh one is divisible by 11.

-

HINT $\ \rm\:[n,n+b)\:$ has exactly one multiple of $\rm\:b\:,\:$ hence $\rm\:[n,n+k\:b)\:$ has exactly $\rm\:k\:$ multiples, being $\rm\:k\:$ of the same $\rm\:[n,\:n+k\:b) = [n,\:n+b)\cup[n+b,\:n+2\:b)\cup\cdots\cup\:[n+k\:b-b,\:n+k\:b)$ Equivalently, they are $\rm\:k\:$ complete systems of representatives for the residues classes modulo $\rm\:b\:.$

In other words, $\rm\: [n,m)\:$ has exactly $\rm\:(m-n)/b\:$ multiples of $\rm\:b\$ if $\rm\ b\ |\ m-n\:.$

Now specialize $\rm\:b = 11,\ n = 10^{\:7},\ m = 10^{\:9},\:$ noting $\rm\:11\ |\ 10^9-10^7 =\: 99\cdot 10^7\:.$

-