A $56$-digit number divisible by $13$

Question

Let $N$ be a $56$-digit number with all the digits same except the $32$nd digit from the right which is a different one. If $N$ is divisible by $13$, then which digits can never be the units digit of $N$?

I tried to approach this question with the help of divisibility rules available for $13$ but I was not able to figure out the solution for this. Can someone please explain the way to solve this?

Update : As many of you guys are helping with the solution and thanks for that...I am just putting down the answer over here... the correct answer is 4 and 7.

Answer 1

Let $N$ have digit $a$ $55$ times and digit $b$ once at $32$nd place from right.

Now $13$ divides any block of six same consecutive digits $$13 \mid a\cdot 111111 \cdot 10^m \quad , \quad m \in \{0,1,2,\ldots\} $$

There are five blocks of $aaaaaa$ before $31$st digit and four blocks of $aaaaaa$ after $32$nd digit. So $13$ divides $N$ iff $13$ divides the remaining two digit number formed by $32$nd and $31$st digits. $$13 \mid ba$$

Looking at two-digit multiples of $13$, $a$ cannot be $0,4,7$.

Answer 2

Notice that $\frac{10^{56}-1}9$ in decimal is a string of 56 ones, so $$N=a\frac{10^{56}-1}9+(b-a)10^{31}$$ where $1\le a\le9$ is the repeated digit and $0\le b\le9$ is the different digit.

Looking mod 13, we have $9^{-1}=3$, and using that $10^6\equiv1$, we have $$ 10^{56}=(10^6)^910^2\equiv1^910^2\equiv9\\ 10^{31}=(10^6)^510^1\equiv1^510^1=10. $$

Therefore, the statement that $N$ is divisible by 13 is equivalent to the (mod 13) congruence $$ 0\equiv a(9-1)3+(b-a)10\\ 0\equiv 14a+10b\\ 3b\equiv a. $$ This means we can use any digit $a$ as long as there is a digit $b$ such that $a\equiv3b$ (mod 13). The first ten multiples of 3, corresponding to $b=0,\dots,9$, are $a=0,3,6,9,12,2,5,8,11,1$. (The next values $a=4,7,10$ correspond to $b=10,11,12$.) So $a$ can't be 4 or 7.

Answer 3

The division rule of $13$ is that if you take the $k$ and $k+3$ digit of any number, and increase or decrease them both by the same amount, then the divisibility by $13$ of the result will be unchanged.

(This is because increasing of decreasing those digits is the same as adding or subtracting a multiple of $1001$ and $1001$ is a multiple of $13$.)

We can use this method to completely eliminating the smaller digit while subtracting the smaller digit from the larger digit. Also, if its convenient to do so, we can do this to three pairs of digits at a time and increase any six consecutive digits a time.

(We can think of this as adding or subtracting a multiple of $111111 = 111\cdot 1001$ which is a multiple of $13$.

Sooooo...

$N=\underbrace{\underbrace{aaa.....a}_{24}\color{red}b\underbrace{aaa....}_{31}}_{56}=$

$\underbrace{\underbrace{aaaaaa}.....\underbrace{aaaaaa}}_{4\text{ groups of }6}ba\underbrace{\underbrace{aaaaaa}.....\underbrace{aaaaaa}}_{5\text{ groups of }6}\equiv $

$\underbrace{\underbrace{000000}.....\underbrace{000000}}_{4\text{ groups of }6}ba\underbrace{\underbrace{000000}.....\underbrace{000000}}_{5\text{ groups of }6}\pmod {13}\equiv$

$ba\times 10^{30}=$

$ba\times 10^{30} + ba\times 10^{27} - ba\times 10^{27} =$

$ba\times 1001\times 10^{27} - ba\times 10^{27}\equiv $

$-ba \times 10^{27} \pmod{13}\equiv $

$-ba \times 10^{27} - ba \times 10^{24} + ba\times 10^{24} \equiv $

$-ba\times 1001\times 10^{24} + ba\times 10^{24}\equiv$

$ba \times 10^{24} \pmod {13}\equiv$

$....$

$ba \times 10^{18} \pmod {13}\equiv$

$....$

$....$

$ba \times 10^0 \equiv ba\equiv 10b + a\pmod{13}$

So if $N$ is divisible by $13$ then $ba$ is divisible by $13$. Assuming $a$ and $b$ are not both $0$ there are $7$ two digit numbers divisible by $13$ and of the possible values of $a$ only $4$ and $7$ never occur. (The seven two digit multiples of $13$ are $13, 26,39,52, 65, 78,91$.)

........

A more sophisticated way but the exact same idea would be to note $1001 \equiv 0 \pmod{13}$ so $10^3 \equiv -1 \pmod {13}$ and by induction.

$10^{6k}\equiv 1 \pmod {13}$ and $10^{6k + 3}\equiv -1 \pmod {13}$.

This also means $10^{6k +i} a \equiv - 10^{6k + i + 3}a\pmod {13}$ and $10^{6k+i}a + 10^{6k+i+3} \equiv 0 \pmod{13}$

Therefore:

$N = \sum_{i=0; i\ne 31}^{55} 10^ka+ b10^{31}=$

$\sum_{i=0}^{55} 10^k a + (b-a)10^{31}\equiv$

$\sum_{i=0}^1 10^ka + \sum_{j=0}^{53}10^{k+2}a + (b-a)\cdot 10=$

$11a + \sum_{m=0}^8(\sum_{n=0}^n (10^{6m + n+2}a + 10^{6m + n + 2 + 3}a) + (b-a)\cdot 10 \equiv $

$11a + 0 + (b-a)10 \equiv 10b + a \pmod{13}$

Again we can look at all $7$ of $10b + a\equiv 0 \pmod {13}$ or we can still be more sophisticated.

$10b + a \equiv a -3b \pmod{13}$ so if $N \equiv 0 \pmod{13}$ then

$a \equiv 3b \pmod{13}$.

$13$ is prime so multiplication and addition is a field $\pmod {13}$ and we will $a\equiv 3b \equiv 3\times 10\equiv 30\equiv 4 \pmod{13}$ if and only if $b \equiv 10 \pmod {13}$ and likewise $a \equiv 3b \equiv 3\times 11\equiv 33\equiv 7\pmod {13}$ if and only if $b \equiv 11 \pmod{13}$ and $a \equiv 3b \equiv 3\times 12 \equiv 10\pmod {13}$ if and only if $b \equiv 12 \pmod {13}$.

And as $0 \le b < 10$ we can not have any of those cases, so we can not have $a \equiv 4$ or $7\pmod {13}$. so $a$ can not be $4$ or $7$.