# 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?

-
The approach through Fermat's Theorem is absolutely standard, and with some practice will be usually faster than the perfectly reasonable approach you took. With $2$ minutes per question, for most problems one is forced into the rote line of attack. – André Nicolas Jul 6 '11 at 15:23
If you notice that $7^2 = 49 \equiv -3$ mod 13 then the work done for 3 can be used again in the case of 7 (with attention to signs). – Mark Bennet Jul 6 '11 at 15:31
The title of this question has lead to a misfiled bug report‌​. Perhaps it could be changed slightly? – Nathan Osman Jul 6 '11 at 16:38
@Deb: For the $n^{th}$ time: Please, try to use better titles. With almost all questions you post, someone has to come and clean up. – Aryabhata Jul 6 '11 at 18:27

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$.

-
As noted by another answer, one does not really have to invoke Euler and the easier Fermat's Little Theorem should be sufficient. – johnny Jul 6 '11 at 15:23
For any $a$?,ain't the $a$ and $13$ should be co-prime? – Quixotic Jul 6 '11 at 15:24
One more possible speed up is that 7^5 = - 6^5 mod 13, so $x = 3^5( 1- 2^5) = 3^2(-31) = (-4)(-5) = 20 mod 13$. – Willie Wong Jul 6 '11 at 15:27
@Debanjan: yes, they have to be coprime. I was hoping nobody had noticed before I corrected it. If $a$ is not coprime, then $a^{12} \equiv 0 \mod 13$. – johnny Jul 6 '11 at 15:31

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.

-
+1 for both using the balanced residue system, and the term $\mu$Fermat. – Willie Wong Jul 6 '11 at 17:22
@Willie Alas, whenever I can't fit "little Fermat" into my marginal notes, I resort to the micro-contraction $\mu$ Fermat. For more on Fermat contractions, see the thriller Fermat's Room (La habitación de Fermat) b.k.a "Honey, I shrunk the mathematicians". – Bill Dubuque Jul 6 '11 at 17:44

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.

-

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.

-
For the unse of the in-mind multiplicationtable :-) I like it to have bases for the powers as reduced as possible. Here I did $7^k=2^{-k}(2*7)^k=2^{-k}$ (mod 13). Then it was $3^2+2^7=3^2+2^6 \cdot 2^1=9-2$ (mod 13) .(But this was outside the situation of an exam, so I don't know, whether I would have found it in reality) – Gottfried Helms Jul 10 '11 at 8:20