Order-restricted linear congruences (Q2280006)

Let \(n,k\ge 1\) be integers and let \(b\in\mathbb{Z}\). The author proves that the number \(M_n(k,b)\) of solutions of the linear congruence \(x_1 + \ldots + x_k \equiv b\pmod n\), where \(x_1 \ge \ldots \ge x_k\), is \[ M_n(k, b) = \frac1{n + k} \sum_{d\mid (n,k)} \binom{\frac{n+k}{d}}{\frac{k}{d}} c_d(b). \] Here \((n,k)\) denotes the greatest common divisor of \(n\) and \(k\), and \(c_d(b)\) is Ramanujan's sum. The proof is by using a result from the theory of partitions and properties of Ramanujan sums and of the discrete Fourier transform of arithmetic functions. This generalizes an earlier result by \textit{J. Riordan} [Proc. Am. Math. Soc. 13, 107--110 (1962; Zbl 0101.25106)], obtained in the special case \(k=n\) and \(b=0\).