Городская олимпиада по математике среди физ-мат школАлматы, 2010 год

Пусть $a_1, a_2, \dots, a_n$ — арифметическая прогрессия целых чисел такая, что $a_i$ делится на $i$ для всех $i=1, 2, \dots , n-1$ и $a_n$ не делится на $n$. Докажите, что $n$ — степень простого числа. ( Д. Елиусизов )

Комментарий/решение

Пусть $d$ разность данной арифметикой прогрессии. $a_{i}=a_{1}+(i-1)d \equiv a_{1}-d \pmod i$ при $i=1,2,...,n-1$. Значит $a_{1}-d$ делится на $1,2,...,n-1$. Пусть $n$ имеет хотя бы 2 простых делителя. Обозначим так: $n=p_{1}^{b_{1}}...p_{k}^{b_{k}}$ (это стандартное каноническое разложения). Так как $p_{j}^{b_{j}} \leq n-1$, значит $a_{1}-d$ делится на $p_{j}^{b_{j}}$. Аналогично, понимаем что $a_{1}-d$ делится на $p_{1}^{b_{1}}...p_{k}^{b_{k}}=n$. Противоречия. Значит $n$ имеет только один простой делитель.