第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\}$ 中互不相同的元素矛盾。