Арифметические прогрессии

[RIP]

Вспомнилась изумительная задачка.
Докажите, что множество натуральных чисел $\mathbb{N}$ нельзя представить в виде объединения конечного числа арифметических прогрессий с попарно различными разностями, бОльшими 1.
Утверждение довольно очевидно (но неверно: см. ниже), а вот попробуйте доказать.

[Юстас]

Это на самом деле очевидно. Понятно, что достаточно рассматривать случай простой разности. Если такое представление возможно, то $\forall n\in\mathbb{N}\ n $ является решением одного из конечного множества сравнений $x\equiv a_i(mod\ p_i)$. Рассмотрев систему этих сравнений с заменой каждого $a_i\rightarrow a_i^{'},\ a_i\ne a_i^{'}$, убеждаемся в существовании числа, не лежащего в объединении множества значений прогрессий(по китайской теореме об остатках решение будет).

[RIP]

Юстас писал(а):

Понятно, что достаточно рассматривать случай простой разности.

А мне непонятно. Как Вы будете действовать с $\{2k\}$ и $\{4k+1\}$?
P.S. Это трудная задача.

[Юстас]

Да, я погорячился насчет простых расзностей.

[worm2]

Или я чего-то не понимаю, или одно из двух.

$\mathbb{N}$=$\{2k\} \cup \{3k\} \cup \{4k-3\} \cup \{6k+5\} \cup \{12k-5\}$ (везде k натуральное).

Добавлено спустя 1 минуту 35 секунд:

Может быть, имелось в виду "непересекающихся прогрессий"

[RIP]

Мдааа, ошибся

Добавлено спустя 1 минуту 17 секунд:

Для непересекающихся прогрессий док-во простое, но думал, что верно в такой формулировке.

Добавлено спустя 4 минуты 49 секунд:

Казалось, что читал где-то док-во именно в такой формулировке. Извините за дезынформацию.
То-то никак не получалось доказать

[maxal]

С этой задачей связано несколько открытых проблем (в том числе и с денежными призами от Эрдёша). См. раздел F13 в UPINT.