Need to require a assertion for two subsets of natural numbers

Question

Let $P\ne Q$ be an arbitrary pair of primes, $M=PQ$.

$S$ = sum of all $m<M$ co-prime to $M$ such that equation $Px+Qy=m\ (1)$ has a solutions in natural numbers.

$s$ = sum of all $m<M$ co-prime to $M$ such that this equation is not solvable.

Is the assertion $S-s=\dfrac{(P^2-1)(Q^2-1)}{6}$ right?

Answer 1

Consider the set $$T = \{ (x,y)\ :\ 1\leq x\leq Q,\ 1\leq y\leq P,\ Px+Qy\leq PQ\}.$$ It is easy to see that $$S = \sum_{(x,y)\in T} (Px+Qy).$$

Switching to double summation in $S$, we get $$S = \sum_{y=1}^{P} \sum_{x=1}^{X_y} (Px+Qy) = \sum_{y=1}^{P} QyX_y + P\frac{X_y(X_y+1)}2,$$ where $$X_y = \left\lfloor \frac{PQ-Qy}P\right\rfloor = Q + \frac{-Qy - Z_y}P$$ and $$Z_y = -Qy\bmod P.$$ Hence, $$S=\sum_{y=1}^{P} \left(\frac{PQ^2+PQ}2 - \frac{Q}{2}y - (Q+\frac{1}{2})Z_y + \frac{1}{2P}Z_y^2 - \frac{Q^2}{2P}y^2\right).$$ Since $(P,Q)=1$, $Z_y$ runs over $\{0,1,\dots,P-1\}$ when $y$ runs over $\{1,2,\dots,P\}$. Therefore, $$S = \frac{P^2Q^2+P^2Q}2-\frac{QP(P+1)}{2}-(Q+\frac{1}{2})\frac{P(P-1)}2+\frac{(P-1)P(2P-1)}{12P}-\frac{Q^2P(P+1)(2P+1)}{12P}$$ $$=\frac{(P-1)(Q-1)(4PQ+P+Q+1)}{12}.$$

---

Now, the sum of all $m<PQ$ coprime to $PQ$ equals $$S+s=\frac{PQ(PQ-1)}2 - P\frac{Q(Q-1)}2 - Q\frac{P(P-1)}2=\frac{PQ(P-1)(Q-1)}2,$$ implying that $$s = \frac{PQ(P-1)(Q-1)}2 - S = \frac{(P-1)(Q-1)(2PQ-P-Q-1)}{12}.$$ Finally, $$S-s = \frac{(P-1)(Q-1)(4PQ+P+Q+1)}{12} - \frac{(P-1)(Q-1)(2PQ-P-Q-1)}{12}$$ $$=\frac{(P^2-1)(Q^2-1)}6$$ as expected.

Answer 2

T C Brown and Peter Jau-shyong Shiue, A remark related to the Frobenius problem, Fibonacci Quart. 31 (1993) 32-36, MR 93k:11018 gives you what you need.

"For given $a,b$ with $(a, b) = 1$, let $NR(a, b)$ denote the set of numbers nonrepresentable in terms of $a,b$. Thus, $NR(a, b)$ is the set of all those nonnegative integers $n$ which cannot be expressed in the form $n = ax + by$, where $x,y$ are nonnegative integers. Let $$S(a,b) = \sum\{\,n : n \in NR(a,b)\,\}$$ equal the sum of the numbers nonrepresentable in terms of $a$ and $b$.... In this note we find that, in fact, $$S(a,b)={1\over12}(a-1)(b-1)(2ab-a-b-1)"$$

Note that there is no need here for $a,b$ to be prime numbers; relative primality is all that is required.

Now, you'll have to do some fiddling to get exactly what you want. You want natural numbers, while the paper is about nonnegative numbers. But if $x=0$ (resp., $y=0$), then $n$ is a multiple of $b$ (resp., $a$), and it's easy to calculate the contribution of those values to the sum.

Also, you want the difference between the representables and the nonrepresentables. But of course the sum of the representables and the nonrepresentables is just all the sum of all the integers from $1$ to your $M$, which is easy, even after you account for the ones not relatively prime to $M$, and having the sum and one of the terms you can work out the difference easily enough.

The paper is available online and is quite easy to read.

A follow-up paper, Oystein J Rodseth, A note on T. C. Brown & P. J.-S. Shiue's paper: "A remark related to the Frobenius problem", Fibonacci Quart. 32 (1994) 407-408, MR 95j:11022, evaluates the sum of the $m$th powers of the nonrepresentables for all nonnegative integers $m$.

Answer 3

Gerry Myerson, Max Alekseyev, thank you! Sum of the representables $S'=\dfrac{(P+1)(Q+1)(4M-P-Q+1)}{12};S=\dfrac{(P-1)(Q-1)(4M+P+Q+1)}{12}.$ Curious. $P\rightarrow -P,Q\rightarrow -Q.$ I need time to read everything. The problem has grown from another problem on the number of solutions $N$ of the system $\begin{cases} X+Y+Z+T = M \\ XY\equiv ZT \mod M \end{cases}$ also in natural numbers for odd $M=PQ:$ $\ N=\dfrac{S-s}{4}-\dfrac{(P-1)(Q-1)}{4}=\dfrac{(M-2)^2-(P+Q-3)^2}{24}$. For other compound numbers the question is open, for a prime $M$ the system is undecidable: $(X-Y)^2\equiv (Z-T)^2\mod M$.

$S-s=\dfrac{(P^2-1)(Q^2-1)}{6}=\dfrac{\varphi (M)\sigma (M)}{6}.$ Is it possible to generalize, or is it an accident? Do not rush.