# Is there a method to calculate large number modulo?

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

• – lab bhattacharjee Aug 22 '15 at 4:24
• Don't even think about factorisation here! Division is much faster. – TonyK Aug 22 '15 at 19:20

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


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

• 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. – Bill Dubuque Oct 12 at 0:18

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

• 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$). – Jyrki Lahtonen Aug 22 '15 at 19:27
• This is a special case of the universal divisibility test (using various chunks sizes), see my answer. – Bill Dubuque Oct 12 at 0:18

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

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

• See here for another example using negative digits. – Bill Dubuque Oct 29 '18 at 23:10

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

• Great, where can I read about the tricks you mention for $2,3,5,11$? (you don't mention $9$...?) – learner Aug 23 '15 at 4:29
• @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$. – Alex M. Aug 28 '15 at 10:59