A "fast" way to manually compute $3^{41}+7^{41} \pmod{13}$ The problem:

Find the remainder of $3^{41}+7^{41}$
  when divided by $13$.

My approach is by utilizing the cyclicity of remainders for examples $3^1,3^2,3^3,3^4,3^5 \text{ and }3^6$ when divided $13$ gives $3,9,1,3,\text{ and }9 $ respectively,so we can see that the cycle repeats after $3$ steps.Hence the remainder of $3^{41}$ when divided by $13$ will be same as $3^2$ i.e $9$
For $7$ the repetition will occur in $7^{13}$ which means the cycle is of step $12$, hence it will be same as $7^5$ which gives $11$.
So the final answer is remainder of $(11+9)$ divided by $7$ which is $7$.
But as you might noticed, the computation of step for $7$ is quite a bit tedious (we have to check till $7^{13}$).
But, considering the fact that this problem is been taken from a exam which requires solution within $2$ mints, I am quite sure that there might be an easier method for finding the answer but I can't think of any other easier method, so could anybody suggest me a tricky method?
 A: By $\mu$Fermat, $\rm\: mod\ 13:\: 3^{12}\!\equiv 7^{12}\!\equiv 1\:,\: $ so $\rm\ 3^{41}+(-6)^{41}\!\equiv\: 3^5-6^5\!\equiv\:  3\cdot 4^2-6\cdot 3^2\! \equiv\: \!-4-2$
REMARK $\ $The arithmetic is simpler due to use of the balanced residue system $\pm\{0,\!1,\!2,\cdots,6\}\:.$ Indeed, the above rote congruence arithmetic calculation can be completed in less than a minute.
A: Since we need to know only the remainder, it is convenient to work $\mod 13$. Hence, we have to find $x$ such that 
$3^{41} + 7^{41} \equiv x \mod 13$
Since 13 is prime, $\varphi(13) = 12$ (Euler's totient function). Hence, $a^{12} \equiv 1 \mod 13$ for any $a \in \mathbb{Z}$ that is coprime to $13$ by Euler's theorem. So the equation above is equivalent to
$3^{12}3^{12}3^{12}3^{5} + 7^{12}7^{12}7^{12}7^{5} \equiv x \mod 13 \quad \Longrightarrow \quad 3^{5} + 7^{5} \equiv x \mod 13$
Computing the rest is pretty fast when you're working $\mod 13$.
A: By Fermat's little theorem, the remainder of $3^{12}$ and $7^{12}$ when divided by $13$ is $1$, since $13$ is a prime number and it does not divide neither $3$ nor $7$. This does not assure that $12$ is the least number with this property, but a number with such a property must divide $12$. Thus, you could then check $6$ and $4$ and so on.
A: One could do a few things. Here is what struck at me.
First: Note that $3^3 = 27 \equiv 1 \mod {13}$. So then we note that $41 = 3(13) + 2$. So $3^41 \equiv 3^2$. This is essentially what you did, but it's less cumbersome within the mod operation. To do 7, we can be wittier. By Fermat's Little Theorem, $7^{12} \equiv 1 \mod 13$. Now we can do the same thing.
Fermat's Little Theorem and Euler's Theorem, combined with repeated squaring, makes short work of all this type of problem.
