# Proof of equation in modular arithmetic

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

-

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.

-
Got it! Thanks a lot both of you. – Nick Apr 29 '12 at 16:17

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

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