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?

$\endgroup$
4
  • 2
    $\begingroup$ 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. $\endgroup$ Jul 6 '11 at 15:23
  • 2
    $\begingroup$ 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). $\endgroup$ Jul 6 '11 at 15:31
  • $\begingroup$ The title of this question has lead to a misfiled bug report. Perhaps it could be changed slightly? $\endgroup$ Jul 6 '11 at 16:38
  • $\begingroup$ @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. $\endgroup$
    – Aryabhata
    Jul 6 '11 at 18:27
6
$\begingroup$

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

$\endgroup$
4
  • $\begingroup$ As noted by another answer, one does not really have to invoke Euler and the easier Fermat's Little Theorem should be sufficient. $\endgroup$
    – johnny
    Jul 6 '11 at 15:23
  • 1
    $\begingroup$ For any $a$?,ain't the $a$ and $13$ should be co-prime? $\endgroup$
    – Quixotic
    Jul 6 '11 at 15:24
  • 2
    $\begingroup$ 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$. $\endgroup$ Jul 6 '11 at 15:27
  • $\begingroup$ @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$. $\endgroup$
    – johnny
    Jul 6 '11 at 15:31
7
$\begingroup$

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.

$\endgroup$
2
  • 3
    $\begingroup$ +1 for both using the balanced residue system, and the term $\mu$Fermat. $\endgroup$ Jul 6 '11 at 17:22
  • 2
    $\begingroup$ @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". $\endgroup$ Jul 6 '11 at 17:44
4
$\begingroup$

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.

$\endgroup$
2
$\begingroup$

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.

$\endgroup$
1
  • $\begingroup$ 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) $\endgroup$ Jul 10 '11 at 8:20

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.