Hey so I'm trying to provide proof of the answer to :
9000008 ^ 625767 % 9
I've solved the answer, and I believe a valid way to prove this is via induction, however while I know the inductive proof should be true I cannot figure out a valid way to write this out. I've researched a bunch on this topic and they validate the theory I used, but do not provide a proper way to prove it. Any assistance would be greatly appreciated
We see that $9000008 \equiv (-1)$ modulo $9$, since $9000008 + 1 = 9000009 = 9 \cdot 1000001$. Therefore, we must compute $(-1)^{625767}$, which is $(-1)$ since $625767$ is odd. Finally, $-1 \equiv 8$ modulo 9. So the final answer is 8.