Пусть p1,..., pn - различные простые числа. Пусть S - сумма всевозможных произведений четного количества различных простых из этого набора. Докажите, что S+1 делится на 2^(n-2).

задан 20 Окт '13 7:36

изменен 20 Окт '13 8:11

10|600 символов нужно символов осталось
3

Рассмотрим два произведения: $$\Pi_{+}=(1+p_1)(1+p_2)\ldots(1+p_n)$$ и $$\Pi_{-}=(1-p_1)(1-p_2)\ldots(1-p_n).$$ Каждое из них делится на $%2^{n-1}$%, так как все простые числа списка нечётны за исключением, может быть, одного.

Раскроем скобки в первом произведении: $%\Pi_{+}=1+(p_1+p_2+\cdots+p_n)+(p_1p_2+p_1p_3+\cdots+p_{n-1}p_n)+(p_1p_2p_3+\cdots)+\cdots$%, где сначала идёт $%1$%, потом сумма всех чисел, потом сумма попарных произведений различных чисел, и далее сумма произведений троек, четвёрок и т.п. Теперь поступим аналогично со вторым произведением, в результате чего получится $%\Pi_{-}=1-(p_1+p_2+\cdots+p_n)+(p_1p_2+p_1p_3+\cdots+p_{n-1}p_n)-(p_1p_2p_3+\cdots)+\cdots$%, где сначала идёт $%1$%, затем вычитается сумма, потом прибавляется сумма попарных произведений, вычитается сумма произведений троек, и так далее -- с чередующимися знаками. Если теперь два произведения сложить, то окажется, что $%\Pi_{+}+\Pi_{-}=2(1+(p_1p_2+p_1p_3+\cdots)+(p_1p_2p_3p_4+\cdots)+\cdots)$%, то сократятся все те суммы, в которых мы складывали произведения нечётного количества простых чисел из набора, а остальные слагаемые удвоятся. В итоге останется в точности $%2(1+S)$%. Это число делится на $%2^{n-1}$%, откуда $%S+1$% делится на $%2^{n-2}$%.

ссылка

отвечен 20 Окт '13 12:11

10|600 символов нужно символов осталось
Ваш ответ

Если вы не нашли ответ, задайте вопрос.

Здравствуйте

Математика - это совместно редактируемый форум вопросов и ответов для начинающих и опытных математиков, с особенным акцентом на компьютерные науки.

Присоединяйтесь!

отмечен:

×737

задан
20 Окт '13 7:36

показан
514 раз

обновлен
20 Окт '13 12:11

Отслеживать вопрос

по почте:

Зарегистрировавшись, вы сможете подписаться на любые обновления

по RSS:

Ответы

Ответы и Комментарии

Дизайн сайта/логотип © «Сеть Знаний». Контент распространяется под лицензией cc by-sa 3.0 с обязательным указанием авторства.
Рейтинг@Mail.ru