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.
$\endgroup$ 06 Answers
$\begingroup$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.
$\endgroup$ 1 $\begingroup$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$.
$\endgroup$ 2 $\begingroup$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}
$\endgroup$ 1 $\begingroup$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.
$\endgroup$ 1 $\begingroup$29 × 2901 × 2017 $\equiv$ 12 × 11 × 11 (mod 17)
12 × 121 $\equiv$ (mod 17)
12 × 2 $\equiv$ (mod 17)
24 $\equiv$ 7 (mod 17)
$\endgroup$ 3 $\begingroup$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$$
$\endgroup$
