# Divisibility 1,2,3,4,5,6,7,8,9,&10

Tried: Seems the ten-digit number ends with $$240$$ or $$640$$ or $$840$$ (Is not true, there are more ways the number could end)

$$8325971640,$$ $$8365971240,$$ $$8317956240,$$ $$8291357640,$$ $$8325971640,$$ $$8235971640,$$ $$1357689240,$$ $$1283579640,$$ $$1783659240,$$ $$1563729840,$$ $$1763529840,$$ $$1653729840,$$ $$7165239840,$$ $$7195236840,$$ $$2165937840,$$ $$9283579640$$

• any multiple of 27720 is a multiple of all those numbers up to 11. Not sure what else they re asking – Will Jagy Oct 27 '18 at 0:11
• maybe I understand. Divisibility by 9 is automatic here. The digits add up to 45. For 11, we need to choose a group of four digits and a group of five digits, so the sums differ by a multiple of 11, yet add to 45. So, 28+17 = 45 or 39+6 = 45. We cannot use the second one because four digits ad up to bigger than 6, so five (distinct) digits (including the highest 10^9 place) add to either 17 or 28. – Will Jagy Oct 27 '18 at 0:21
• 100 place a and 10 place b, we need $100a + 10b \equiv 0 \pmod 8,$ or $4a+2b \equiv 0 \pmod 8,$ or $2a + b \equiv 0 \pmod 4.$ The choices become 120, 320, 520, 720, 920; 240, 440, 640, 840 where 440 has a repeat. then 160, 360,560,760,960; 280, 480, 680, 880 which is a repeat – Will Jagy Oct 27 '18 at 0:26
• Found the answer 2438195760, 3785942160, 4753869120 and 4876391520 – user608997 Oct 27 '18 at 0:48
• those four are divisible by all the numbers from 1 through 18, but not 19. – Will Jagy Oct 27 '18 at 1:03

Suppose the number is of form $$N=jihgfedcba$$. We may write:

$$a+b+c+d+e+f+g+h+i+j+(10-1)b+(10^2-1)c+(10^3-1)d+(10^4-1)e+(10^5-1)f+(10^6-1)g+(10^7-1)h+(10^8-1)i+(10^9-1)j$$

A: Any number such as following forms are divisible by 2, 4, 5 and 8:

$$(2k)(40)$$ such as $$240, 440, 640, 840 . . .$$

$$(2k+1)(20)$$, such as $$120, 320, 520, 720, . . .$$

B: Whatever the value of g is, the term $$\frac{10^6-1}{9}$$ is divisible by $$77$$.

C: For 7 we consider the remainder of $$10^n-1$$ when divided by 7:

$$T=.....10, 10^2, 10^3, 10^4, 10^5, 10^6, 10^7, 10^8, 10^9$$

$$R_{10^n}=...3,..2,.. 6,.. 4,.. 5,... 1,.. 3,.. 2,.. 6$$

$$R_{10^n-1}=2,..1,..5,..3,...4,...0,...2,..1,..5$$

We can make following relation for divisibility by 7:

$$a+b+c+d+e+f+g+h+i+j+(2)b+(1)c+(5)d+(3)e+(4)f+(0)g+(2)h+(1)i+(5)j≡ mod 7$$

D: For 11 we just consider the remainder of $$10^n-1$$ for odd n because for even n,. $$(10^n-1)$$ is divisible by 11 :

$$T= .......10,....10^3,...10^5,...10^7,..10^9$$

$$R_{10^n}=...-1,...-1,...-1,...-1,..-1$$

$$R_{10^n-1}=-2,...-2,...-2,...-2,..-2$$

So we can make following relation for divisibility by 11:

$$a+b+c+d+e+f+g+h+i+j+(-2)b+(-2)d+(-2)f+(-2)h+(-2)j≡ mod 11$$

So we have following system of Diophantine equations:

$$a+b+c+d+e+f+g+h+i+j+(-2)b+(-2)d+(-2)f+(-2)h+(-2)j≡ mod 11$$

$$a+b+c+d+e+f+g+h+i+j+(2)b+(1)c+(5)d+(3)e+(4)f+(0)g+(2)h+(1)i+(5)j≡ mod 7$$

The sum $$a+b+c+. . .i+j= \frac{9(9+1)}{2}=45$$ is divisible by 3 and 9. This system of equations indicates that the question can have numerous solutions, to find one for example take $$cba=840$$ which is divisible by 2, 3, 4, 5, 7 and 8, That is we assume $$a=0$$, $$b=4$$ and $$c=8$$ and look for other digits as follows, we have:

$$45+4\times2+8\times1+5d+3e+4f+2h+i+5j≡ mod 7$$

Or:

