2
$\begingroup$

Is there a (number theoretic or algebraic) trick to find a large nunber modulo some number?

Say I have the number $123456789123$ and I want to find its value modulo some other number, say, $17$.

It's not fast for me to find the prime factorisation first. It's also not fast to check how many multiples of $17$ I can "fit" into the large number.

So I was wondering if there is any method out there to do this efficiently.

I am looking for something like the other "magic trick" where you sum all the digits and take the result $\mod 9$.

$\endgroup$
5
$\begingroup$

The best I could come up with is to use 17*6 = 102. Dividing by 102 goes pretty fast...

 123456789123
  214
   105
     367
      618
        691
         792
          783
           69

 and 69 mod 17 = 1

addendum

You can speed things up by trying to eliminate two digits at a time

 123456789123
 1224
 ----
   1056
   1020
   ----
     3678
     3672
     ----
        6912
        6834
        ----
          783
          714
          ---
           69

 and 69 mod 17 = 1

for really large numbers

For really large numbers, you can use the fact that 17 | 100,000,001

The procedure is similar to the check for divisibility by 11, except you break the number up into larger chunks.

Starting from the right, split the number up into 8-digit chunks.
So 123456789123 becomes

 chunk #         1     2
 chunk    56789123  1234

Compute (sum of odd numbered chunks) - (sum of even numbered chunks)

56789123 - 1234 = 56787889

If the result is negative, add a big enough multiple of 100,000,001 to
make it positive.

This number is congruent to the original number modulo 17.

56787889
5610
----
  6878
  6834
  ----
    4489
    4488
   -----
       1

and, again, we get 1

| cite | improve this answer | |
$\endgroup$
  • $\begingroup$ This is a special case of the universal divisibility test (using various chunks sizes), see my answer. Both (well-known) methods were already mentioned in Lab's prior answer. $\endgroup$ – Bill Dubuque Oct 12 at 0:18
2
$\begingroup$

$10^2\equiv-2\pmod{17}\implies10^4=(10^2)^2\equiv(-2)^2\equiv4;$

$\displaystyle\implies\sum_{r=0}^na_r10^r\equiv(4)^0(a_3a_2a_1a_0)+(4)^1(a_7a_6a_5a_4)++(4)^2(a_{11}a_{10}a_9a_8)+\cdots\pmod{17}$

Again, $10^8\equiv(-2)^4\equiv-1$

$\displaystyle\implies\sum_{r=0}^na_r10^r\equiv(-1)^0(a_7a_6a_5\cdots a_0)+(-1)^1(a_{15}\cdots a_8)+\cdots\pmod{17}$

| cite | improve this answer | |
$\endgroup$
  • $\begingroup$ Undoubtedly you know this, but in case others are wondering: for any prime $p>2$ we have $10^{(p-1)/2}\equiv\pm1\pmod p$. The sign here depends on whether $10$ is a quadratic residue modulo $p$ or not. That, in turn, can be easily determined using the law of quadratic reciprocity. This leads to a divisibility rule like the one here in chunks of $(p-1)/2$ digits. In some cases we can do shorter chunks. The best known cases of that are perhaps $p=13$ ($10^3\equiv-1$) and $p=41$ ($10^5\equiv1$). $\endgroup$ – Jyrki Lahtonen Aug 22 '15 at 19:27
  • $\begingroup$ This is a special case of the universal divisibility test (using various chunks sizes), see my answer. $\endgroup$ – Bill Dubuque Oct 12 at 0:18
1
$\begingroup$

Well, it is fast to divide 17 into that number.

Where you can gain a lot is when the number you want to be divide is a special form such as $a^n$, where $n$ is large. There are ways (usually involving the Euler $\phi$ function) for rapidly computing $a^n \bmod{b}$ where $n$ is large.

A good start is to remember that $a^n \bmod{b} =(a\bmod{b})^n \bmod{b} $.

| cite | improve this answer | |
$\endgroup$
1
$\begingroup$

