设 $n$ 是一个正整数，$a_{1},a_{2},\ldots,a_{k}$ 是集合 $\{1,\ldots,n\}$ 中的互不相同的整数，使得对于 $i=1,\ldots,k-1$，都有 $n$ 整除 $a_{i}(a_{i+1}-1)$．证明：$n$ 不整除 $a_{k}(a_{1}-1)$．（澳大利亚）
【难度】
【出处】
2009年第50届IMO试题
【标注】
【答案】
略
【解析】
我们先用归纳法证明对任意的整数 $2\leqslant i\leqslant k$，都有 $n|a_1(a_i-1)$．
当 $i=2$ 时，由已知得 $n|a_1(a_2-1)$，结论成立．
假设已有 $n|a_1(a_i-1)$，其中 $2\leqslant i\leqslant k-1$，则 $n|a_1(a_i-1)(a_{i+1}-1)$．
又由已知得 $n|a_i(a_{i+1}-1)$，故 $n|a_1a_i(a_{i+1}-1)$．因此 $n|(a_1a_i(a_{i+1}-1)-a_1(a_i-1)(a_{i+1}-1))$，即 $n|a_1(a_{i+1}-1)$，由归纳法知上面结论对所有的整数 $2\leqslant i\leqslant k$ 成立．特别地，我们有 $n|a_1(a_k-1)$．
由于 $a_1(a_k-1)-a_k(a_1-1)=a_k-a_1$ 不能被 $n$ 整除（这里用到 $a_1$ 和 $a_k$ 是集合 $\{1,\cdots,n\}$ 中的两个不同整数），故 $n$ 不整除 $a_k(a_1-1)$．证毕．
当 $i=2$ 时，由已知得 $n|a_1(a_2-1)$，结论成立．
假设已有 $n|a_1(a_i-1)$，其中 $2\leqslant i\leqslant k-1$，则 $n|a_1(a_i-1)(a_{i+1}-1)$．
又由已知得 $n|a_i(a_{i+1}-1)$，故 $n|a_1a_i(a_{i+1}-1)$．因此 $n|(a_1a_i(a_{i+1}-1)-a_1(a_i-1)(a_{i+1}-1))$，即 $n|a_1(a_{i+1}-1)$，由归纳法知上面结论对所有的整数 $2\leqslant i\leqslant k$ 成立．特别地，我们有 $n|a_1(a_k-1)$．
由于 $a_1(a_k-1)-a_k(a_1-1)=a_k-a_1$ 不能被 $n$ 整除（这里用到 $a_1$ 和 $a_k$ 是集合 $\{1,\cdots,n\}$ 中的两个不同整数），故 $n$ 不整除 $a_k(a_1-1)$．证毕．
答案
解析
备注
