7
$\begingroup$

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?

  • 0
    @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.2011-07-06

4 Answers 4

2

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.

  • 0
    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)2011-07-10
7

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.

  • 2
    @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)](http://www.imdb.com/title/tt1016301/) b.k.a "Honey, I shrunk the mathematicians".2011-07-06
6

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

  • 0
    @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$.2011-07-06
4

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.