|
I have the following question:
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:
Doing this for the numbers separately, then multiplying the expressions will get you the solution very quickly. |
|||||
|
|
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$. |
|||||||||
|
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} |
|||||
|
|
29 × 2901 × 2017 $\equiv$ 12 × 11 × 11 (mod 17) 12 × 121 $\equiv$ (mod 17) 12 × 2 $\equiv$ (mod 17) 24 $\equiv$ 7 (mod 17) |
|||||||||||||
|
|
This can be done in $15$ seconds of purely mental modular arithmetic of small numbers. 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, which we mark by a comma. We prove $\ 3247\equiv 0\pmod{\!17}\,$ for practice. $\begin{align}{\rm mod}\ 17\!:\qquad &\,\ \color{#0a0}{32}\,47\\ \equiv\ &{\color{#0a0}{-2}},\color{#c00}47 \ \ \text{by }\ \ \ \ \ \,\color{#0a0}{32}\,\equiv\,\color{#0a0}{-2} \\ \equiv\ &\quad\ \ \color{#f84}{\bf 1}7\ \ \ \text{by }\ {\color{#0a0}{-2}},\color{#c00}4 \equiv\, \color{#0a0}{{-}2}(10)+\color{#c00}4\equiv -16\equiv \color{#f84}{\bf 1} \\[-.3em] \text{Let's do the number in the OP}\qquad\ \ \ \ \\[-.3em] &\,\ \color{#0a0}{29}\,01\\ \equiv\ & {\color{#0a0}{-5}},\color{#c00}01\,\ \text{ by }\quad\! \color{#0a0}{29\equiv -5} \\ \equiv\ &\quad\ \ \color{#f84}{\bf 1}1\ \ \text{ by }\ \color{#0a0}{{-}5},\color{#c00}0\equiv {\color{#0a0}{-5}(10)+\color{#c00}0}\equiv -50\equiv\color{#f84}{\bf 1}\\[-.2em] \text{Similarly $\,2017\equiv 11\equiv\,\color{#08f}{-6}\ $ hence}\phantom{MM}\\[-.2em] &\ 29\cdot 2901\cdot 2017\\ \equiv\ &(-5)(\color{#08f}{-6})(\color{#08f}{-6})\\ \equiv\ &(-5)\ \color{#08f} 2\\ \equiv\ &\ 7 \end{align}\qquad\qquad$ |
|||||||||||||
|
|
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$$ |
|||
|
|
