円周上に N 個並べた点の上を M ステップで移動していく時に乗る点についての話
$ N 個の点を円周上に並べ、時計回りに $ 0 ~ $ N-1 と名付ける
最初 $ 0 にいて、 $ M, 2M, .. のように前の点 $ +M の点に移動していく
$ N-1 の次の点は $ 0 とする
全ての点を訪れるのはどんな場合か?
例: $ N = 12, M = 3 とすると、 0, 3, 6, 9, 12 しか訪れない。 $ N = 12, M = 5 とすると、 0, 5, 10, 3, 8, 1, 6, 11, 4, 9, 2, 7, 0.. と全ての点を経て 0 に戻ってくる。
この答えは $ N と $ M が互いに素であるケースというのは直感的にわかるのだけど、その証明を思いついては忘れるのでメモしておく。
「不定方程式$ ax+by=c が整数解を持つ⇔ $ c は $ gcd(a, b) の倍数」が知られている
全ての点を訪れる
⇔ 何度かのステップにより一つ次の点を訪れることができる
⇔ $ My \equiv 1 \pmod N なる $ y が存在する
⇔ $ Nx + My = 1 を満たす整数解が存在する
⇔ $ N と $ M が互いに素 $ \because上述の定理