$$61+5d+3e+4f+2h+i+5j≡ mod 7$$

$$45-2\times 4-2(d+f+h+j)=37-2(d+f+h+j)≡ mod 11$$

Suppose $$37-2(d+f+h+j)=11$$$$d+f+h+j=(37-11)/2=13$$

Suppose $$d=1, . f=2,.h=3,. and,..j=7$$ then we have:

$$61+5+3e+8+6+i+35=115+3e+i≡ mod 7$$

Let $$115+3e+i=21\times 7=$$$$3e+i=32$$$$e=9$$ and $$i=5$$

The only number which remains is 6 for g, so one solution can be:

$$N=7536291840$$

• That is hard to read. The naming of the digits as a,b,c is not very useful, $a_0, a_1,\ldots$ make more sense. Formulas like $61+5d+3e+4f+2h+i+5j≡ mod 7$ have no mathematical meaning. It seems you try to use dots to align values, but one should Latex arrays or similar structures to display this. – miracle173 Oct 27 '18 at 17:01

If the digit representation of such number is $$\langle d_9 d_8 d_7 d_6 d_5 d_4 d_3 d_2 d_1 d_0 \rangle$$, where $$\langle d_9 d_8 d_7 d_6 d_5 d_4 d_3 d_2 d_1 d_0 \rangle:=\Sigma_{i=0}^{9}10^id_i$$ then we know that $$d_0=0$$ because $$10\mid \langle d_9 d_8 d_7 d_6 d_5 d_4 d_3 d_2 d_1 d_0 \rangle.$$

The sum $$d_9 +d_8+ d_7+ d_6+ d_5+ d_4+ d_3+ d_2+ d_1 +0$$ is $$0+1+2+3+4+5+6+7+8+9=45,$$ so $$9 | \langle d_9 d_8 d_7 d_6 d_5 d_4 d_3 d_2 d_1 0\rangle.$$

Because $$8\mid \langle a_2 a_10\rangle.$$ we also know that $$4\mid \langle a_2a_1\rangle \tag{2}$$

So we have $$t\mid \langle d_9 d_8 d_7 d_6 d_5 d_4 d_3 d_2 d_1 0 \rangle, \; \forall t \in \{2,3,4,5,6,8, 9, 10\}$$ if $$(2)$$ holds.

If $$11\mid \langle d_9 d_8 d_7 d_6 d_5 d_4 d_3 d_2 d_1 d_0 \rangle$$ then for the alternate sum holds
$$11 \mid d_9 +d_8- d_7+ d_6- d_5+ d_4- d_3+ d_2- d_1+0$$

The alternate sum is between $$-9-8-7-6-5+1+2+3+4=35$$ and $$9+8+7+6-1-2-3-4-5=30.$$ But we know that the alternate sum is divisible by $$11$$ and it is the sum of $$5$$ odd and $$5$$ even numbers, so it is odd. Therefore the alternate sum is in $$\{-33,-11,11\}.$$

How to construct a solution?

1. Set $$a_0=0$$
2. Start with a possible value for $$\langle a_2a_1\rangle$$ such that

• $$4\mid \langle a_2a_1\rangle$$
• $$a_1 \ne a_2$$
• $$a_1 \ne 0$$
• $$a_2 \ne 0$$
3. The remaining digits $$\{1,2,3,4,5,6,7,8,9\}\setminus\{d_1, d_2\}$$ partion into two sets, set $$\cal{O}=\{d_3, d_5, d_7, d_9\}$$ that contains $$4$$ elements at the odd indexed positions and set $$\cal{E}\{d_4, d_6, d_0\}$$ that contains the $$3$$ elements at the even indexed positions.

4. If $$\Sigma_{d \in \cal{E}}-\Sigma_{d \in \cal{O}}+a_2-a_1 \in \{-33,-11,11\} \tag{1}$$ we are done, otherwise select an element $$\cal{e} \in \cal{E}$$ and $$\cal{o} \in \cal{O}$$, remove $$\cal{e}$$ from $$\cal{E}$$ and $$\cal{o}$$ from $$\cal{O}$$ and add $$\cal{e}$$ to $$\cal{O}$$ and $$\cal{o}$$ to$$\cal{E}.$$ The left hand side of $$(1)$$ is incremented by $$2(\cal{o}-\cal{e}).$$ Repeat this step until $$(1)$$ is satisfied or if you are bored.
5. If $$(1)$$ holds then assign the elements of $$\cal{O}$$ to $$d_9, d_7, d_5, d_3$$ in an arbitrary way and assign the elements of $$\cal{E}$$ to $$a_8, a_6, a_4$$ also in an arbitrary way. Now $$t\mid \langle d_9 d_8 d_7 d_6 d_5 d_4 d_3 d_2 d_1 0 \rangle, \; \forall t \in \{2,3,4,5,6,8, 9, 10,11\}$$ holds.

