Взаимно простые составные числа, нужна помощь по ТЧ

[Xenia1996]

Доказать, что существует множество из 2011 натуральных чисел, со следующими свойствами:
1) Все элементы этого множества попарно взаимно просты.
2) Сумма элементов любого непустого подмножества этого множества является составным числом.


Возьмём 2011 попарно различных простых чисел, равных 1 по модулю $2011!$ и выпишем их квадраты. Мы получим множество, удовлетворяющее обоим учловиям.
Но тут одна проблемка - нужно доказать, что 2011 таких простых чисел существуют

Тогда я по-другому попробовала:
Возьмём числа $(2011!+1)^2, (2\cdot 2011!+1)^2, (3\cdot 2011!+1)^2, \dots (2011\cdot 2011!+1)^2$
Каждое из этих чисел, естественно, будет составным, а так как каждое равно 1 по модулю всех чисел от 2 до 2011, сумма любых нескольких тоже будет составной.
Вопрос лишь в том, будут ли эти числа попарно взаимно простыми.
Я думаю, что да. Для этого достаточно доказать, что числа $2011!+1, 2\cdot 2011!+1, 3\cdot 2011!+1, \dots 2011\cdot 2011!$ являются попарно взаимно простыми.
Разность между любыми двумя из них равна $k\cdot 2011!$, где $1\le k\le 2010$.
Значит, если у каких-либо двух есть общий простой делитель, он должен быть делителем числа $2011!$, но это невозможно.

У меня по-прежнему такое подозрение, что я что-то сделала не так.
Помогите, пожалуйста, разобраться.
Заранее благодарна!

[nnosipov]

Не вижу ошибки. О простых числах в арифметических прогрессиях: для прогрессии вида $mk+1$ при любом натуральном $m$ проходит рассуждение Евклида, однако нужно привлекать круговые полиномы. Но, с другой стороны, это самый простой частный случай теоремы Дирихле, его все-таки можно доказать элементарно.

[Xenia1996]

nnosipov в сообщении #440061 писал(а):

Не вижу ошибки. О простых числах в арифметических прогрессиях: для прогрессии вида $mk+1$ при любом натуральном $m$ проходит рассуждение Евклида, однако нужно привлекать круговые полиномы. Но, с другой стороны, это самый простой частный случай теоремы Дирихле, его все-таки можно доказать элементарно.

Спасибо!

Просветите, пожалуйста, насчёт теоремы Дирихле. В смысле, подскажите идею доказательства.

Пруфа я тута не нашла: http://en.wikipedia.org/wiki/Dirichlet' ... ogressions

-- Пт апр 29, 2011 20:05:52 --

Вообще, если кому интересно, задачу вот отсюда взяла (она там последняя):

http://www.imomath.com/othercomp/Ita/ItaTST96.pdf

[nnosipov]

Xenia1996 в сообщении #440063 писал(а):

nnosipov в сообщении #440061 писал(а):

Не вижу ошибки. О простых числах в арифметических прогрессиях: для прогрессии вида $mk+1$ при любом натуральном $m$ проходит рассуждение Евклида, однако нужно привлекать круговые полиномы. Но, с другой стороны, это самый простой частный случай теоремы Дирихле, его все-таки можно доказать элементарно.

Спасибо!

Просветите, пожалуйста, насчёт теоремы Дирихле. В смысле, подскажите идею доказательства.

Пруфа я тута не нашла: http://en.wikipedia.org/wiki/Dirichlet' ... ogressions

На примере прогрессии $4k+1$. Рассуждаем от противного. Пусть $P$ --- произведение всех простых такого вида. Рассмотрим число $N=4P^2+1$. Все его простые делители должны иметь вид $4k+1$ (поскольку ввиду малой теоремы Ферма ни одно простое вида $4k+3$ не может делить такое $N$ --- докажите сами). Ну вот и противоречие.
Для произвольного $m$ нужно придумать аналог числа $N$. Для этого и используют круговые многочлены (cyclotomic polynomials). Рекомендую их поизучать, это очень интересные вещи.

[Xenia1996]

А вот как доказать, что такого бесконечного множества не существует? В смысле, заменить в условии задачи 2011 на бесконечность.

[svv]

В этом случае нужно подкорректировать, верно?

Цитата:

2) Сумма элементов любого конечного непустого подмножества этого множества является составным числом.

[Xenia1996]

svv в сообщении #440076 писал(а):

В этом случае нужно подкорректировать, верно?

Цитата:

2) Сумма элементов любого конечного непустого подмножества этого множества является составным числом.

Само собой. Имела в виду, но забыла приписать

[nnosipov]

Xenia1996 в сообщении #440071 писал(а):

А вот как доказать, что такого бесконечного множества не существует? В смысле, заменить в условии задачи 2011 на бесконечность.

Возможно, это сложный вопрос. Мой небольшой опыт в решении подобных вопросов исчерпывается следующей задачей, когда-то решенной: доказать, что в любом бесконечном подмножестве натурального ряда найдутся два элемента, сумма которых имеет простой делитель, больший миллиона. Помню, эта задача далась мне с большим трудом.

[Xenia1996]

nnosipov в сообщении #440085 писал(а):

доказать, что в любом бесконечном подмножестве натурального ряда найдутся два элемента, сумма которых имеет простой делитель, больший миллиона. Помню, эта задача далась мне с большим трудом.

Это на ленинградке 2003 года было. Отборочный тур, 11 класс, задача 5.

[nnosipov]

Совершенно верно.

[Xenia1996]

nnosipov в сообщении #440091 писал(а):

Совершенно верно.

(Оффтоп)

Это Вам, получается, 25 лет?

[nnosipov]

Xenia1996 в сообщении #440093 писал(а):

(Оффтоп)

Это Вам, получается, 25 лет?

(Оффтоп)

Увы, нет. Просто решаю такие задачи, потому что готовлю школьников к олимпиадам.