Теория чисел на Межведе

Вычислим

То есть нужно найти остаток по модулю Рассмотрим первое слагаемое.

Раскрывая скобки, как минимум два раза выберется из скобок, что дает в сравнении по модулю Это верно, кроме случаев, когда были выбраны все единицы или когда было выбрано одно из всех скобок. Тогда, используя бином Ньютона, получаем, что первое слагаемое сравнимо с

Аналогично получаем, что второе слагаемое сравнимо с

Тогда получаем

Следовательно, остаток равен