Remainder division What is the remainder when $35^{245}$ is divided by $41$?
I know this is a basic question to ask but I seems to forgot the method, tried to search for it online but to no avail.
I think it is related to number theory, hope someone can point me in the right direction.
 A: An elementary approach:
$$35=-6\pmod {41}\;,\;\;245=-1\pmod{41}\implies $$
$$35^{245}=\left((-6)^6\right)^{41}\cdot(-6)^{-1}$$
Using now Fermat's Little Theorem and $\,6^{-1}=7\pmod{41}\;$ and doing arithmetic modulo $\,41\;$ all along:
$$35^{245}=(-6)^6\cdot(-7)=(-6)^5=\left((-6)^2\right)^2(-6)=5^2(-6)=(-16)(-6)=\ldots$$
Spoiler

 The result is $\;14\;$

A: Hint:$$\gcd(a,n)=1\to a^{\phi (n)}\equiv1 \mod n$$ 

$$\gcd(35,41)=1\to 35^{\phi (41)}=35^{40}\equiv1 \mod  41 \to 35^{240}\equiv 1 \mod 41$$ 
$$35\equiv-6 \mod  41 \to35^2\equiv-5 \mod  41\to35^5\equiv25\cdot 6\equiv -16\cdot -6\equiv14 \mod41$$ 
now we have $35^{245}\equiv14 \mod41$

A: You can use Fermat’s little theorem, which says that if $p$ is prime, then $a^p\equiv a\pmod p$, and if $p\nmid a$, then $a^{p-1}\equiv 1\pmod p$. $41$ is prime and not a divisor of $35$, and $245=5\cdot41+40$, so modulo $41$ we have 

 $$35^{245}\equiv\left(35^{41}\right)^5\cdot35^{40}\equiv35^5\cdot1\equiv(-6)^5\equiv$ $36^2(-6)\equiv(-5)^2(-6)\equiv-150\equiv14\;.$$

(Mouseover to see the spoiler.)
