チラ裏メモ＾ｐ＾

問題「a^(a*n)≡1 (mod n) となるようなa,nの条件は何か？」

必要条件はaとnが互いに素であることだと（実験的に）わかっています。
aとnの最大公約数をmとすると、a^(a*n) mod n は、(mの倍数)mod(mの倍数)なのでmの倍数になります。
これが1になるってことは m=1しかありませんが、これでは必要条件のみを示したにすぎません。
例えばa=3,n=5は互いに素だけど1にならないのね。
一般にa^n≡a (mod n)っていうのが成り立つので、それを使ってa^a≡1 (mod n) にはなるね。
ただ単に十分条件っていうなら、a=n*(0以上の整数)+1なんかを提示してみるわけですが、
それが成り立つのはnが素数の時だけだと思う。（フェルマーの小定理。それを拡張したものは一般には成り立たない）

で、答えを書くと、条件は「aとnが互いに素であり、かつa^k≡1(mod n)を満たす最小のkに対してa*nがkで割り切れること」

必要条件の証明：
aとnが互いに素になることは証明済み。従ってオイラーの定理より a^φ(n)≡1 (mod n) となる。
これよりa^x≡1(mod n)なる整数xが存在することが言えるから、そのうちで最小のものをkとする。
kの定義よりk≦φ(n)となる。φ(n)＜nよりφ(n)＜a*n、よってk＜a*nとなる。
a^k≡a^(a*n)≡1(mod n)と併せて考えると、a*nはkで割り切れる。

十分条件の証明：
a^k≡1(mod n)であり、a*nはkの倍数であることから、a^(a*n)≡1(mod n)

ただ、このようなkが存在するかどうかに依存するから、実際使うためにはkを割り出さないといけなくて、
それは全数チェックになるのかな？ a^k≡1となる最小のkを求める定理があれば良さそうだねぇ。
kはφ(n)の約数でもあるので、φ(n)とa*nの最大公約数を求めてからその値の約数を調べていけば
全数探索よりはよさそうな気がしますが、じゃあφ(n)は楽に求まるかと言えばそうでもない感じですよね。
結局、因数分解の困難性に帰着するってことでしょうか。

＾ｐ＾