Finding the remainder when a large number is divided by 13 Let a number $x = 135792468135792468$. Find the remainder when $x$ is divided by $13$.
Is it possible to use Fermat's little theorem on this? I notice that the number is also repeating after $8$. 
Would really appreciate any help, thanks!
 A: You noticed how the number repeats, so you can see that it equals $135792468\times1000000001$. Now test $1000000001$ for divisibility by $13$ (repeatedly add $4$ times the rightmost digit to the rest of the number, and if you reach a multiple of $13$ (you reach 26 in this case), the original number is divisible by $13$.

A: Note that $\ 13\mid \overbrace{n\,10^{\large 9}\!+n}^{\textstyle n(\color{#c00}{10^{\large 9}\!+1})\!\!}\,\ $  by $\,\ {\rm mod}\ 13\!:\, \overbrace{\color{#c00}{10^{\large 9}}\equiv ((-3)^{\large 3})^{\large 3}}^{\Large (10\ \ \,\equiv\,\ \ -3)^{\LARGE 9}\quad\ \, }\!\!\equiv (-1)^{\large 3}\equiv\,\color{#c00}{{-}1}$

Remark $\ \ 7,11,19\mid 10^{\large 9}\!+1$ all follow similarly
$\qquad \left.\begin{align}
{\rm mod}\ \ 7\!:&\,\ \color{#c00}{10^{\large 3}}\ \equiv\,\ 3^{\large 3}\,\ \equiv\,\ \color{#c00}{{-}1}\\ \\
{\rm mod}\ 11\!:&\,\ \color{#c00}{10^{\large 3}}\equiv (-1)^{\large 3}\equiv\color{#c00}{-1}
\end{align}\right\}\ \Rightarrow\, 10^{\large 9}\equiv (\color{#c00}{10^{\large 3}})^{\large 3}\equiv (\color{#c00}{-1})^3\equiv -1$
$\qquad {\rm mod}\ 19\!:\ 10^{\large 9}\equiv (-3^{\large 2})^{\large 9}\equiv -3^{\large 18}\equiv -1\ $ by little Fermat
The above shows that $\, 7,11,13\mid 10^{\large 3}+1\mid 10^{9}+1\,$ which leads to the well-known divisibility test: casting out $1001$'s, i.e. the remainder $\bmod 1001\! =\! \color{#c00}{10^{\large 3}}$ is the alternating digit sum in radix $10^3,\,$ which is the analog of casting out $11 =$ elevens in radix $10$ (decimal), i.e.
$\begin{align} \bmod 1001\!:\ \ \ \  &\cdots\, d_8 d_7 d_6\,,\, d_5 d_4 d_3\,,\, d_2 d_1 d_0\ \ \text{in radix $\,10^{\large 3}$}\\ \equiv\, &\cdots\,  d_8 d_7 d_6\! \color{#c00}{-\! d_5 d_4 d_3}\!\! +\! d_2 d_1 d_0\end{align}  $ 
A: Brute force isn't demanding so much effort, actually a handful of two-digits subtractions, using the table $13,26,39,52,65,78,91,104,117$.
$$\color{blue}{13}5792468135792468\\\color{blue}{57}92468135792468\\\color{blue}{59}2468135792468\\\color{blue}{72}468135792468\\\color{blue}{74}68135792468\\\color{blue}{96}8135792468\\\color{blue}{58}135792468\\\color{blue}{61}35792468\\\color{blue}{93}5792468\\\color{blue}{25}792468\\\color{blue}{127}92468\\\color{blue}{109}2468\\\color{blue}{52}468\\\color{blue}{46}8\\\color{blue}{78}\\\color{blue}0.$$
A: $135-792+468-135+792-468=0\implies$


*

*$7$ divides $135792468135792468$ without remainder

*$11$ divides $135792468135792468$ without remainder

*$13$ divides $135792468135792468$ without remainder


This trick is applicable since each one of them divides $1001$ without remainder.
A: A little digression to speculate on the source of the problem.
The test for divisibility by $9$ is well known: the remainder is the sum of the digits (mod $9$).
The test for divisibility by $11$ is a little less well known: look at the alternating sum of the digits. That works because odd powers of $10$ are $-1 \pmod{11}$ while even powers are $1$.
Now note the lovely fact that $7 \times 11 \times 13 = 1001$. That means you can find the remainder mod $1001$ and hence mod $7$, $11$ and $13$ by alternately adding and subtracting "digits" in groups of three - essentially thinking of the number as written in base $1000$.
(Written while @Barakmanos was posting essentially the same argument.)
