第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$ 的剩余类上是一个双射；记 $r_i$ 为 $ik\bmod n$ 在 $\{1,\dots,n-1\}$ 中的代表元（它非零，因为 $0<i<n$ 且 $\gcd(k,n)=1$ 蕴含 $ik\not\equiv0$ ）。当 $i$ 遍历 $1,\dots,n-1$ 时， $r_i$ 的值按某种顺序恰好遍历 $M$ 的所有元素各一次。