Остатки от деления

[confabulez]

Пишу на форму впервые. Решаю задачи с сайта головоломок и встретилась такая задача:
"На окружности дано 300 точек. Мегамозг находится в произвольной точке. Двигаясь против часовой стрелки, он перемещается сначала на одно деление в соседнюю точку, затем перемещается на два деления, потом – на три, четыре и т.д. В скольких точках побывает Мегамозг? Ответ обосновать."

Мои соображения: занумеровать точки от 0 до 299. Мегамозг стартует из точки 0. Необходимо выяснить, какие остатки от деления на 300 будет иметь число $S=1+2+...+n=\frac{n(n+1)}{2}$ при всех натуральных $n$. Если все возможные значения от 0 до 299, то побывает во всех точках. Мне кажется, что так и будет, но вот почему? Есть ли какая-нибудь теорема?

[ИСН]

Есть; называется "теорема о лопате". Она гласит, что если человеку лень взять лопату в руки и копнуть пару раз, то хрен ему, а не картошка.

-- Ср, 2011-06-22, 13:29 --

Казалось бы, взять руками и проверить, нет? Если 300 - слишком много, проверьте для 10. Если этого много, проверьте для 3. Теоремам предшествуют гипотезы. Гипотезам - сбор данных.

[confabulez]

Спасибо за совет. Посмотрел для 3. Остаток не принимает значение 2, для 5 - не принимает значения 2,4. Для 10 - 2,4,7 и 9.

[confabulez]

Получилось, что он побывает всего в 88 точках. Остатки от деления на 300 начинают полностью повторяться начиная с $n=601$. Но проделал все это на компьютере. А ведь должно же быть красивое решение на бумажке, если понадобится для очень большого числа точек решить задачу. Подскажите, пожалуйста, идею общего решения.

[bot]

Здесь с другим вопросом.

[ИСН]

С бумажным решением сложно; впрочем, возможно, до мультипликативности удастся добраться, а там уже - - -
Общая формула (словесно) есть в OEIS: A117484