# 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. Jan 29, 2017 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. Jan 29, 2017 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. Jan 29, 2017 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. Jan 29, 2017 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! Jan 29, 2017 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)$ Jan 29, 2017 at 17:49
• Ok I keep in mind that. Jan 29, 2017 at 17:53
• @KanwaljitSingh: $(-a) \equiv (b - a) (\mathrm{mod}\, b)$ Jan 29, 2017 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$$