12
$\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$
  • $\begingroup$ "$135792468$ $135792468$" is two numbers!!! $\endgroup$ – barak manos Nov 26 '16 at 13:54
  • $\begingroup$ @barakmanos it's one? There shouldn't be a space in between tho $\endgroup$ – NAA Nov 26 '16 at 13:56
  • $\begingroup$ @barakmanos I have to show the working! $\endgroup$ – NAA Nov 26 '16 at 14:17
  • 1
    $\begingroup$ Have you tried putting it divided by 13 into a calculator? $\endgroup$ – The Great Duck Nov 27 '16 at 22:31
  • $\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 Nov 28 '16 at 0:37
19
$\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$
  • 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 Nov 27 '16 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$ – barak manos Nov 27 '16 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$ – barak manos Nov 27 '16 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$ – barak manos Nov 27 '16 at 11:48
  • $\begingroup$ That makes a lot of sense now and is a lot simpler than I expected! +1 $\endgroup$ – Darren H Nov 27 '16 at 14:21
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$
  • 5
    $\begingroup$ +1 because this is an approach which someone with no knowedge of divisibility tests can come up with. $\endgroup$ – Wojowu Nov 26 '16 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 Nov 27 '16 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$ – Bill Dubuque Nov 27 '16 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$ – Bill Dubuque Nov 27 '16 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$ – Bill Dubuque Nov 27 '16 at 18:51
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$
7
$\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$
  • 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$ – Marc van Leeuwen Nov 27 '16 at 15:36
5
$\begingroup$

Notice $\ 13\mid n\,10^{\large 9}\!+n = 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 $\ $ In the same way we can quickly see that $\,7,11,19\mid 10^{\large 9}+1$

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

$\endgroup$
  • $\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$ – Ilmari Karonen Nov 27 '16 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$ – Bill Dubuque Nov 27 '16 at 22:37

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.