好像是一道简单的高中题目

hujunhua

易见对于k>=2，必存在i,1<=i<=k,s.t.(Ai*(Ai-1),n)<n

咋个易见呢？还是应该写出来，否则功亏一篑。

反证法：
假如$n|a_k(a_1-1)$,
记$(a_i, n)=p_i$,$ (a_i-1, n)=q_i$, 并规定$p_(i+k)=p_i$, $q_(i+k)=q_i$
一方面由$p_i$与$q_i$互质$->p_iq_i|n$, 得$n>=p_iq_i$, 连乘得$n^k>=\prod(p_iq_i)$, 取等号的条件是$n=p_iq_i$。
另一方面由题设加假设有 $n|p_iq_(i+1)$, 得$n<=p_iq_(i+1)$, 连乘得$n^k<=\prod(p_iq_i)$, 取等号的条件是$n=p_iq_(i+1)$。

所以必有$n^k=\prod(p_iq_i)$, 并致使前述取等号的条件俱真, 于是可得$p_i=q_i=\sqrt{n}$。（余略）

mathe

最后一步还不完善。取等号的条件是$p_1=p_2=...=p_k,q_1=q_2=...=q_n,p_1q_1=n$
这个时候我们我们需要借助中国剩余定理来得出矛盾。
我记得这个题目在百度数学吧里面给出过的

wiley

这是去年IMO的第一题.  分享一个证明:

由已知条件, 易得
$a_1\equiv a_1a_2\equiv\cdots\equiv a_1a_2\cdots a_k \ (mod \ n)$
同理,
$a_2\equiv a_2a_3\equiv\cdots\equiv a_2a_3\cdots a_k \ (mod \ n)$

反证, 如果 $n|a_k(a_1-1)$ , 那么
$a_1a_2\cdots a_k\equiv a_2a_3\cdots a_k \ (mod \ n)$
即 $a_1\equiv a_2 \ (mod \ n)$
但是已知 $0<|a_1-a_2|<n$ , 矛盾