Remainder with congruences I'm having some trouble understading how to use congruence to solve this type of exercises: > a) Determinate the remainder of the division of $2173451$ with $17$ > > b) Determinate the remainder of the division of $1522^{1000}$ with $19$ For example, in b) I know that $1522=80\times19+2$, so $1522 \equiv 2(mod19)$ , so $1522^{1000} \equiv 2^{1000}(mod19)$. What now?

(a) $$17 \times 1 = 17$$ $$17 \times 2 = 34$$ $$17 \times 3 = 51$$ $$17 \times 6 = 102$$ $$17 \times 6 - 2 = 100$$

Hence $$100 \equiv -2 \mod 17$$ \begin{align}2173451&= 2000000+170000+3400+51 \\\&\equiv2\times(10^2)^3+0+0+0 \mod 17\\\ &\equiv 2\times (-2)^3 \mod 17 \\\ &\equiv -16 \mod 17 \\\& \equiv 1 \mod 17\end{align}

(b) $$19 \times 5 = 95$$ $$19 \times 5 + 5 = 100 \equiv 5 \mod 19$$ $$1522 = 1500+22 \equiv (-4)\times 10^2+3 \equiv -20+3 \equiv -17 \equiv 2 \mod 19$$

Now, let's examine the exponent, $1000 \equiv 10 \times 100\equiv 10 \times (18 \times 5+10)\equiv 100 \equiv 10 \mod 18$

Hence, we want to compute $2^{10} \mod 19$

$$2^{10} \equiv 1024 \equiv 1000+24 \equiv 10(5)+5 \equiv 55 \equiv 57-2 \equiv -2 \equiv 17 \mod 19 $$