6
$\begingroup$

$N$ is a $50$ digit number (in the decimal scale). All digits except the $26^{th}$ digit (from the left) are $1$. If $N$ is divisible by $13$, find the $26^{th}$ digit.

This question was asked in RMO $1990$ and is very similar to this question and the same as this question but it is not solved by the approach used by me whereas I want to verify my approach.

My approach:

Suppose $N=111\cdots a\cdots111$ and $N\equiv 0\pmod {13}$

Now $N=10^{49}+10^{48}+\ldots+a10^{24}+\ldots+10+1=(10^{49}+10^{48}\ldots+10+1)+(a-1)10^{24}$

$N=\dfrac{10^{50}-1}{9}+(a-1)10^{24}$

Now $10^{12}\equiv 1\pmod {13}\Rightarrow 10^{24}\equiv 1\pmod {13}$ by fermat's little theorem.

Thus $(a-1)10^{24}\equiv (a-1) \pmod{13}\Rightarrow \dfrac{10^{50}-1}{9}\equiv 1-a\pmod{13}$ since $N\equiv 0\pmod{13}$

$10^{24}\equiv 1\pmod{13}\Rightarrow 10^{48}\equiv 1\pmod{13}$ or $10^{50}-1\equiv -5 \pmod{13}$

Now $10^{50}-1\equiv -5\pmod {13}\Rightarrow 9(1-a)\equiv -5\pmod{13}$

$a=3$ clearly satisfies the above conditions

$\therefore$ The $26^{th}$ digit from the left must be $3$.

Please suggest what is incorrect in this solution and advice for alternative solutions.

THANKS

$\endgroup$
7
  • 1
    $\begingroup$ $111111$ is divislbe by $13$ so only consider 25th and 26th digits $\endgroup$
    – Math Lover
    Sep 1, 2020 at 9:25
  • 1
    $\begingroup$ @Peter Yes, but by then they have already multiplied away the denominator; note how $4$ became $36$. $\endgroup$
    – Arthur
    Sep 1, 2020 at 9:26
  • $\begingroup$ @MathLover But we can also consider the residues of $\frac{10^{50}-1}{9}$ and $10^{24}$ mod $13$ to get the solution. $\endgroup$
    – Peter
    Sep 1, 2020 at 9:29
  • 1
    $\begingroup$ @Peter absolutely we can and OP's is the right way to do it. I was just making a comment that if we know $111111$ is divisible by $13$, we can ignore first $24$ and last $24$ $1's$. $\endgroup$
    – Math Lover
    Sep 1, 2020 at 9:32
  • 2
    $\begingroup$ @Peter If we want to add $10^{50} + 10^{49} + \cdots + 10 + 1$, then that becomes $\frac{10^{51} - 1}9$. Turns out, however, that that's not what we want to add. So yes, the exponent in the fraction should've been $50$, but only because the original sum was not the one we were after, not because of an arithmetical error. $\endgroup$
    – Arthur
    Sep 1, 2020 at 9:32

4 Answers 4

2
$\begingroup$

$10^{50}$ is a 51-digit number. And in a 50-digit number, the digit 26th from the left is represented by $10^{24}$.

Other than these two mistakes, I find your approach entirely reasonable. And if they were looking for a 51-digit number, with all except the 25th digit from the left being $1$, then it would've been correct too.

Edit: After having corrected these two off-by-one errors, the solution looks fine.

$\endgroup$
6
  • $\begingroup$ I'm sorry if I am mistaken, but wouldn't the 26th digit frmo the left be represented by $10^{25}$? $\endgroup$ Sep 1, 2020 at 9:28
  • $\begingroup$ @DevanshKamra In a 51-digit number, yes. Not in a 50-digit number. $\endgroup$
    – Arthur
    Sep 1, 2020 at 9:28
  • $\begingroup$ Okay, let me correct the question $\endgroup$ Sep 1, 2020 at 9:29
  • $\begingroup$ Please check the question now. Is it correct now? $\endgroup$ Sep 1, 2020 at 9:37
  • $\begingroup$ @DevanshKamra It looks good to me, yes. $\endgroup$
    – Arthur
    Sep 1, 2020 at 9:39
2
$\begingroup$

