# 10 digit numbers formed using all the digits $0,1,2,...,9$

If $10$ digit numbers are formed using all the digits $0,1,2,...,9$ such that they are divisible by $11111$ then the question is to find number of such numbers possible and the digit in the $10000^{th}$ place of largest number of such numbers.

I have not been taught number theory in school and have no idea on how to approach this problem.i tried by some hit and trial during exam but was not successful I would appreciate if someone could help me with this.Thanks.

• Hint: try proving that any ten-digit number divisible by $11111$ of the form $a_1a_2a_3a_4a_5b_1b_2b_3b_4b_5$ must have $a_i+b_i=9$ for each $i$. May 9 '17 at 16:28

All numbers will be of the form $a_1a_2a_3a_4a_5b_1b_2b_3b_4b_5$ where $a_i+b_i=9$ for all $i$ using each digit exactly once and each number of that form will satisfy your conditions. Proof below.

As such, by choosing $a_1$, the choice of $b_1$ is forced. Similarly choosing $a_2,a_3,a_4,a_5$ will force the choice for $b_2,b_3,b_4,b_5$.

Applying multiplication principle, and remembering that leading zeroes do not contribute to the number of digits of a number (e.g. $012349876$ does not count as a ten-digit number) we have $9$ options for $a_1$, $8$ options for $a_2$, $6$ options for $a_3$, $4$ options for $a_4$, and $2$ options for $a_5$.

There are then $9\cdot 8\cdot 6\cdot 4\cdot 2=3456$ ten digit numbers satisfying all of the desired properties.

The largest number of which is formed with the largest selections available for $a_1,a_2,\dots$ respectively and is then $9876501234$, the $10000$'s place being the $5$.

Lemma: Any ten digit number of the form $a_1a_2a_3a_4a_5b_1b_2b_3b_4b_5$ is divisible by $11111$ if and only if $a_1a_2a_3a_4a_5+b_1b_2b_3b_4b_5$ is divisible by $11111$.

$a_1a_2a_3a_4a_5+b_1b_2b_3b_4b_5\equiv (9\cdot 11111)a_1a_2a_3a_4a_5+a_1a_2a_3a_4a_5 + b_1b_2b_3b_4b_5$

$\equiv 10^5a_1a_2a_3a_4a_5+b_1b_2b_3b_4b_5\equiv a_1a_2a_3a_4a_5b_1b_2b_3b_4b_5\pmod{11111}$

Claim: In the set of ten digits numbers using all digits $0$-$9$ the number is divisible by $11111$ if and only if it is of the form $a_1a_2a_3a_4a_5b_1b_2b_3b_4b_5$ where $a_i+b_i=9$ for all $i$.

$\Leftarrow)~~$ Suppose that $a_i+b_i=9$ for all $i$. Then $a_1a_2a_3a_4a_5+b_1b_2b_3b_4b_5=99999$ is divisible by $11111$. Then by the lemma, so too is $a_1a_2a_3a_4a_5b_1b_2b_3b_4b_5$.

$\Rightarrow)~~$ Suppose that $a_1a_2a_3a_4a_5b_1b_2b_3b_4b_5$ is a ten-digit number using all digits exactly once which is divisible by $11111$.

By the lemma, we know then that $a_1a_2a_3a_4a_5+b_1b_2b_3b_4b_5=n\cdot 11111$ for some $n$.

As all digits are used exactly once, the sum of the digits is $1+2+\dots+9=\frac{9\cdot 10}{2}=45$. As this is divisible by $9$ both $a_1a_2a_3a_4a_5b_1b_2b_3b_4b_5$ and $a_1a_2a_3a_4a_5+b_1b_2b_3b_4b_5$ must also be divisible by $9$. (see sum of digits of a number is equivalent modulo 9 to the number itself proof elsewhere).

As the digits are distinct $16047= 13579+02468\leq a_1a_2a_3a_4a_5+b_1b_2b_3b_4b_5\leq 97531+86420=183951$ as those selected numbers minimize and maximize the sums of the respective digit positions respectively. From this, we know then that $1\cdot 11111<a_1a_2a_3a_4a_5+b_1b_2b_3b_4b_5<17\cdot 11111$ so we know that $n\in \{2,3,\dots,16\}$.

As $11111$ is coprime to $9$, by chinese remainder theorem, we know then that $a_1a_2a_3a_4a_5+b_1b_2b_3b_4b_5$ must be divisible by $9\cdot 11111=99999$. The only value then for $n$ which satisfies this is $n=9$ and therefore $a_1a_2a_3a_4a_5+b_1b_2b_3b_4b_5=99999$

Now... if $a_i+b_i\neq 9$ for some $i$ then there must be some $a_j+b_j>9$ for some $j$ due to law of averages. The largest value of which is $9+8=17$, and the largest carryover for a specific digit place is $1$, which would result in a digit of $a_1a_2a_3a_4a_5+b_1b_2b_3b_4b_5$ being strictly less than $9$. It follows then that it must be that $a_i+b_i=9$ for all $i$.

• Thanks for your answer.I will have to study elementary number theory to have a full grasp of your proof :) May 9 '17 at 18:54

Trick is tor realize adding or subtracting $11111$ will raise or lower $5$ consecutive digits. And to realize that $11111*11 = 122221$ and $11111*111 = 1233321$ etc. So...

consider $11111^2 = 123454321$.

Then notice that $11111^2 + 11111 = 123465432$

and $11111^2 + k*11111 = 1234(5+k)(4+k)(3+k)(2+k)(1+k)$.

So $11111^2 + 4*11111 = 123498765$

and so $10(11111^2 + 4*11111) = 1234987650$.

So $1234987650 = 11111*111150$