7の7乗の7乗の…。

『高校への数学』の裏の広告に載っていた問題が興味深かったので。

どこぞの塾の広告なのだけれど、問題は以下の通り。

A=7777777を13で割ったあまりを求めよ。

おそらくの答えを出したのですが、とりあえずそれはまた今度で。

---

では解答編。
結局エレガントな解答は見つからなかった…OTL

まず、以下は明らか

∀n、7n≡1 (mod 2) ―（１）

次のことを示す。

a≡b (mod 2) ⇒ 7a≡7b (mod 12) ―（２）

∵　71≡7 (mod 12)
　　72≡49 (mod 12)
　　　　≡1 (mod 12)
　である。
　今、
　　a≡b (mod 2)
　ならば、
　　a=2n+b (n∈Z)
　よって、
　　7a=72n+b
　　　　=(72)n7b
　　　　≡7b (mod 12)
　よって、示された。


次に、次のことを示す。

a≡b (mod 12) ⇒7a≡7b (mod 13) ―（３）

∵計算すると、
　　71≡7 (mod 13)
　　72≡10 (mod 13)
　　73≡5 (mod 13)
　　74≡9 (mod 13)
　　75≡11 (mod 13)
　　76≡12 (mod 13)
　　77≡6 (mod 13)
　　78≡3 (mod 13)
　　79≡8 (mod 13)
　　710≡4 (mod 13)
　　711≡2 (mod 13)
　　712≡1 (mod 13)
　となっている。
　今、
　　a≡b (mod 12)
　ならば、
　　a=12n+b (n∈Z)
　よって、
　　7a=712n+b
　　　　=(712)n7b
　　　　≡7b (mod 13)
　よって示された。


さて、（１）より、
　77777≡1 (mod 2)

（２）より、
　777777≡71 (mod 12)
　　　　　≡7 (mod 12)

（３）より、
　7777777≡77 (mod 13)
　　　　　　≡6 (mod 13)

したがって、Aを13で割ったあまりは6である。//

この議論をたどる限り、
　77・・・7≡6 (mod 13)
のようですねぇ。
だから、
　7A≡A (mod 13)
であることが証明できれば、エレガントに証明できそうなんですけれどねぇ。