олимпиада - Степень двойки

Рассмотрим два произведения: $$\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}$%.