Another way is to use the trick from Wikipedia (that doesn't solve your solution)

Taking $N$ from the right, and applying the sequence $(1, −3, −4, −1, 3, 4)$ as instructed on the page (multiply the digits from the right by the given numbers in sequence), we get

$0$ for the 6 first digits from the right ($1-3-4-1+3+4=0$), repeating the sequence, $0$ up to digit 24 (from right), we still have $0$

Then, the next $6$ are our $a$ and $5\times 1$, or $$a-3-4-1+3+4\\=a-1$$

We did $30$ digits, $20$ to go. The next $18$ will give $0$, the last $2$ give $1-3$, thus the whole sum is $$a-1-2=a-3$$ The only digit that would have $a-3\equiv 0\pmod {13}$ is $$\bbox[5px,border:2px solid #ba9]{a=3}$$

$\endgroup$
1
  • $\begingroup$ not a general approach, but quite a neat one. Thanks for this approach (+1) $\endgroup$ Sep 1, 2020 at 9:50
1
$\begingroup$

After your editions, your approach is correct. Here's an alternative one:

The number $N$ consists of $24$ ones followed by the two digits $1a$ (the $2$-digit number $10+a$) followed by another $24$ ones, so with the number $M$ consisting of $24$ ones, $M:=\sum_{k=0}^{23}10^k=\frac{10^{24}-1}{9}$, we have $$N=M\cdot10^{24+2}+(10+a)\cdot10^{24}+M$$ Since $13$ is a prime, from Fermat's Little Theorem we know that $10^{12}\equiv1\pmod{13}$, and it follows that $13\mid(10^{12}-1)(10^{12}+1)=10^{24}-1=9M \Rightarrow 13\mid9 \lor 13\mid M$. Obviously, $13\nmid 9$, so $13\mid M$.

Now, if $13\mid N$, it follows that $13\mid (10+a)\cdot10^{24}$, and since $13\nmid10^{24}$, it must be $13\mid10+a$. Since $0\le a\le9$, it must be $a=3$.

$\endgroup$
1
  • $\begingroup$ That certainly is a good approach. (+1) $\endgroup$ Sep 1, 2020 at 14:14
0
$\begingroup$

There's several tricks you can use but mostly they are similar to yours.

A famous well known trick is that as $1001 = 13*7*11$ so your number, $N$ is divisible by $13$ if and only if the $N- 1001*10^k$ is divisible by $13$ and so we can remove any pairs of $1$s if there are $3$ spaces apart. So we can get rid of the $1$ and $4$ one, the $2$nd and $5$ one, and the third and $6$th ones to get rid of the first $6$ ones ($111111\div 13 = 8547$ BTW). We can repeat that $4$ times to get rid of the first $24$ ones, and do it to the end to get rid of the last $24$ ones to and up with $11111...11d111.....11$ is divisble by $13$ if and only if $1d00000....000= (10+d)\times 10^{24}$ is.

Now $1001 = 13*7*11$ so $100\equiv -1 \pmod 13$ so $10^{24} = 1000^{8}\equiv (-1)^8\equiv 1 \pmod {13}$. So $(10+d)\times 10^{24}\equiv (10+d)\times 1\equiv 10+d \pmod {13}$ so if this is divisble by $13$ we must have $d = 3$.

That was tedious.....

We could also do, by Fermat's little Theorem $10^{12} \equiv 1 \pmod {13}$ so $10^{12}- 1 =999999999999 \equiv 0 \pmod 13$ so $13$ divides $999999999999 = 9\times 111111111111$ and so $13$ divides $9$ or $111111111111$ so $13|111111111111$ and we do similar to above to get $(10+d)\times 10^{24}$ and as $10^{12} \equiv 1$ then $10^{24} \equiv 1$ and $10+d\equiv 0$ so $d = 3$.

.....

Or we could realize the remainder of $10\div 13$ is $10$. The remainder of $10^2 \div 13$ is $9$ and so on, and these must eventually cycle through. Just list them all: $10 \equiv 10; 10^2\equiv 9; 10^3 \equiv 12 \equiv -1$. SO $10^4\equiv -10\equiv 3$ and $10^{5}\equiv -9\equiv 4$ and $10^6\equiv 1$ and then it repeats. And add them all up. (In groups of $6$ whe get $\sum_{k=0}^5 10^k \equiv 1+10 + 9+(-1)+(-10)+(-9) \equiv 0$ so $13|111111$)

All of theses are more or less the same idea and lead to the conclusion $d=3$.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.