第1問

n, k \ge 2

を正の整数とし、

a_1, a_2, \dots, a_k

を集合

\{1, 2, \dots, n\}

に属する相異なる整数で、

i = 1, 2, \dots, k - 1

のすべてに対して

n

が

a_i(a_{i+1} - 1)

を割り切るとする。このとき

n

は

a_k(a_1 - 1)

を割り切らないことを証明せよ。

ステップ 1/5: 整除関係が輪になって閉じると仮定する

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

ざっくり言うと

相異なるという仮定と矛盾させるため、禁じられた整除関係も仮定することで、開いた関係の鎖を閉じた輪に変える。

a_i(a_{i+1}-1)\equiv 0 \pmod n \text{ for } i=1,\dots,k \text{ (indices mod } k\text{)}

詳しい解説

背理法として、 $n$ が $a_k(a_1-1)$ も割り切ると仮定する。与えられた $k-1$ 個の関係と合わせると、 $i=1,\dots,k$ のすべてで $a_i(a_{i+1}-1)\equiv 0\pmod n$ が成り立つ（添字は $k$ を法とし $a_{k+1}=a_1$ とする）。これにより $a_1,\dots,a_k$ が $n$ を法として互いに合同になることを示し、 $\{1,\dots,n\}$ の相異なる元であることと矛盾させる。