последовательность и китайская теорема об остатках

[ShMaxG]

Помогите пожалуйста справиться с задачей:

Доказать, что для любой конечной последовательности

\[x_1 ,...,x_n \]

натуральных чисел найдутся такие два натуральных числа

\[a, b\]

, что при любом

\[ 1 \leqslant k \leqslant n \]

выполнено сравнение

\[x_k \equiv a(\bmod (bk + 1))\]

. (Указание: воспользуйтесь китайской теоремой об остатках.)

[bot]

ShMaxG писал(а):

Указание: воспользуйтесь китайской теоремой об остатках

Этого могли и не говорить - она сама просится. Что в ней говорится о модулях?
А что теперь на роль b просится?

Ой, не слишком ли много я уже сказал?

[ShMaxG]

Так, понятно, кажется понял. Спасибо.

P.S. задумался о великом множестве эквивалентных формулировок Китайской теоремы об остатках...

[Профессор Снэйп]

В Ленге теорема формулируется так:

Пусть $A$ --- ассоциативное коммутативное кольцо с единицей и идеалы $\mathfrak{a}_1,\ldots, \mathfrak{a}_n$ таковы, что $\mathfrak{a}_i + \mathfrak{a}_j = A$ при всех $i \neq j$. Тогда для любого семейства элементов $x_1,\ldots,x_n$ кольца $A$ существует такой элемент $x \in A$, что $x-x_i \in \mathfrak{a}_i$ при всех $i$ от $1$ до $n$.

На мой взгляд, это наиболее общая формулировка китайской теоремы об остатках.

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

Кстати, факт, который требуется доказать в этой задаче, существенно используется при доказательстве теоремы Гёделя о неполноте.

[TOTAL]

ShMaxG писал(а):

Так, понятно, кажется понял. Спасибо.

Пожалуйста, расскажите решение.

[Trotil]

Попробовал решить эту задачу на досуге.

Сначала я подумал, что $b=n$, но быстро нашел свою ошибку.

Теперь предполагаю, что $b=n!$.

Очевидное утверждение: если простое число $p|(kn!+1)$, то $p>n$.

С другой стороны, если $p$ простой общий делитель каких-то двух чисел из множества модулей сравнения $(k_2n!+1)$ и $(k_1n!+1)$, то он должен делить их разность: $p|(k_2-k_1)*n!)$, отсюда следует, что $p \leqslant n$.
Противоречие.

Отсюда числа $n!+1$, $2n!+1$,..., $n*n!+1$ - взаимо простые.

Условия для Китайской теоремы об остатках выполнены и таким образом, существует $a$, при котором будет верны сравнения из условия.

Верное ли решение?

[Профессор Снэйп]

Trotil писал(а):

Верное ли решение?

Да, верное.

[TOTAL]

Trotil писал(а):

Отсюда числа $n!+1$, $2n!+1$,..., $n*n!+1$ - взаимо простые.

Условия для Китайской теоремы об остатках выполнены и таким образом, существует $a$, при котором будет верны сравнения из условия.

Верное ли решение?

Взаимно простые числа я и сам могу придумать. Что дальше делать?

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

Прошу прощения, вопрос снимаю.
Мне почему-то во всех постах читалось, что речь идет о какой-то второй китайской теореме.

[bot]

Trotil писал(а):

Теперь предполагаю, что $b=n!$.

Угу, сначала напросилось это, а следом $n?$ - произведение всех простых, не превосходящих $n.$

[TOTAL]

bot писал(а):

Trotil писал(а):

Теперь предполагаю, что $b=n!$.

Угу, сначала напросилось это, а следом $n?$ - произведение всех простых, не превосходящих $n.$

1. Зачем экономить?
2. Если экономить, то зачем в произведение включать само (простое) $n$?

[bot]

1. Зачем? Да просто так - даром далось.
2. Согласен - можно взять $b=(n-1)?$