13
$\begingroup$

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!

$\endgroup$
4
  • $\begingroup$ "$135792468$ $135792468$" is two numbers!!! $\endgroup$ Commented Nov 26, 2016 at 13:54
  • $\begingroup$ @barakmanos it's one? There shouldn't be a space in between tho $\endgroup$
    – NAA
    Commented Nov 26, 2016 at 13:56
  • $\begingroup$ @barakmanos I have to show the working! $\endgroup$
    – NAA
    Commented Nov 26, 2016 at 14:17
  • $\begingroup$ The intent is likely to solve by some variant of "divisible by 100..001", but long division (or synthetic division) solves this problem. There's no reason to make things more complicated than necessary. $\endgroup$
    – Nate 8
    Commented Nov 28, 2016 at 0:37

5 Answers 5

26
$\begingroup$

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.$$

$\endgroup$
8
  • 5
    $\begingroup$ +1 because this is an approach which someone with no knowedge of divisibility tests can come up with. $\endgroup$
    – Wojowu
    Commented Nov 26, 2016 at 17:01
  • 5
    $\begingroup$ +1 as well because this approach is generally applicable. A bag of tricks that only work in rare cases isn't very useful. Take the question, replace 13 with 17, and see which answer still applies. $\endgroup$
    – gnasher729
    Commented Nov 27, 2016 at 13:27
  • $\begingroup$ @gna This is equivalent to using the division algorithm to divide by $13$ (while ignoring quotients). Yes, it will always work, but it will be much more work for numbers that have special form, such as the OP's $\,n(\color{#c00}{10^9+1}).\,$ Here the modular approach is much, much simpler, namely $$\,\ {\rm mod}\ 13\!:\,\ \color{#c00}{10^{\large 9}}\equiv ((-3)^{\large 3})^{\large 3}\equiv (-1)^{\large 3}\equiv\,\color{#c00}{-1}$$ $\endgroup$ Commented Nov 27, 2016 at 15:52
  • $\begingroup$ @Yves But there are no "properties of the divisor" to find. Rather we need only compute $\,\color{#c00}{10^{\Large 9}\bmod 13}\,$ which is simple and fast (even if done non-optimally by brute force). Taking advantage of innate power structure will almost always give major speedups over long division in problems like this. $\endgroup$ Commented Nov 27, 2016 at 16:09
  • 1
    $\begingroup$ @Wildcard To be sure, I agree that this method is useful when special structure is lacking. Indeed, as I said above, I often recommend essentially the same method (including same color highlighting!) as a universal divisibility test.. I too am glad it was posted, since such ideas deserve to be much better known - as do many of the beautiful simplifications made possible via modular viewpoints. A large number of my posts are devoted to attempting to reveal such beauty in elementary number theory. $\endgroup$ Commented Nov 27, 2016 at 18:51
20
$\begingroup$

$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.

$\endgroup$
7
  • 8
    $\begingroup$ As a software dev with a passing interest in mathematics Yves' answer is immediately obvious to me, but I'm unclear about yours. It seems to follow some externally proven rule that I'm unaware of. Would you care to elaborate or at least link me to where I can investigate this rule myself? $\endgroup$
    – Darren H
    Commented Nov 27, 2016 at 10:01
  • 2
    $\begingroup$ @DarrenH: You can prove this by induction. The base cases are a $6$-digit number $\overline{abcdef}$ and a $9$-digit number $\overline{abcdefghi}$ (see following comments). $\endgroup$ Commented Nov 27, 2016 at 11:48
  • 1
    $\begingroup$ $\color\red{\overline{abc}-\overline{def} = 0 \implies \overline{abc} = \overline{def} \implies \overline{abcdef} = 1000\overline{abc}+\overline{def} = 1000\overline{abc}+\overline{abc} = 1001\overline{abc} = 13\cdot77\overline{abc}}$ $\endgroup$ Commented Nov 27, 2016 at 11:48
  • 1
    $\begingroup$ $\color\green{\overline{abc}-\overline{def}+\overline{ghi} = 0 \implies \overline{abc}+\overline{ghi} = \overline{def} \implies \overline{abcdefghi} = 1000000\overline{abc}+1000\overline{def}+\overline{ghi} = 1000000\overline{abc}+1000\overline{abc}+1000\overline{ghi}+\overline{ghi} = 1001000\overline{abc}+1001\overline{ghi} = 13\cdot(77000\overline{abc}+77\overline{ghi})}$ $\endgroup$ Commented Nov 27, 2016 at 11:48
  • $\begingroup$ That makes a lot of sense now and is a lot simpler than I expected! +1 $\endgroup$
    – Darren H
    Commented Nov 27, 2016 at 14:21
10
$\begingroup$

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.)

$\endgroup$
0
8
$\begingroup$

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$.

enter image description here

$\endgroup$
1
  • 3
    $\begingroup$ Note the second factor is $10^9+1$. If you know by heart the handy fact that $13$ divides $1001=10^3+1$ (as do $7$ and $11$, and as remarked elsewhere) then you see $10^3\equiv{-}1\pmod{13}$ and so $10^9+1\equiv(-1)^3+1=0\pmod{13}$. $\endgroup$ Commented Nov 27, 2016 at 15:36
5
$\begingroup$

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} $

$\endgroup$
2
  • $\begingroup$ +1 for an excellent method of solving problems like this, but honestly, your answer would IMO be a lot more readable of you added a few more English words and simplified the notation a bit. As it is, your answer looks kind of like something scribbled on a blackboard during a lecture -- which would be fine on a blackboard, but here on SE people can't hear you explain your thinking as you're writing, so a little more written explanation can be helpful. $\endgroup$ Commented Nov 27, 2016 at 22:22
  • $\begingroup$ @IlmariKaronen One of the goals of my posts here is to teach readers how to think like an algebraist or number theorist. As such, I purposely avoid spurious human language when it obfuscates the essence of the matter. The sooner students learn to wean themselves from the crutches of natural language, the sooner they will be able to concentrate on the mathematical essence of the matter. $\endgroup$ Commented Nov 27, 2016 at 22:37

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .