>>43-46 あっさりコンプですか。すごいですね！
（俺がそもそも数学科じゃないというのもあるが、丸一日かかって
　分からんかったやつを、いともあっさりと解きやがってっｗｗ）

一応、別解というか、用意してた>>42のテクニカルな証明はこんな感じ。
------------------------------
a＝1, n＝1 の時は自明なので a＞1, n＞1 とする。
n を素因数分解した時、素因子p が p|a かそうでないかで分けて、
前者をb, 後者をc とする。つまり、n＝bc, gcd(b,c)＝1, gcd(c,a)＝1
明らかに a^φ(c)≡1 (mod c) なので、
a^φ(bc)＝a^(φ(b)φ(c))＝(a^φ(c))^φ(b)≡1 (mod c)
故に c|a^φ(n)-1 …①
今、p を b の素因子とする。b を素因数分解した時の p の指数部を r、
a を素因数分解した時の p の指数部を s(≧1) すると、
r ≦ (p-1) p^(r-1) φ(n/p^r) ＝ p^rφ(n/p^r)-p^(r-1)φ(n/p^r)
　≦ p^r(n/p^r)-φ(p^r(n/p^r)) ＝ n-φ(n) ≦ s(n-φ(n))
故に、b|a^(n-φ(n))　…②
①,② より　bc|a^(n-φ(n))(a^φ(n)-1) つまり n|a^n-a^(n-φ(n))