Question about congruence modulo n

Question

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?

Answer 1

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.

Answer 2

$10^3\equiv-1\pmod7$

Now $515=(2n+1)3+2$ where $2n+1=171$

$\implies10^{(2n+1)3+2}=(10^3)^{2n+1}\cdot10^2\equiv(-1)^{2n+1}\cdot2\equiv5$

---

$8^2\equiv-1\pmod5$ and $391=4\cdot197+3$

$\implies8^{2(2n+1)+1}=8(8^2)^{2n+1}\equiv3(-1)^{2n+1}\pmod5\equiv2$