Question about congruence modulo n Is there any sort of algorithm to calculate the remainder when $10^{515}$ is divided by $7$?
Could the same algorithm be applied to finding the remainder of $8^{391}$ divided by $5$?
Is it even necessary to use congruence here?

By Fermat's Little Theorem you know that
$$10^6\equiv 1 \mod 7$$
because $7$ is not a divisor of $10$. Now, since
$$10^{515}=10^{6\cdot 85+5}=(10^6)^{85}\cdot 10^5,$$
you get
$$
10^{515}\equiv
(10^6)^{85}\cdot 10^5\equiv
1^{85}\cdot 10^5\equiv
10^5\pmod 7.
$$
Finally, dividing $10^5=100000$ by $7$ the quotient is $14285$ and the remainder is $5$, so $5$ is the solution.
Same thing for $8^{391}\mod 5$: this time $8^4\equiv 1\mod 5$ because $5$ is not a divisor of $8$, then $8^{391}=8^{4\cdot 97+3}$ and so on.
