Given coprime positive integers $p,q>1$, call all positive integers that cannot be written as $px+qy$(where $x,y$ are non-negative integers) bad, and define $S(p,q)$ to be the sum of all bad numbers raised to the power of $2019$. Prove that there exists a positive integer $n$, such that for any $p,q$ as described, $(p-1)(q-1)$ divides $nS(p,q)$.
Problem
Source: China TST 2019 Test 2 Day 2 Q6
Tags: number theory, China TST
K_Mirrorheart
12.03.2019 09:51
Does anyone have a solution of this? I only proved that both $p-1$ and $q-1$ divide $2020!S(p,q)$ during the test, which was not enough. And I would be greatly disappointed if I don't know how to do this before the second phase of TST.
lbh_qys
12.03.2019 13:49
$S(p,q)=\sum_{i=0}^{pq-p-q}i^{2019}-\sum_{i=0}^{q-2}\sum_{j=0}^{p-2} [ip+jq\le pq-p-q](ip+jq)^{2019}$,obviously $(p-1)(q-1)|2\sum_{i=0}^{pq-p-q}i^{2019}$. Let generating function $T_{p,q}(x)=\sum_{i=0}^{q-2}\sum_{j=0}^{p-2} [ip+jq\le pq-p-q]e^{(ip+jq)x}$，only need $c[x^{2019}]T_{p,q}(x)\equiv 0 \pmod{(p-1)(q-1)}$. $T_{p,q}(x)=\sum_{i=0}^{q-2}e^{ipx} \frac{e^{(\lfloor p-1-\frac{(i+1)p}{q}\rfloor +1)qx}-1}{e^{qx}-1}=\sum_{i=0}^{q-2}e^{ipx} \frac{e^{(p-1-\lfloor \frac{(i+1)p}{q}\rfloor )qx}-1}{e^{qx}-1}=\frac{1}{e^{qx}-1} (e^{(pq-p-q)x}\sum_{i=0}^{q-2}e^{((i+1)p-\lfloor \frac{(i+1)p}{q}\rfloor q)x}-\sum_{i=0}^{q-2}e^{ipx})$ $(i+1)p-\lfloor \frac{(i+1)p}{q}\rfloor q=(i+1)p\bmod q$ traverses in $\{1,2,\cdots,q-1\}$ when $i$ traverses in $\{0,1,\cdots,q-2\}$,so $T_{p,q}(x)=\frac{1}{e^{qx}-1} (e^{(pq-p-q+1)x}\sum_{i=0}^{q-2}e^{ix}-\sum_{i=0}^{q-2}e^{ipx})=\frac{1}{e^{qx}-1} (e^{(pq-p-q+1)x}\frac{e^{(q-1)x}-1}{e^x-1}-\frac{e^{p(q-1)x}-1}{e^{px}-1})=\frac{e^{pqx}+e^{(p-1)(q-1)x}-e^{((p-1)(q-1)+p)x}-e^{((p-1)(q-1)+q)x}+e^x-1}{(e^{px}-1)(e^{qx}-1)(e^x-1)}$ Constant term of $\frac{e^{px}-1}{px}$ is $1$,so the coefficient of $\frac{px}{e^{px}-1}$ is the rational coefficient polynomial of $p$. The coefficient of $pqx^3T_{p,q}(x)$ is rational coefficient polynomial of $p,q$. The coefficient of $x^i$ of $e^{pqx}+e^{(p-1)(q-1)x}-e^{((p-1)(q-1)+p)x}-e^{((p-1)(q-1)+q)x}+e^x-1$ is $\frac{(pq)^i+((p-1)(q-1))^i-((p-1)(q-1)+p)^i-((p-1)(q-1)+q)^i+1-0^i}{i!}$.It is equal to $0$ when $p=0,p=1,q=0,q=1$.So it has factor $pq(p-1)(q-1)$. So the coefficient of $pqx^3T_{p,q}(x)$ has factor $pq(p-1)(q-1)$,$T_{p,q}(x)$ has factor $(p-1)(q-1)$. This implies $\exists c=c(2019)$ s.t. $(p-1)(q-1)|c[x^{2019}]T_{p,q}(x)$.
61plus
16.03.2019 10:23
I hope the following works. Every time we choose the constant here, it is always independent of $p,q$. The main motivation comes from the proof of the following lemma: Lemma 1: For fixed $n$ non-negative integer, there exist a rational polynomial $R_n(x)$ such that for any $k$, $$[1^n+2^n+\ldots+(k-1)^n]=(k-1)R_n(k-1).$$
Proof: This is done by strong induction. The conclusion is clearly true for $n=0$.
Suppose $n\leq m-1$ is true and we want to show for $n=m$. Consider the following:
\begin{align*}
(k-1)^{m+1}=&\text{ }1^{m+1}+2^{m+1}+\ldots+(k-1)^{m+1}\\
&\text{ }-(1-1)^{m+1}-(2-1)^{m+1}-\ldots-((k-1)-1)^{m+1}\\
=&\text{ }(m+1)(1^m+2^m+\ldots+(k-1)^m)+(k-1)Q(k-1), Q\in \mathbb{Q}[x].
\end{align*}which shows that $n=m$ must be true as well.
The first step is to characterize all the bad numbers. Claim 1: Bad numbers are of the form $px+qy$.
WLOG $q>p$. For readability, we introduce the function $B(r,s)=rp-sq$. Then it is not hard to show that all the bad numbers are as follow:
\begin{align*}
B\Big(\lceil\frac{q}{p}\rceil, 1\Big), & & B\Big(\lceil\frac{q}{p}\rceil+1,1\Big), & & \ldots, & & B\Big(q-1,1\Big)\\
B\Big(\lceil\frac{2q}{p}\rceil, 2\Big), & & B\Big(\lceil\frac{2q}{p}\rceil+1, 2\Big), & & \ldots, & & B\Big(q-1,2\Big)\\
& & & & \ldots\\
B\Big(\lceil\frac{(p-1)q}{p}\rceil, (p-1)\Big), & & B\Big(\lceil\frac{(p-1)q}{p}\rceil+1, (p-1)\Big), & & \ldots,& & B\Big(q-1,(p-1)\Big)
\end{align*}where each $(x,y)$ corresponds to the number $px+qy$.
So for $p=5, q=7$, the bad numbers written in these form look like:
\begin{align*}
3, 8, 13, 18, 23 \\
1, 6, 11, 16\\
4, 9\\
2
\end{align*}
Let $P(n)$ be the proposition that if $S_n$ is the sum of bad integers raised to the power $n$ , there exists a positive integer $m$, such that for any $p,q$ as described, $(p-1)(q-1)$ divides $mS_n$. Claim 2: $P(n)$ is true for all even $n$.
Note that the sum of the following numbers raised to the $n$th power is equals to $2S_n$:
\begin{align*}
B\Big(1, 1\Big), & & B\Big(2, 1\Big), & & \ldots, & & B\Big(q-1,1\Big)\\
B\Big(1,2\Big), & & B \Big(2, 2\Big), & & \ldots, & & B\Big(q-1, 2\Big)\\
& & & & \ldots \\
B\Big(1, (p-1)\Big), & & B\Big(2, (p-1)\Big), & & \ldots,& & B\Big(q-1, (p-1)\Big)
\end{align*}
So for $p=5, q=7$, the array will look like:
\begin{align*}
-2,& & 3, & & 8, & & 13, & & 18, & & 23 \\
-9,& & -4, & & 1, & & 6, & & 11, & & 16\\
-16,& & -11, & & -6, & & -1, & & 4, & & 9\\
-23,& & -18, & & -13, & & -8, & & -3, & & 2
\end{align*}
So we just need to show that $(p-1)(q-1)$ divides the sum of these numbers raised to the $n$ times a constant. This sum is given by
\begin{align*}
&\text{ }B(1,1)^n+B(2,1)^n+\ldots+B(q-1,1)^n \\
+&\text{ }B(1,2)^n+B(2,2)^n+\ldots+B(q-1,2)^n \\
+&\text{ }\ldots\\
+&\text{ }B(1,p-1)^n+B(2,p-1)^n+\ldots+B(q-1,p-1)^n\\
=&\text{ }\sum_{i=1}^{n} c_i (1^i+2^i+\ldots+(p-1)^i)(1^{n-i}+2^{n-i}+\ldots+(q-1)^{n-i})p^iq^{n-i}
\end{align*}Since for each component $x$ of this sum there exist a constant $c$ such that $cx$ is divisible by $(p-1)(q-1)$ using Lemma 1, the sum must be too, implying $P(n)$ is true for $n$ even.
Claim 3: $P(n)$ is true for all odd $n$.
This is done by induction. We observe that if $A$ is the set of all bad numbers , let $L$, $R$ be the set of the leftmost, rightmost bad numbers in the array written at the start. Then if we subtract $p$ to all of elements in $A$, we obtained $A$ including elements from $L$ minus $p$, and excluding elements in $R$. Furthermore, $L$ is $\lbrace1, 2, \ldots, p-1\rbrace$. $R$ is $\lbrace q-p, 2q-p,\ldots, (p-1)q-p\rbrace$. This is motivated from the proof of Lemma 1 and will allow us to induct downwards from even $n$.
We can prove $P(1)$ quite easily with this:
Click to reveal hidden text\begin{align*}
\sum_{a\in A} a^2 &= \sum_{a\in A} (a-p)^2 - \sum_{l \in L} (l-p)^2 + \sum_{r \in R} r^2\\
&= \sum_{a\in A} a^2 - 2p\cdot\sum_{a\in A} a+(p-1)(q-1)\cdot p^2- \sum_{l \in L} l^2 + \sum_{r \in R} r^2
\end{align*}So
\begin{align*}
2p\cdot\sum_{a\in A} a &= (p-1)(q-1)\cdot p^2- \sum_{l \in L} l^2 + \sum_{r \in R} r^2\\
&= (p-1)(q-1)\cdot p^2 - \frac{1}{6}(p-1)p(2p-1) \\
&\phantom{=}+ (p-1)\cdot p^2 - pq\cdot (p-1)p + q^2\cdot \frac{1}{6}(p-1)p(2p-1)\\
&= (p-1)(q-1)p\Big(p + \frac{1}{6}(2p-1)(q+1) - p\Big)
\end{align*}and thus $P(1)$ is true.
Now comes the painful part. We want to show for $P(2k-1)$, and will employ almost the same strategy for $P(1)$ on $P(2k-1)$, by binomial expansion of $(a-p)^{2k}$.
Suppose it is true for any lower $P(n)$. The sum we have in $P(1)$ now looks like this
\begin{align*}
\sum_{a\in A} a^{2k} &= \sum_{a\in A} (a-p)^{2k} - \sum_{l \in L} (l-p)^{2k} + \sum_{r \in R} r^{2k}\\
&= \sum_{a\in A} a^{2k} - 2p\cdot\sum_{a\in A} a^{2k-1}+(p-1)(q-1)\cdot c'- \sum_{l \in L} l^{2k} + \sum_{r \in R} r^{2k}
\end{align*}where $c'$ is some rational number whose denominator is finite from induction. Thus we actually only need to show that there exist a positive rational constant $c$ such that
\[ p(p-1)(q-1)\Big|c\cdot\Big( \sum_{r \in R} r^{2k}- \sum_{l \in L} l^{2k}\Big)=c\cdot T \]This is easy to show for $p,p-1,q-1$ separately, but we are in trouble if $p-1,q-1$ shares a lot of factors, or if $p|q-1$. We will proceed with a different strategy, by first finding $\sum_{r \in R} r^{2k}- \sum_{l \in L} l^{2k} \pmod{(q-1)^2}$. (Note: There ought to be a better way to do it than this)
Evaluation mod (q-1)^2Note that the sum can be rewritten as
\begin{align*}
&\text{ }\Big((q-1)-(p-1)\Big)^{2k}+\Big(2(q-1)-(p-2)\Big)^{2k}+\ldots+\Big((p-1)(q-1)-1\Big)^{2k}\\
&\text{ }-1^{2k}-2^{2k}-\ldots-(p-1)^{2k}\\
\equiv &\text{ }-2k(q-1)\Big((p-1)^{2k-1}\cdot 1+(p-2)^{2k-1}\cdot 2+\ldots +1^{2k-1}\cdot (p-1)\Big) \pmod{(q-1)^2}
\end{align*}It is not difficult to show that a constant times $(p-1)^{2k-1}\cdot 1+(p-2)^{2k-1}\cdot 2+\ldots +1^{2k-1}\cdot (p-1)$ is divisible by $(p-1)p$ with help from Lemma 1. Hence, there exist a rational constant $c_2$, such that $\gcd{\Big(q-1, p(p-1)\Big)}\Big|c_2\cdot \frac{T}{q-1}$.
Now we find $\sum_{r \in R} r^{2k}- \sum_{l \in L} l^{2k}$ mod $(p-1)^2$.
Evaluation mod (p-1)^2We can rewrite the sum as
\begin{align*}
&\text{ }\Big(q-1-(p-1)\Big)^{2k}+\Big(2q-1-(p-1)\Big)^{2k}+\ldots+\Big((p-1)q-1-(p-1)\Big)^{2k}\\
&\text{ }-(1-1)^{2k}-(2-1)^{2k}-\ldots-(p-1-1)^{2k}\\
\equiv &\text{ }\sum_{i=1}^{2k} (iq-1)^{2k} -2k(p-1)\sum_{i=1}^{p-1}(iq-1)^{2k-1}\\
\equiv &\text{ }\sum_{i=1}^{2k} (-1)^{i}{2k\choose i}\sum_{j=1}^{p-1} (j^iq^i - j^i) -2k(p-1)\sum_{i=1}^{p-1}(iq-1)^{2k-1}\\
\equiv &\text{ }\sum_{i=1}^{2k} (-1)^{i}{2k\choose i}(q^i-1)\sum_{j=1}^{p-1} j^i -2k(p-1)\sum_{i=1}^{p-1}(iq-1)^{2k-1}\pmod{(p-1)^2}
\end{align*}Again from Lemma 1, there exist a fixed constant $e$ such that for $i\leq 2k$, $p-1|e\cdot \sum_{j=1}^{p-1} j^i$. Furthermore, $q-1|q^i-1$. For the second part of the expression, let $\gcd(p-1,q-1)=d$, then
\begin{align*}
&\sum_{i=1}^{p-1}(iq-1)^{2k-1}\\
\equiv &\sum_{i=1}^{p-1}(i-1)^{2k-1}\\
\equiv &\sum_{i=1}^{p-1}i^{2k-1}\\
\equiv &(p-1)\cdot R_{2k-1} \pmod{d}
\end{align*}and note that $d|p-1$. So we have for some fixed rational $c_1$ , $\gcd{(p-1, q-1)}\Big|c_1\cdot \frac{T}{p-1}$.
It remains to show that $$\gcd{\Big(q-1, p(p-1)\Big)}\Big|c_2\cdot \frac{T}{q-1},$$$$\gcd{(p-1, q-1)}\Big|c_1\cdot \frac{T}{p-1}$$implies the desired result. Consider a prime $r$ (We exclude $r=p$ first). Then let $v_r(p-1)=a, v_r(q-1)=b$. We have that $$v_p(c_1c_2\cdot T)\geq \max{(a,b)}+\min{(a,b)}=a+b=v_r\Big(p(p-1)(q-1)\Big).$$If $r=p$, let $v_p(q-1)=b$. Then $p|c_2\cdot \frac{T}{q-1}$ so $$v_p(c_2\cdot T) \geq 1+b = v_p\Big(p(p-1)(q-1)\Big).$$Thus there exist a positive rational constant $c=c_1c_2$ independent of $p,q$ such that
\[ p(p-1)(q-1)\Big|c\cdot\Big( \sum_{r \in R} r^{2k}- \sum_{l \in L} l^{2k}\Big)=c\cdot T \]$P(2k-1)$ is proven. By induction it is true for all $n$
Thus the result must be true for $P(2019)$ as well.
CANBANKAN
19.03.2021 07:33
Very hard NT! Let $e=2019$, and we solve the problem for any $e$. Claim 1: Bad numbers are of the form $px-qy: x>0, y<0$ Proof: Suppose a number $\equiv pk(\bmod\; q)$, where $0\le k<q$. If it is at least $pk,$ it is clearly good, and if it's not, $y$ is negative, or I have to decrease $k$ by $q$ to make $x$ negative. Claim 2: The claim holds for $e=1$. Proof. $\sum\limits_{x=1}^{q-1} \sum\limits_{y=1}^{\lfloor \frac{px}{q} \rfloor} (px-qy) = p\sum\limits_{x=1}^{q-1} x\lfloor \frac{px}{q} \rfloor - \frac q2 \sum\limits_{x=1}^{q-1} (\lfloor \frac{px}{q} \rfloor^2 + \lfloor \frac{px}{q} \rfloor )$ Note $ \frac q2\sum\limits_{x=1}^{q-1} \lfloor \frac{px}{q} \rfloor = \frac 12 \sum\limits_{x=1}^{q-1} (px - R(px,q)) = \frac{(p-1)q(q-1)}{4}$ $\frac q2\sum\limits_{x=1}^{q-1} \lfloor \frac{px}{q} \rfloor ^2 = \frac q2\sum\limits_{x=1}^{q-1} (\frac{px}{q} - \{ \frac{px}{q}\})^2 = \frac q2\sum\limits_{x=1}^{q-1} (\frac{p^2x^2}{q^2} - 2\frac{px}{q}\{ \frac{px}{q}\} + \{ \frac{px}{q}\}^2)=\frac{p^2}{2q} \frac{(q-1)q(2q-1)}{6}-p\sum\limits_{x=1}^{q-1} x\{ \frac{px}{q} \} + \frac{1}{2q} \cdot \frac{(q-1)q(2q-1)}{6}=\frac{(p^2+1)(q-1)(2q-1)}{12} -p\sum\limits_{x=1}^{q-1} x\{\frac{px}{q}\}$ Also, $p\sum\limits_{x=1}^{q-1} x\{\frac{px}{q}\} + p\sum\limits_{x=1}^{q-1} x\lfloor \frac{px}{q} \rfloor = p\sum\limits_{x=1}^{q-1} \frac{px^2}{q} = \frac{p^2}{q} \cdot \frac{(q-1)q(2q-1)}{6} = \frac{p^2(q-1)(2q-1)}{6}$. Therefore, the sum is $\frac{p^2(q-1)(2q-1)}{6} - \frac{(p-1)q(q-1)}{4} - \frac{(p^2+1)(q-1)(2q-1)}{12} = \frac{(p^2-1)(q-1)(2q-1)}{12} - \frac{(p-1)q(q-1)}{4} = (p-1)(q-1) (\frac{(p+1)(2q-1)}{12}-\frac{q}{4})$, so $n=12$ indeed works. Notice a bad number can be represented as $px-qy$ but also as $q(p-y)+p(x-q)$ where $x,y>0$. Therefore, if $e$ is even, $2\sum\limits_{x \text{ bad}} x^e = \sum\limits_{x=1}^{q-1} \sum\limits_{y=1}^{p-1} (px-qy)^e=\sum\limits_{x=1}^{q-1} \sum\limits_{y=1}^{p-1} \sum\limits_{j=0}^e \binom ej (px)^j (qy)^{e-j} = \sum\limits_{j=0}^e \binom ej \sum\limits_{x=1}^{q-1} (px)^j \sum\limits_{y=1}^{p-1} (-qy)^{e-j}$. It's easy to see that $q-1\mid C\sum\limits_{x=1}^{q-1} x^j$ with polynomial or other summation techniques, so we are done with the $e$ even case. Now we are temporarily stuck because the $\sum\limits_{x=1}^{q-1} x^j \sum\limits_{y=1}^{\lfloor \frac{px}{q} \rfloor} y^k$ term is hard to work with. Well, first of all, the $\sum\limits_{y=1}^k y^e$ is hard to work with when $k=\lfloor \frac{px}{q} \rfloor$. We have nothing to lose if we induct on $e$. Induction allows us to use shift $x^j$ to $\prod\limits_{m=x-j+1}^x m$ Okay. With induction, we can make this a "binomial coefficient" to get $$\sum\limits_{x=1}^{q-1} x^j\binom{\lfloor \frac{px}{q} \rfloor +1 }{k+1}$$ I've gotten rid of the weird sum, but the $\lfloor \frac{px}{q} \rfloor$ is so cumbersome!! I need to get rid of it. Hmm. What about $x^j\rightarrow (x-k)^j$? It's clear that only few of the $k$'s are actually useful; indeed, we can just WLOG $p<q$ and use $k=p$. Let's draw a table for $p=5,q=7$. \begin{tabular}{c|c|c|c|c|c} \color{red} 2 & 7 & 12 & 17 & 22 & 27 \\\hline \color{red} 4 & \color{red} 9 & 14 & 19 & 24 & 29 \\\hline \color{red} 1 & \color{red} 6 & \color{red} 11 & \color{red} 16 & 21 & 26 \\\hline \color{red} 3 & \color{red} 8 & \color{red} 13 & \color{red} 18 & \color{red} 23 & 28 \end{tabular} (Here, red numbers indicate bad numbers) Call a sum fine if it times a constant is always divisible by $(p-1)(q-1)$. As mentioned, such a transformation maps $x^e$ to sums of $x^{e-1},\cdots, x$. It completely avoids the $\lfloor \frac{px}{q}\rfloor$ term. Since even exponents are easier to deal with, we make $e$ even, and note $\sum\limits_{x \text{ bad}} (x^e-(x-p)^e) = \sum\limits_{j=0}^{e-1} \binom ej (-p)^{e-j-1} \sum\limits_{x \text{ bad}} x^j$ By Inductive hypothesis, $e-2,\cdots,0$ are fine. So if this is fine, $p\sum\limits_{x \text{ bad}} x^{e-1}$ must be fine as well. This is so much easier to deal with than that floor sum. Let's compute the sum in two ways. First of all, note that $qx-p$'s are lost and $1,\cdots,p-1$ are gained, so $\sum\limits_{x \text{ bad}} (x^e-(x-p)^e) = \sum\limits_{x=1}^{p-1} (qx-p)^e - \sum\limits_{x=1}^{p-1} x^e = \sum\limits_{j=0}^{e-1} \binom ej (-p)^{e-j} q^j (\sum\limits_{x=1}^{p-1} x^j)$ We compute the sum mod $r^k$ for $r$ prime. We have two cases: Case 1: $r\nmid p, r\mid q-1$. One observation is that $p-1\mid C(\sum\limits_{x=1}^{p-1} x^j)$ for all $j<e-1$. Therefore, this is $\sum\limits_{j=0}^{e-1} \binom ej (-p)^{e-j} \sum\limits_{x=1}^{p-1} x^j=\sum\limits_{x=1}^{p-1} ( \sum\limits_{j=0}^{e-1} \binom ej (-p)^{e-j} x^j = \sum\limits_{x=1}^{p-1} (x-p)^e - x^e = 0$ since $e$ is even. Case 2: $r\mid p$, then note $p\mid C\sum\limits_{x=1}^{p-1} x^j$, so we can repeat the same argument.
squareman
25.08.2021 18:40
WLOG, $q > p.$ Consider a positive integer $b \equiv px \pmod{q},$ where $0 \le x \le q-1,$ then $b$ is bad if and only if $b < px.$ We characterize bad numbers as positive integers of the form $b = px - qy,$ where $x,y$ are positive integers and $q-1 \ge x.$ Replace $2019$ with $n.$ We prove the result for all positive integers $n.$ First the evens. Note $px - qy$ is the negative of $p(q-x) - q(p-y).$ Thus, if we let both $x$ and $y$ vary from $0$ to $q-1$ inclusive and $0$ and $p-1$ inclusive respectively, $px-qy$ will traverse every bad number and its negative exactly once, with no extra numbers. So $$2\sum\limits_{x \text{ bad}} x^n = \sum\limits_{x=1}^{q-1} \sum\limits_{y=1}^{p-1} (px-qy)^n = \sum\limits_{m=0}^n \binom nm \sum\limits_{x=1}^{q-1} (px)^m \sum\limits_{y=1}^{p-1} (-qy)^{n-m} = \sum\limits_{m=0}^n (p)^m (-q)^{n-m} \binom nm \left( \sum\limits_{x=1}^{q-1} x^m \sum\limits_{y=1}^{p-1} y^{n-m} \right).$$ It's not hard to see that $\sum\limits_{x=1}^{q-1} x^m$ and $\sum\limits_{y=1}^{p-1} y^{n-m}$ will be a multiple of $p-1$ and $q-1$ respectively when multiplied by constants independent of both. For odds, we prove with induction. First $n = 1.$ Let $S$ be the set of bad numbers. If we subtract $p$ from all the elements in $S,$ we get $S \cup \{-1,-2, \dots -p+1 \} \setminus \{ q-p, 2q-p,\ldots, (p-1)q-p \}.$ Note \begin{align*} \sum_{b \in S} b^2 &= \sum_{b\in S} (b-p)^2 - \sum_{i=1}^{p-1} i^{2} + \sum_{i=1}^{p-1} (qi-p)^{2} \\ &= \sum_{b\in S} b^2 -2p\sum_{b\in S} b + \frac{1}{2}(p-1)(q-1)p^2 - \sum_{i=1}^{p-1} i^{2} + \sum_{i=1}^{p-1} (qi-p)^{2} \\ \end{align*} So it suffices to show that $\sum_{i=1}^{p-1} (qi-p)^{2}-\sum_{i=1}^{p-1} i^{2}$ times a fixed constant is always divisible by $p(p-1)(q-1)$ which is easy. Now, suppose we want to show for $n = 2k-1.$ Note \begin{align*} \sum_{b \in S} b^{2k} &= \sum_{b\in S} (b-p)^{2k} - \sum_{i=1}^{p-1} i^{2k} + \sum_{i=1}^{p-1} (qi-p)^{2k} \\ &= \sum_{b\in S} b^{2k} -2p\sum_{b\in S} b^{2k-1} + (p-1)(q-1)pc - \sum_{i=1}^{p-1} i^{2k} + \sum_{i=1}^{p-1} (qi-p)^{2k} \\ \end{align*} where $c$ is some rational number independent of $p-1,q-1$ that exists due to the inductive assumption (we can add the $p$ in there due to the properties of binomial expansion). It suffices to show that some fixed integer times $ \sum_{i=1}^{p-1} (qi-p)^{2k}-\sum_{i=1}^{p-1} i^{2k} $ always yields a multiple of $p(p-1)(q-1).$ To do this, we rewrite the sum as $$\sum_{i=1}^{p-1} (i(q-1)- (p-i))^{2k}-\sum_{i=1}^{p-1} i^{2k}.$$ Showing that this is a multiple of $q-1$ is trivial. So we divide by $q-1$ getting $$\sum_{j=1}^{2k} (-1)^j (q-1)^{j-1} \binom{2k}{j} \left( 1^{j} (p-1)^{2k-j} + 2^{j}(p-2)^{2k-j} + \dots + (p-1)^{j}1^{2k-j} \right).$$ It's not hard to show that some fixed integer in terms of $k, j$ times $1^{j} (p-1)^{2k-j} + 2^{j}(p-2)^{2k-j} + \dots + (p-1)^{j}1^{2k-j}$ will yield a multiple of $p(p-1)$ and we're done. $\square$
CANBANKAN
22.01.2023 08:59
I want to expand a bit on the motivation behind the generating function solution, once we got to the "good integers" part. If I want to use the ordinary generating function to handle this, I get a sum of the form $$\sum_{n\ge 0} \sum_{a=0}^{q-2} \sum_{b=0}^{\lfloor \frac{p(q-1-a)}{q}\rfloor} ((ap+bq)x)^n$$ If I swap the order of the summations, this is difficult to handle. However, if I use the exponential generating functions, its algebraic properties are really useful $$\sum_{n\ge 0} \sum_{a=0}^{q-2} \sum_{b=0}^{\lfloor \frac{p(q-1-a)}{q}\rfloor} ((ap+bq)x)^n/n! = \sum_{a=0}^{q-2} \sum_{b=0}^{\lfloor \frac{p(q-1-a)}{q}\rfloor} \exp((ap+bq)x) =\sum_{a=0}^{q-2} \exp(apx) \sum_{b=0}^{\lfloor \frac{p(q-1-a)}{q}\rfloor} \exp(bqx) $$ This is conveniently a geometric series.
lbh_qys
02.08.2024 05:26
A generating function method that avoids complex calculations is as follows: We still consider the generating function of all "good" integers, but here we consider all "good" integers in the infinite range instead of being limited to within \( pq - p - q \): $$ F(x) = \sum_{k} f(k) x^k$$ where \( f(k) \) indicates whether \( k \) can be represented as a non-negative linear combination of \( p \) and \( q \), taking values of 0 or 1. Let's examine the recurrence relation of \( f(k) \). By considering the idea of eliminating duplicates, it is easy to come up with: $$f(k) = f(k-p) + f(k-q) - f(k-p-q)$$ This recurrence relation is correct in most cases, but there are still special cases to handle: 1. When \( f(k) = 1 \) but \( f(k-p), f(k-q) = 0 \), there is no basis for calculation. In this case, only \( k=0 \) applies. 2. When \( f(k-p) = f(k-q) = 1 \) and \( f(k-p-q) = 0 \), the solutions are counted twice. In this case, only \( k = pq \) applies. Thus, the complete recurrence relation is: $$f(k) = f(k-p) + f(k-q) - f(k-p-q) + [k=0] - [k=pq]$$ Using this recurrence relation, we immediately obtain the generating function \( F \) satisfying: $$F = F \cdot x^{p} + F \cdot x^{q} - F \cdot x^{p+q} + x^0 - x^{pq}$$ Solving this, we get: $$F(x) = \frac{1 - x^{pq}}{(1-x^p)(1-x^q)}$$ Since the generating function for all non-negative integers is \( \frac{1}{1-x} \), the generating function for "bad" integers is: $$\frac{1}{1-x} - F(x) = \frac{1}{1-x} - \frac{1-x^{pq}}{(1-x^p)(1-x^q)}$$ Now, by replacing \( x \) with \( \exp(x) \) in the generating function, we immediately obtain the exponential generating function we need: $$\frac{1}{1-\exp(x)} - \frac{1-\exp(pq x)}{(1-\exp(px))(1-\exp(qx))}$$ From this, it is evident that each term \( x^i \) in the series has coefficients that are rational polynomials in \( p \) and \( q \). The remaining work is trivial.