Example:

The smallest valid value for $$\langle a_2 a_1 \rangle$$ is $$12.$$ The values $$00, 04, 08, 20$$ are not valid because they contain $$d_0.$$ The numbers $$44$$ and $$88$$ are not valid because $$d_2=d_1$$, so the number cannot be a permutation.

So $$d_1=6$$ and $$d_2=1$$, we set $$\cal{O}=\{2,3,4,5\}$$ and $$\cal{E}=\{7,8,9\}$$. The left hand side of $$(1)$$ is $$-14+24+1-6=-5.$$ Now we shift $$7$$ to $$\cal{O}$$ and $$4$$ to $$\cal{E}.$$ This decreases the LHS of $$(1)$$ by $$6$$ to $$-11$$ and we are done. So we have $$\cal{O}=\{2,3,5,7\}$$ $$\cal{E}=\{4,8,9\}$$ $$\langle d_2 d_1 d_0 \rangle =160$$ and can construct the number $$2435879160$$ $$\square$$

We can generate $$4!\cdot 3!=144$$ different numbers from our sets $$\cal{O}$$ and $$\cal{E}.$$ There is a good chance that about $$\frac{1}{7}$$ of these 144 numbers are divisible by $$7$$, these are about $$20$$ numbers. If there is no such number we can construct other numbers by repeating steps 2 to 5.

Here number $$2435879160$$ is already divisible by $$7.$$

We just need a number divisible by $$5,7,8,9,11$$ and everything else is automatic. Divisibility by $$9$$ isn't a concern, as the digits already sum to $$45$$ and $$9\mid45$$. The number must end with $$0$$ since it's even and divisible by $$5$$. The last three digits must be divisible by $$8$$, so they're some multiple of $$040$$ (of course $$040$$ isn't actually a valid candidate, since it repeats $$0$$ twice). Divisibility by $$11$$ means the alternating sum of the digits must be a multiple of $$11$$. Divisibility by $$7$$ means the first $$9$$ digits is a multiple of $$7$$. Now, I think the most efficient method is to write a program taking into account all of these parameters to find a numerical answer.

• I don't think that one should use a program to solve this problem. – miracle173 Oct 27 '18 at 16:24
• @miracle173 Well, I guess that is the easy way out. Since I posted my answer sirous and you have posted pen-and-paper solutions, but of course it's quite tedious. – YiFan Oct 27 '18 at 16:26

COMMENT.- It is clear that the required number, $$N$$, must be a multiple of $$2^3\cdot3^2\cdot5\cdot7\cdot11=27720$$ so we must have $$N=27720x$$ where $$x$$ is such that $$N$$ have ten (distinct) digits. It follows after a calculation that if there is solution then $$x$$ is an integer such that$$36076\le x\le360750$$ In other words, $$x$$ is a number belonging to a set of $$324675$$ integers.

The number which are divisible by $$8$$ is also divisible by $$2$$ and $$4$$.

The number which are divisible by $$9$$ is also divisible by $$3$$.

The number of which is divisible by $$6$$ is also divisible by $$2$$ and $$3$$.

The number which are divisible by $$10$$ is also divisible by $$2$$ and $$5$$.

Also also the number we expect is divisible by $$11$$ and $$7$$.

So the number is in the form $$=P×2^{3i}×3^{2j}×5^k×7^m×11^n$$, Where $$i$$, $$j$$, $$k$$, $$m$$, & $$n$$ are positive any positive integer and $$P$$ is any positive integer integer.Using this condition we will produce a required ten digit number.

• This is not correct. You need something in the form of $k \times 2^3 \times 3^2 \times 5 \times 7 \times 11$. What you have is only a subset (and a quite restrictive one of that) of the numbers that fulfill the divisibility criteria described. – Jean-Luc Bouchot Oct 27 '18 at 2:38
• @Jean-LucBouchot yes Sir. Absolutely. I forget to include this. Anyhow Thanks much. – Avinash N Oct 27 '18 at 2:45
• Why did I get downvote? Then mentioned me where the mistake occurs. It will help me to correct myself. Thank you. – Avinash N Oct 27 '18 at 5:38
• I voted this down. @Jean-LucBouchot already showed you what was wrong. And it is still wrong. e,g 16*9*5*7*11 is not contained in your set. And even if you replace it by Jean's correct formula, how does this answer the question? How do you use this formula to create such a number or to proof that such a number does not exist? – miracle173 Oct 27 '18 at 6:11
• @miracle173 oh yes. There is a mistake. Thanks much. Any help to fix this issue? It is greatly appreciated... – Avinash N Oct 27 '18 at 12:00