剰余の世界：mod n の時計が一周する
底 a と法 n を変えながら a^k mod n を 0…n−1 の円環（時計）上に打ち、跳ね回りながら現れる周期を体感します。
時計の文字盤は 12 で一周します。12 時の 5 時間後は 5 時、これが
法を
17 mod 12 = 5 の剰余演算です。法を
n にすると、数直線は 0,1,…,n−1 の n 個の点だけの円環に折りたたまれます。
ある底 a を掛け続けた a^k mod n はこの円環上を跳ね回り、やがて同じ場所に戻って周期を作ります。a と n が互いに素なら、フェルマー小定理 a^(p−1) ≡ 1 (mod p)（n=p が素数のとき）のように、必ず 1 に戻る瞬間が来ます。
3
13
6
現在の値 a^k mod n
—
周期（乗法的位数）
—
gcd(a, n)
—
n は素数？
—
mod n の時計（緑＝1 に戻った瞬間）
a^k mod n の推移（横＝k、縦＝余り）
べき乗の列 a^k mod n（赤＝1、緑＝1周して戻った位置）
いま何が起きている？
ここがポイント
- 剰余は円環 ── mod n の世界は数直線でなく 0…n−1 の n 個だけの時計。超えると一周して戻る。
- 周期（位数）が必ず現れる ── gcd(a,n)=1 なら a^k mod n は有限個しか取れず、いつか 1 に戻って同じ列を繰り返す。
- フェルマー小定理 ── n=p が素数で a が p の倍数でないとき
a^(p−1) ≡ 1 (mod p)。周期は必ず p−1 の約数になる。 - gcd≠1 だと 1 に戻れない ── a と n が公約数を持つと、列は 1 を二度と通らず別のサイクルに落ち込む。暗号で鍵やメッセージに互いに素な関係（あるいは素数）を意識するのは、この「戻れる／戻れない」を制御するためでもある。