Calculating residues with congruence

Question

I have to calculate the resiude of $41^{65}$ dividing by $7$. I know that we can calculating the size $k$ of the cycle of the powers of $41^n$ with $n=1,2,\ldots$ then by clasificating the residues with the $k$ clases we only use $65\equiv r(\mod k)$ and then we finish. But... $41$ is a prime number an the power are too big with $n=3,4,...$ Are there some hint of result that simplifies this problem? Any helop would be appreciated.

Answer 1

By Fermat's Little Theorem, $$a^{p-1}\equiv1\pmod p$$ where $p$ is a prime and $p$ does not divide $a$, we may observe a cyclic pattern for the base 41 with respect to 7. To start, $$41^0\equiv1\pmod7$$ Multiplying by 41: $$41^1\equiv6\pmod7$$ Repeating $$41^2\equiv6\times41\pmod7\implies41^2\equiv1\pmod7$$ By this we see that for any exponent of 41, the remainder with respect to 7 is either 6 or 1, this should simplify your problem.