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