Nemotron-IMO-Bench 2026 C6

Let $p_1,\ldots, p_s$ be pairwise distinct primes and let $x_1,\ldots, x_n$ be integers, with $n\geq \max p_i$. Let $P_i=\frac{p_1\ldots p_s}{p_i}$ and let $P'_i$ be an integer such that $P_iP'_i\equiv 1\pmod {p_i}$. For $1\leq j\leq n$ let $M^{(j)}$ be the number of sums of $j$ numbers among $x_1,\ldots, x_n$ which are relatively prime to $p_1\ldots p_s$ and let $$M=M^{(1)}-M^{(2)}+\ldots+(-1)^{n-1}M^{(n)}.$$ For $1\leq i\leq s$ and $1\leq j\leq n$ let $N_i^{(j)}$ be the number of sums of $j$ numbers among $x_1,\ldots, x_n$ which are relatively prime to $p_i$, but not to $P_i$ and let $$N_i=N_i^{(1)}-N_i^{(2)}+\ldots+(-1)^{n-1}N_i^{(n)}.$$ Prove that $$p_1\ldots p_s\mid M+\sum_{i=1}^n P_i P_i'N_i.$$