# Fast Way of Finding The Remainder

I have the following question:

Find the remainder of $29\times 2901\times 2017$ divided by $17$

I already have the answer (7) for this problem. I solved it using the long way by multiplying all of the numbers then divvy them with 17. I am just thinking if there are any fast way of solving this. My solution takes a long time.

Hint:

If $$a\equiv b\pmod c$$ And $$d\equiv e\pmod c$$ You can multiply the two to get $$a\times d\equiv b\times e\pmod c$$

Doing this for the numbers separately, then multiplying the expressions will get you the solution very quickly.

• See here for this Congruence Product Rule. But here we can also exploit radix rep to mod out chunks of digits, which greatly simplifies the computation - see my answer. – Bill Dubuque Jan 29 '17 at 19:52

You can write each number as a multiple of $17$ plus a small remainder:

$$(17+12)(170\cdot 17+11)(118\cdot 17+11).$$

When you multiply this out (which you don't have to do) every term is a multiple of $17$ except the last one $12\cdot 11\cdot 11$. So you need consider only this last product. We can repeat what we just did with a little factoring. The above $= 3\cdot 11 \cdot 4 \cdot 11 = 33\cdot 44 = (17+16)(2\cdot 17 + 10).$ So you need consider only $16\cdot 10$.

• $(-5)\cdot(-6)\cdot(-6)$ is easier to compute. – tomasz Jan 29 '17 at 18:09
• @tomasz Yes, but from the question, I don't think the OP knows about modular arithmetic yet, so dealing with a negative remainder is an extra complication. Although I see a "mod" answer was accepted as best, so maybe I'm wrong. – B. Goddard Jan 29 '17 at 18:23

Find remainder after dividing $29 \times 2901 \times 2017$ by $17$.

Work $\mod 17$ !

\begin{align} & 29 \times 2901 \times 2017 \\ & 12 \times 1201 \times 317 \\ & 12 \times 1201 \times 147 \\ & 12 \times 351 \times 62 \\ & 12 \times 11 \times 11 \\ & 1452 \\ & 602 \\ & 92 \\ & 7. \end{align}

• This is much easier if one works with least magnitude reps (i.e. allow negative remainders), e.g. see my answer. – Bill Dubuque Jan 29 '17 at 19:54

This can be done in $$15$$ seconds of purely mental modular arithmetic of small numbers using the universal divisibility test, which is essentially the division algorithm ignoring quotients. To obtain optimal speedup we use least magnitude remainders, e.g. $$-1$$ vs. $$16\pmod{\!17}$$ since doing so simplifies subsequent arithmetic. To reduce a decimal number mod $$n$$ we continually mod out the leading chunks of its digits. Since we allow negative remainders, we will encounter negative digits, delimited by a comma, e.g. $$\,a,b := a(10)\!+\!b.\,$$ We prove $$\ 3247\equiv 0\pmod{\!17}\,$$ for practice.

\begin{align}{\rm mod}\ 17\!:\qquad &\,\ \color{#90f}{32}\ 47\\ \equiv\ &{\color{#90f}{-2}},\color{#0a0}47 \ \ \ \text{by }\ \ \ \ \ \,\color{#90f}{32}\,\equiv\,\color{#90f}{-2} \\ \equiv\ &\quad\ \ \, \color{#f84}{\bf 1}7\ \ \ \text{by }\ {\color{#90f}{-2}},\color{#0a0}4 \equiv\, \color{#90f}{{-}2}(10)\!+\!\color{#0a0}4\equiv -16\equiv \color{#f84}{\bf 1} \\[-.3em] \text{Let's do the number in the OP}\qquad\ \ \ \ \\[-.3em] &\,\ \color{#90f}{29}\ 01\\ \equiv\ & {\color{#90f}{-5}},\color{#0a0}01\ \ \text{ by }\quad \color{#90f}{29\,\equiv\, -5} \\ \equiv\ &\quad\ \ \color{#f84}{\bf 1}1\ \ \, \text{ by }\ \color{#90f}{{-}5},\color{#0a0}0\equiv {\color{#90f}{-5}(10)\!+\!\color{#0a0}0}\equiv -50\equiv\color{#f84}{\bf 1}\\ \equiv\ &\quad \,\color{#08f}{-6}\\[-.2em] \text{Similarly \,2017\equiv\color{#c00}{-6}\ so we have}\phantom{MM}\\[-.2em] &\ 29\cdot 2901\cdot 2017\\ \equiv\ &(-5)(\color{#08f}{-6})(\color{#c00}{-6})\\ \equiv\ &(-5)\ \color{#08f} 2\\ \equiv\ &\ 7 \end{align}\qquad\qquad

where we have applied the Congruence Product and Sum Rules many times above.

Remark  I wrote every little detail above to help avoid confusion with negative digits. Once one gains proficiency there is no need to be so extremely verbose. See here for a larger example which also employs negative digits for optimization.

• (+1) The OP did say "fast way" of finding the remainder, this is it! – Silverfish Jan 29 '17 at 23:42

29 × 2901 × 2017 $\equiv$ 12 × 11 × 11 (mod 17)

12 × 121 $\equiv$ (mod 17)

12 × 2 $\equiv$ (mod 17)

24 $\equiv$ 7 (mod 17)

• Even faster if you use negative modulos to keep the numbers small, so in this case, the first line would be $(-5)*(-6)*(-6)$ – WorldSEnder Jan 29 '17 at 17:49
• Ok I keep in mind that. – Kanwaljit Singh Jan 29 '17 at 17:53
• @KanwaljitSingh: $(-a) \equiv (b - a) (\mathrm{mod}\, b)$ – Kevin Jan 29 '17 at 19:31

The numbers are given in decimal representation, therefore I would start by simplifying $100 \bmod 17$. We have that $20\equiv 3$, therefore $100=20\times 5\equiv 3\times 5 = 15\equiv -2$. This allows us to write:

$$2900\equiv -2\times 29\equiv -2\times (-5) = 10$$

And

$$2000\equiv -2\times 20\equiv-2\times 3 = -6$$

We thus have:

$$29\times 2901\times 2017\equiv -5\times 11\times (-6) = 30\times 11\equiv -4\times 11\equiv -4\times (-6) = 24\equiv 7$$