Is there a method to calculate large number modulo?

Question

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

Answer 1

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

Answer 2

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

Answer 3

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

Answer 4

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

Answer 5

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