Processing math: 40%

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


Пусть a1,a2,,an — арифметическая прогрессия целых чисел такая, что ai делится на i для всех i=1,2,,n1 и an не делится на n. Докажите, что n — степень простого числа. ( Д. Елиусизов )
посмотреть в олимпиаде

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

пред. Правка 2   2
3 года 1 месяца назад #

Пусть 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 имеет только один простой делитель.