Find the remainder when $123412341234$...(written $1234$ times) is divided by $13$
Find the remainder when $123412341234$...(written $1234$ times) is divided by $13$
I divided $1234$ by $13$ and I got the answer $12$ which is the correct answer but what is the approach behind solving this one?
$\endgroup$ 25 Answers
$\begingroup$$\underbrace{1234}_{\text{written } 1234\text{times}}\cdots=1234\sum_{r=0}^{1233}(10^3)^r$
Now $S=\sum_{r=0}^{1233}(10^3)^r=\dfrac{10^{3\cdot1234}-1}{10^3-1}$
Now $10^3\equiv-1\pmod{13}\implies10^{3\cdot1234}\equiv(-1)^{1234}\equiv1$
As $(10^3-1,13)=1,13|S$
$\endgroup$ 3 $\begingroup$\begin{eqnarray*} 1234 \equiv 12 \pmod {13} \\ 12340000 \equiv 10 \pmod {13} \\ 123400000000 \equiv 4 \pmod {13}. \\ \end{eqnarray*}Now note that $12+10+4$ is divisible by $13$, So everytime you tack $123412341234$ on the end of the number its divisibility by $13$ will not change ... so we can discard the first $1233$ $1234$'s so we need only consider the first $1234$, which we have already seen to give a remainder of $12$ when divided by $13$.
So the answer is $\color{red}{12}.$
$\endgroup$ $\begingroup$Write this number in a "ten thousand system": $$\sum_{k=0}^{1233}1234\cdot 10000^k=1234\cdot\sum_{k=0}^{1233}10000^k.$$ Then it is enough to find the remainders of $1234$ and the powers of $10000$, which is very easy task.
In a meantime I have found nicer answer: observe that $10000^3$ gives the remainder $1$ and $123412341234$ is divisible by $13$. This shows that our number is divisible by $13$!!!. See:
$$ 123412341234\cdot\sum_{k=0}^{410}(10000^3)^k $$
is a number we are dealing with.
$\endgroup$ 5 $\begingroup$I wanted to see why your approach worked, OP. That is, why was the answer $1234 \mod 13$? Here is what I found.
There are $1234$ blocks of "$1234$" to consider. But consider that
$$123412341234 \mod 13 = 0$$
Thus there are $411$ blocks of "$123412341234$" with one remaining $1234$. The answer must be
$$1234 \mod 13 = 12$$
$\endgroup$ 3 $\begingroup$Guys I don't really have a background in maths, so I can't get into depth as previous answers have. What I can help with is the business end for comp exams.
There are 2 basic rules here. If A is any Digit or Number, then AAAAAAAA upto P-1 times is divisible by P (any prime no except 2,3,5,11).
So since no is written 1234 times. Divide that by (13-1)= 12. Remainder is 10. So you need to only consider the last 10 times it is written, as the rest are divisible.
Here comes the second rule. For test of divisibility for 13. You make blocks of 3 now starting from the right. Ie, 432/143/214/321/432/143..and so on . If the difference of the sum of even an odd blocks is 0 or a multiple of 13 , the number is divisible. You'll see that the blocks start repeating after every 12 digits. 1234 written 10 times has 40 digits. 40÷12 gives remainder 4. Hence only last 1234 set isn't perfectly divisible by 13. Divide 1234/13 and you get remainder 12 which is your answer.
Kinda long, yes, but still doable in exam mode.
$\endgroup$
