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
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.
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)$.
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).$$
The first step is to characterize all the bad numbers. Claim 1: Bad numbers are of the form $px+qy$.
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$.
Claim 3: $P(n)$ is true for all odd $n$.
Thus the result must be true for $P(2019)$ as well.
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.
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$
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.
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.