Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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?

share|improve this question
2  
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
2  
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

4 Answers 4

up vote 6 down vote accepted

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

share|improve this answer
    
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
1  
For any $a$?,ain't the $a$ and $13$ should be co-prime? –  Quixotic Jul 6 '11 at 15:24
2  
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.

share|improve this answer
2  
+1 for both using the balanced residue system, and the term $\mu$Fermat. –  Willie Wong Jul 6 '11 at 17:22
1  
@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

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.

share|improve this answer
    
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

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.

share|improve this answer

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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