第2問

n

と

k

を、

k < n

を満たす互いに素な正の整数とする。集合

M = \{1, 2, \ldots, n-1\}

の各数を青か白のどちらかで塗り、次を満たすとする：(i) 各

i \in M

について、

i

と

n-i

は同じ色である；(ii)

i \ne k

を満たす各

i \in M

について、

i

と

|i-k|

は同じ色である。

M

のすべての数が同じ色であることを証明せよ。

ステップ 1/5:

k

の倍数が

M

を並べ替える

前のステップ次のステップ

ざっくり言うと

$n$ を法として $k$ を掛けることは、 $1,\dots,n-1$ を新しい順序で並べ替えているだけである—— $k$ と $n$ に公約数がないおかげで、カードを一枚も失わず重複もさせずにシャッフルするようなものだ。

\{k,2k,\dots,(n-1)k\} \equiv \{1,2,\dots,n-1\} \pmod n

詳しい解説

$\gcd(n,k)=1$ より、 $k$ を掛ける操作は $n$ を法とする剰余類の上での全単射である。 $ik\bmod n$ を $\{1,\dots,n-1\}$ の中の代表元として $r_i$ と書く（ $0<i<n$ かつ $\gcd(k,n)=1$ より $ik\not\equiv0$ ）。 $i$ が $1,\dots,n-1$ を動くと、値 $r_i$ はある順序で $M$ のすべての元をちょうど一回ずつ巡る。