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.

Can anybody prove that the following equation is true?

$$7^n + 9^n \equiv 0 \pmod {11}\quad\text{where}\quad n\equiv 5 \pmod{10}$$

Thanks in advance.

share|improve this question
add comment

2 Answers

up vote 3 down vote accepted

Hint $\rm\: mod\ 11\!:\ 9^{\!\:5+10j}\!+7^{\:\!5+10k}\! \equiv (3^2)^{5+10j}\! + (-2^2)^{5+10k}\!\equiv (3^{10})^{1+2j}\!+(-2^{10})^{1+2k}\!\equiv 1 - 1 $

Remark $\ $ Thus it is just a special case of the fact that for a prime $\rm\:p = 4\:k+3$

$$\rm mod\ p\!:\ (a^2)^{2k+1}+(-b^2)^{2k+1}\equiv\: a^{p-1} - b^{p-1}\equiv 1 - 1\ \ \ for\ \ a,b\not\equiv 0$$

The innate structure will become clearer when you learn about the group structure of squares and quadratic reciprocity.

share|improve this answer
    
Got it! Thanks a lot both of you. –  Nick Apr 29 '12 at 16:17
add comment

Hint: Express $n$ as $n=10m+5$, then show $7^{10}\equiv 9^{10}\equiv 1$ mod 11.

share|improve this answer
1  
That's the easy part. But you give no hint why $7^5 + 9^5\equiv 0\pmod{11}.\:$ For that, see my answer. –  Bill Dubuque Apr 29 '12 at 15:36
1  
Strange, both steps are equally easy. I think it would be rather unlikely for one who proves the given hint to get stuck on the part you mention. This hint is easily reapplied to general problems of the same type: eliminating $m$ is the hard part, then reducing the constant residue is easy. –  rschwieb Apr 29 '12 at 15:41
    
My point is that one doesn't need to do the remaining part by brute force calculation if one exploits the innate "square" structure - see the remark I just added to my answer. For larger moduli the remaining part is still trivial using the square structure, but is very difficult by brute force. Btw, welcome to MSE. Glad to see you here. –  Bill Dubuque Apr 29 '12 at 16:03
    
Yes, brute force can be traded for sharper tools (at the cost of accessibility.) The reader will benefit from seeing both approaches. –  rschwieb Apr 29 '12 at 16:19
    
That may be true in general, but not here, because no sharper tools are need. To me, the remaining part is the most interesting part of the problem. It's likely that the problem was designed to help students discover some of this beautiful structure. That's why I thought it worth saying something about the remaining part. If one says nothing, as above, students usually resort to brute force calculations, so missing the forest for the trees. –  Bill Dubuque Apr 29 '12 at 16:35
show 3 more comments

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.