Задача 78037

Темы:    [ Простые числа и их свойства ] [ Арифметическая прогрессия ] [ Деление с остатком ] [ Принцип Дирихле (прочее) ]

Сложность: 4 Классы: 8,9,10

Условие

p простых чисел a₁, a₂, ..., a_p образуют возрастающую арифметическую прогрессию и  a₁ > p.
Доказать, что если p – простое число, то разность прогрессии делится на p.

Решение

Рассмотрим остатки от деления чисел a₁, ..., a_p на p. Эти числа простые и все они строго больше p, поэтому ни одно из них не делится на p. Таким образом, мы получили p различных остатков, отличных от p. Следовательно, если два числа a_i и a_j, дающие одинаковые остатки при делении на p. Поэтому их разность делится на p. Но  a_i – a_j = (i – j)d,  где d – разность прогрессии. Число  |i – j|  строго меньше p, поэтому на p должно делиться число d.

Источники и прецеденты использования

олимпиада
Название	Московская математическая олимпиада
год
Номер	18
Год	1955
вариант
Класс	9
Тур	1
задача
Номер	4