2014 dxdy logo

Научный форум dxdy

Математика, Физика, Computer Science, Machine Learning, LaTeX, Механика и Техника, Химия,
Биология и Медицина, Экономика и Финансовая Математика, Гуманитарные науки




 
 последовательность и китайская теорема об остатках
Сообщение06.05.2008, 12:36 
Аватара пользователя
Помогите пожалуйста справиться с задачей:

Доказать, что для любой конечной последовательности\[x_1 ,...,x_n \] натуральных чисел найдутся такие два натуральных числа \[a, b\], что при любом \[
1 \leqslant k \leqslant n
\]
выполнено сравнение \[x_k  \equiv a(\bmod (bk + 1))\]. (Указание: воспользуйтесь китайской теоремой об остатках.)

 
 
 
 
Сообщение06.05.2008, 13:24 
Аватара пользователя
ShMaxG писал(а):
Указание: воспользуйтесь китайской теоремой об остатках

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

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

 
 
 
 
Сообщение06.05.2008, 17:16 
Аватара пользователя
Так, понятно, кажется понял. Спасибо.

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

 
 
 
 
Сообщение06.05.2008, 20:38 
Аватара пользователя
В Ленге теорема формулируется так:

Пусть $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 секунду:

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

 
 
 
 
Сообщение07.05.2008, 06:16 
Аватара пользователя
ShMaxG писал(а):
Так, понятно, кажется понял. Спасибо.
Пожалуйста, расскажите решение.

 
 
 
 
Сообщение07.05.2008, 17:09 
Аватара пользователя
Попробовал решить эту задачу на досуге.

Сначала я подумал, что $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$, при котором будет верны сравнения из условия.

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

 
 
 
 
Сообщение07.05.2008, 17:32 
Аватара пользователя
Trotil писал(а):
Верное ли решение?


Да, верное.

 
 
 
 
Сообщение08.05.2008, 06:31 
Аватара пользователя
Trotil писал(а):
Отсюда числа $n!+1$, $2n!+1$,..., $n*n!+1$ - взаимо простые.

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

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

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

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

 
 
 
 
Сообщение08.05.2008, 16:24 
Аватара пользователя
Trotil писал(а):
Теперь предполагаю, что $b=n!$.

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

 
 
 
 
Сообщение08.05.2008, 16:47 
Аватара пользователя
bot писал(а):
Trotil писал(а):
Теперь предполагаю, что $b=n!$.

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

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

 
 
 
 
Сообщение08.05.2008, 17:32 
Аватара пользователя
1. Зачем? Да просто так - даром далось.
2. Согласен - можно взять $b=(n-1)?$

 
 
 [ Сообщений: 11 ] 


Powered by phpBB © 2000, 2002, 2005, 2007 phpBB Group