Problem 1529

We need to prove that $N(S)$ is a multiple of $q$ for any subset $S$ of $\{1, 2, \dots, p-1\}$, where $p$ and $q$ are distinct primes. We will use induction on $n = |S|$.

1. Base Case:
- When $n = 1$, $S = \{a\}$ for some $a \in \{1, 2, \dots, p-1\}$.
- The equation $\sum_{i=1}^{q} x_i \equiv 0 \mod p$ has no solutions because $q$ is a prime and $q \cdot a \not\equiv 0 \mod p$ (since $p$ and $q$ are distinct primes).
- Therefore, $N(S) = 0$, which is trivially a multiple of $q$.

2. Inductive Step:
- Assume the claim holds for any subset $S$ with $|S| = n$. That is, $N(S)$ is a multiple of $q$.
- Consider a new subset $S'$ formed by adding a new element $a$ to $S$, so $|S'| = n + 1$.
- We need to show that $N(S')$ is also a multiple of $q$.

3. Counting Solutions:
- Let $k$ be the number of solutions to $\sum_{i=1}^{q} x_i \equiv 0 \mod p$ where at least one $x_i = a$.
- Then, $N(S') = N(S) + k$.

4. **Analyzing $k$:**
- Consider solutions where $a$ appears $l$ times in the sum $\sum_{i=1}^{q} x_i \equiv 0 \mod p$.
- The number of ways to choose $l$ positions out of $q$ for $a$ is $\binom{q}{l}$.
- The remaining $q - l$ positions must be filled with elements from $S$ such that their sum modulo $p$ is $-la \mod p$.
- For each $l$, the number of such solutions is $\binom{q}{l} \cdot M$, where $M$ is the number of solutions for the remaining positions.

5. **Divisibility by $q$:**
- For $l = 1, 2, \ldots, q-1$, $\binom{q}{l}$ is divisible by $q$ because $q$ is a prime.
- Therefore, the total number of solutions $k$ where at least one $x_i = a$ is divisible by $q$.

6. Conclusion:
- Since $k$ is divisible by $q$ and $N(S)$ is a multiple of $q$ by the induction hypothesis, $N(S') = N(S) + k$ is also a multiple of $q$.

Thus, by induction, $N(S)$ is a multiple of $q$ for any subset $S$ of $\{1, 2, \dots, p-1\}$.

$\blacksquare$