1
$\begingroup$

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.

2 Answers 2

3

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.

  • 0
    Got it! Thanks a lot both of you.2012-04-29
4

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

  • 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.2012-04-29
  • 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.2012-04-29
  • 0
    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.2012-04-29
  • 0
    Yes, brute force can be traded for sharper tools (at the cost of accessibility.) The reader will benefit from seeing both approaches.2012-04-29
  • 0
    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.2012-04-29
  • 0
    I can identify with what you said. But, I'm making no assumptions about this person's familiarity with quadratic reciprocity, and so they might need some company with the trees for awhile. Hardy lumberjacks such as yourself are welcome at the same time.2012-04-29
  • 0
    Note that I don't use quadratic reciprocity either. I use nothing but little Fermat. My remark simply says that this innate structure becomes clearer *when* one studies the group stucture of squares and quadratic reciprocity. None of that is explicitly used in my answer. The point of such remarks is that they plant germs of ideas in students minds, ideas that they hopefully recall later when they study said advanced topics, so helping them better to comprehened the abstractions by recalling such concrete manifestations.2012-04-29
  • 0
    Most textbooks and lectures are very weak at explicitly pointing out relations between abstractions and prior-known concrete manifestations. It is essential that students learn how to efficiently navigate such abstract-concrete hierarchies. I often emphasize examples of such, because it can help to greatly aid students in the process of learning how to comprehend abstractions. Perhaps I emphasize it too much at times, often pointing out generalizations, and, conversely, various interesting specializations. But better too much than too little - better to be overwhelmed by beauty than blind.2012-04-29