given a very large base and power (strings) calc the (base^power)%M where M is a prime number

Question

link to a previous question on stack overflow https://stackoverflow.com/questions/45458628/calculating-a-pow-b-mod-m-for-very-large-a-and-b-stored-in-string link to the problem https://www.hackerearth.com/practice/math/number-theory/basic-number-theory-1/practice-problems/algorithm/sheero-and-the-party/ i don't understand this part of the answer $$\text{power%(M-1)}$$ the question is answered by the following solution we need to take the number and mod it by using it's digits we will do for every digit $$base=(base*10+digit)%M$$ same goes for the power but we will use $$power=(power*10+digit)%(M-1)$$ why we used M-1 for the power? M is a prime number and i know Fermat's little theorem but still can't understand the reason

Answer 1

You're asked to compute $X^Y\pmod{M}$, say, with $M$ prime. You know that $X^{M-1}\equiv 1\pmod{M}$ by FLT, since it is given that $M\not\mid X$. Hence, if $Y=(M-1)Q+R$ is the division of $Y$ by $M-1$ with the remainder $R$, then $X^Y=X^{(M-1)Q+R}=(X^{M-1})^Q X^R\equiv X^R\pmod{M}$. Is it what you didn't see?