MathLabs

第1题

设 n,k≥2n, k \ge 2 为正整数，a1,a2,…,aka_1, a_2, \dots, a_k 是集合 {1,2,…,n}\{1, 2, \dots, n\} 中互不相同的整数，使得对每个 i=1,2,…,k−1i = 1, 2, \dots, k - 1，nn 都整除 ai(ai+1−1)a_i(a_{i+1} - 1)。证明 nn 不整除 ak(a1−1)a_k(a_1 - 1)。
第 5/5 步：用中国剩余定理汇总得出矛盾
上一步下一步
通俗地说

对 n 的每个素数幂因子都同余，就意味着对 n 本身同余，但 aia_i 本是按模 n 互不相同的剩余选取的。

a1≡a2≡⋯≡ak(modn)a_1 \equiv a_2 \equiv \dots \equiv a_k \pmod n
详细分析

两种情形下，所有 aia_i 都模 qq 同余于同一个常数（00 或 11）。由于 q=peq=p^e 是恰好整除 nn 的任意素数幂，由中国剩余定理得 a1≡a2≡⋯≡ak(modn)a_1\equiv a_2\equiv\dots\equiv a_k\pmod n。但 a1,…,aka_1,\dots,a_k 是 nn 的完全剩余系 {1,…,n}\{1,\dots,n\} 中互不相同的元素，由于 k≥2k\ge2，它们不可能都模 nn 同余。这一矛盾说明假设不成立，故 nn 不整除 ak(a1−1)a_k(a_1-1)。■\blacksquare