Yes, use the universal divisibility test: $ $ repeatedly replace leading digit chunks by their remainder mod the divisor as below, using least magnitude remainders $\, -8\le r \le 9\,$ to simplify arithmetic $\!\bmod 17\ $ (so negative digits occur, denoted $-d,c := 10(-d)+c\equiv 7d+c,\,$ by $10\equiv -7)$ $$\begin{align} \!\bmod 17\!:\,\ 10\equiv -7\ \Rightarrow\quad\ \ &\ \color{#0A0}{1\ 2}\,\ 3\ 4\ 5\ 6\ \ \ {\rm by}\,\ \ \ \ \ \ \color{#0a0}{1\:\!2\equiv -5}\\[.1em] \equiv\, &\ \color{#0A0}{{-5}},\color{#c00} 3\ 4\ 5\ 6\ \ \ {\rm by}\,\ \color{#0a0}{{-}5},\color{#c00}3\equiv\ (\,7\,)\, \color{#0a0}{5}+\color{#c00}3\,\equiv\,\color{#0af} 4\\[.1em] \equiv\, &\ \ \ \ \ \ \ \ \color{#0af}4\ 4\ 5\ 6\ \ \ {\rm by}\,\ \ \ \ \ \ \color{#0af}4\:\!4\equiv (-7)4+4\,\equiv\color{#f60}{-7}\\[.1em] \equiv\, &\ \ \ \ \ \ \ \ \color{#f60}{{-}\!7}, 5\ 6\ \ \ {\rm by}\,\ \color{#f60}{{-}7},5\equiv\,(\,7\,)\, \color{#f60}{7}+5\,\equiv\, 3\\[.2em] \equiv\, &\ \ \ \ \ \ \ \ \ \ \ \ \ \ 3\ 6\ \ \ \:\!\:\!{\rm by}\ \ \ \ \ \ 3\:\! 6\equiv (-7)3+6\,\equiv\, 2\\ \equiv\, &\qquad\qquad\ 2;\ \ {\it quicker,}\,\ 2 \,\text{ digits at a time:}\\[.4em] \!\bmod 17\!:\,\ 10^2\equiv -2\ \Rightarrow\quad\ \ &\ \color{#0A0}{12\ 3 4}\ 56\ \ \ {\rm by}\,\ \color{#0A0}{12\ 3 4}\equiv\, (-2)\color{#0a0}{\,12+34\equiv 10}\\[.1em] \equiv\, &\ \ \ \ \ \ \color{#0A0}{{10}}\ \color{#c00}{56}\ \ \ {\rm by}\,\ \color{#0a0}{10}\ \color{#c00}{56}\equiv\ (-2)\, \color{#0a0}{10}+\color{#c00}{56}\,\equiv\,\color{#0af}2\\[.2em] \equiv\, &\qquad\quad\ \color{#0af}2 \end{align}\qquad\qquad$$

So $\rm\, 123456\equiv 2\pmod{\!17}.\,$ Indeed $\rm\, 123456 = 7262\cdot 17+2.\,$ Continuing this way we can do the entire number in a couple minutes of mental arithmetic. Unlike some other divisibility tests that compute only a binary truth value, this method has the advantage of computing the remainder. Further, it doesn't require remembering any special algorithm or parameters for each modulus.

Remark $ $ Lab & Steven's answers are a special case of above (but without mod arithmetic optimizations), i.e. they use chunk sizes of $\,2\,$ and $\,8,\,$ using $\bmod 17\!:\ 10^2\equiv -2,\ 10^8\equiv -1$.

| cite | improve this answer | |
$\endgroup$
  • $\begingroup$ See here for another example using negative digits. $\endgroup$ – Bill Dubuque Oct 29 '18 at 23:10
0
$\begingroup$

No, there is not. The reason why "magic tricks" work when studying divisibility by $2,3,5,11$ is the fact that we usually write in base $10$. Change the base and they will stop working. In particular, the following trick would work in base $17$: if the last digit of your number is $0$ then the number is divisible by $17$. Of course, in order to check this you would need to write it in base $17$, which is a vicious circle...

| cite | improve this answer | |
$\endgroup$
  • $\begingroup$ Great, where can I read about the tricks you mention for $2,3,5,11$? (you don't mention $9$...?) $\endgroup$ – learner Aug 23 '15 at 4:29
  • 1
    $\begingroup$ @learner: I don't know of any book, I know them from elementary school: for $2$, the last digit must be even; for $3$ the sum of the digits must be divisible by $3$; for $4$, the number formed by the last 2 digits must be divisible by $4$; for $5$, the last digit must be $0$ or $5$; for $8$, the number formed by the last 3 digits must be divisible by $8$; for $10$, the last digit must be $0$; for $11$, sum all the digits on odd positions, sum all the digits on even positions and check whether the difference of these 2 numbers is divisible by $11$. $\endgroup$ – Alex M. Aug 28 '15 at 10:59

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.