I am too lazy to post a solution so I will post a general outline: (1) We can assume that the degree of Q is greater than d/2 (because otherwise we could let A(x) = Q(x) and B(x) = -1) and that the degree of Q is less than d (because otherwise the remainder of Q upon division by P would satisfy the same condition so we could have just taken that remainder, which has degree less than d) (2) We essentially want the coefficient of x^k for all k > d/2 in the polynomial P(x)C(x) - Q(x)B(x) to be 0. Writing the coefficients of A and B as variables and treating the coefficients of P and Q as constants we basically get a linear system of at most d equations and d + 1 variables, none of which have constant terms. They clearly cannot be inconsistent, and moreover since there are more equations than variables there must be a non-trivial solution so we are done. I personally was disgusted by this problem (that may have had something to do with the fact that it ate up 4 hours of my time). The "linear algebra" solution is not hard - in fact, it requires no real finesse at all, and it really is motivated since finding any polynomial that satisfies conditions like these does always boil down to systems of equations. However, the absence of a really "nice" solution does make it somewhat tricky (at least to me).

Oops, I'm still not sure why/how this got on TSTST (I agree it was a bad choice), but some comments: 0. This problem was inspired by Lucas's (cyclotomic) theorem, with $P(x) = \Phi_n(x)$. 1. Compare with \href{http://www.math.uga.edu/~pete/Brauer-Reynolds51.pdf}{Thue's} \href{http://mathworld.wolfram.com/ThuesTheorem.html}{theorem}: If $m>0$ and $\gcd(c,m)=1$, then there exists $(a,b)\in\{1,2,\ldots,\lfloor\sqrt{m}\rfloor\}^2$ such that $a\equiv \pm cb\pmod{m}$. 2. For finite fields $F$, we can also use a counting/pigeonhole argument. If $q=|F|$, then there are $(q^{1+\lfloor{d/2}\rfloor})^2\ge q^{d+1}$ pairs $(U,V)\in F[x]^2$ of degree $\le d/2$ polynomials (here we include the $0$ polynomial), but only $q^d$ possible remainders $U - CV\pmod{M}$. By pigeonhole, there must exist distinct $(U_1,V_1)$ and $(U_2,V_2)$ with $U_1-CV_1\equiv U_2-CV_2\pmod{M}$; then $V_1\not\equiv V_2\pmod{M}$ (or else $U_1\equiv U_2$ gives $(U_1,V_1) = (U_2,V_2)$), and since $C,M$ are coprime, $U_1\not\equiv U_2\pmod{M}$ (or else $V_1\equiv V_2$ gives $(U_1,V_1) = (U_2,V_2)$). Thus we may take $(A,B) = (U_1-V_1,U_2-V_2)$.

In the vein of the previous post, here's another approach for $d/2 < \deg Q < d$, where the idea is basically the pigeonhole principle for degrees of remainder polynomials: Let $\deg Q = m$ and first consider $m < d$. As said above, if $m \le d/2$, then choose $A(x) \equiv Q(x)$ and $B(x) \equiv -1$. For $d/2 < m < d$, we have a lemma. $\textbf{Lemma}$: For integral $i$ such that $0 \le i \le m-\lceil d/2 \rceil$, if there exist $m - \lceil d/2 \rceil - i+1$ equations $T_j(x) P(x) = Q(x) S_j(x)+R_j(x)$ such that for $j = 0,1,\ldots, m-\lceil d/2 \rceil -i$, $\deg R_j \le m-1-i$ and $\deg S_j(x) \le d/2$, then there are polynomials $T, S$ such that $C(x)P(x) = Q(x)B(x)+A(x)$ with $\deg A, \deg B \le d/2$. Proof: Induct down on $i$, beginning with $i = m-\lceil d/2 \rceil$. If there is one equation $T_0(x)P(x) = Q(x)S_0(x) + R_0(x)$ with $\deg R_0 \le m-1- (m-\lceil d/2 \rceil) \le d/2$ and $\deg S_0(x) \le d/2$ then take $A(x) \equiv R_0(x)$ and $B(x) \equiv S_0(x)$. Now for some $0 \le i < m-\lceil d/2 \rceil$, assume the claim holds for $j = i+1$ and consider $j = i$ such equations. If for any $j$ the $j$-th equation is such that $\deg R_j \le d/2$, then use that equation as in the base case. If some subset of $m -\lceil d/2 \rceil - (i+1) +1$ equations are such that $\deg R_j(x) \le m-1-(i+1)$ for each equation, then the claim follows from the induction hypothesis using these equations. Otherwise, there are $k \ge 2$ equations with $\deg R_j(x) = m-1-i$. Let this set of equations be $F$ and pick some $P' \in F$. For arbitrary $P'' \neq P'$ in $F$, by multiplying $P'$ by an appropriate constant then subtracting from $P''$, we can remove the highest degree term in the corresponding remainder polynomial. Doing this for all polynomials in $F \setminus \{P'\}$, we get $k-1$ equations together with the polynomial equations outside of $F$, totaling $m-\lceil d/2 \rceil - (i+1)+1$ equations of the form $\bar{T}(x)P(x) = Q(x)\bar{S}(x) + \bar{R}(x)$ with $\deg \bar{S} \le d/2$ and $\deg \bar{R} \le m-1-(i+1)$. (So it's a kind of Gaussian elimination on the elements of $F$.) We then invoke the induction hypothesis. $\square$ Apply this lemma for $i = 0$ with the equations $x^jP(x) = Q(x)S_j(x)+R_j(x)$ for $j = 0,1,\ldots, m-\lceil d/2 \rceil$ with $\deg R_j(x) \le m-1$ for each $j$. ($\deg x^jP(x) \le m-\lceil d/2 \rceil + d = m + \lfloor d/2 \rfloor$, so that $\deg S_j(x) \le \lfloor d/2 \rfloor$.) Also as said above, for the case of $m \ge d$, letting $Q(x) = P(x) S(x) + R(x)$ with $\deg R < d$, we can reduce to finding $A,B$ for $R$ rather than $Q$, which will then work for $Q$.

TSTST 2014/4 If $\deg Q\le d/2$, then simply pick $B=1$ and $A=-Q$. So we can assume that $\deg Q>d/2$. Let $N$ be some number way bigger than $\deg P+\deg Q$. Let $V$ be the vector space of polynomials of degree at most $N$. Let $V_1$ be the vector space of polynomials of the form $\alpha(x)P(x)$ and that have degree at most $N$. Note then that $\deg\alpha=N-d$, so $\dim V=N-d+1$. Let $V_2$ be the vector space of polynomials of the form $A(x)+Q(x)B(x)$ where $\deg A,\deg B\le d/2$. Note that \[1,x,\ldots,x^{\lfloor d/2\rfloor},Q(x),xQ(x),\ldots,x^{\lfloor d/2\rfloor}Q(x)\in V_2\]and have all different degrees, so they are all linearly independent. Thus, $\dim V_2\ge 2(1+\lfloor d/2\rfloor)>d$. We want to show that $V_2$ and $V_1$ have nontrivial intersection (besides $0$). However, $V_1,V_2$ are both subspaces of $V$ (which has dimension $N+1$), and yet the dimensions of $V_1$ and $V_2$ add to more than $N+1$. If $V_1\cap V_2=\{0\}$, then we could combine bases of $V_1$ and $V_2$ to show that $\dim V>N+1$, which is not possible. Therefore, $V_1\cap V_2$ has more than just $0$, as desired.

Lemma. Let $V$ be a vector space and let $A,B \subset V$ be two subspaces such that $A\cap B = 0_{V}$. Then $\dim A + \dim B \le \dim V$. Proof. Consider the sumspace $A+B$. We know it is a direct sum since if $\sum_{a\in A} a + \sum_{b\in B} b = 0$ then $\sum_{a\in A} a \in (A\cap B)$. Therefore $\dim A+B = \dim A \oplus B = \dim A + \dim B$. But $A+B$ is a subspace of $V$, so $\dim A\oplus B \le \dim V$. $\square$ Back to the original problem. Denote by $V_t$ the real vector space of real-coefficient polynomials with degree at most $t$. For any $B(x) \in V_{d/2}$, let $R(x)$ be the remainder polynomial when we divide $B(x)Q(x)$ by $P(x)$, then $\deg R < \deg P = d$. Define a map $L: V_{d/2} \to V_{d-1}$ by $L(B(x)) = R(x)$. We can easily check that $L$ is a linear map. Furthermore, if some nonzero polynomial $B_0(x) \in \ker L$, then we are already done since we can just take $A(x) = 0$ and $B(x) = B_0(x)$. Thus, $\dim \text{img} L = \frac{d}{2}+1$. Now, using the lemma, we see that since $2(\lfloor\frac{d}{2}\rfloor+1) > d$, the vector spaces $V_{d/2}$ and $\text{img} L$ (both being subspaces of $V_{d-1}$) have nontrivial intersection. Therefore we can take $A(x)$ to be an element in the intersection and take $B(x)$ be be its preimage.

If $deg Q \le \frac{d}{2}$, pick $B=1, A=-Q$. Let $d > deg Q>\frac{d}{2}$. $gcd(P, Q)=D$, if $deg D \le \frac{d}{2}$, by Bezout’s Theorem, we can just use Euclidean algorithm to construct $X, Y$ such that $PX+QY=D$. Then $deg Y \le deg P - deg Q <\frac{d}{2}$, and $A=D, B= -Y$ satisfies the condition. Else $deg D> \frac{d}{2}$, let $A=0, B= \frac{P}{D}$, notice that $ deg \frac{P}{D} < d-\frac{d}{2} =\frac{d}{2}$ so this also satisfies the condition, we’re done.

Let $n=\left\lfloor\frac{d}{2}\right\rfloor$. Let $V$ be the vector space of polynomials of degree at most $n$: \[ V=\{a_nx^n+\cdots+a_1x+a_0\mid a_0,a_1,\ldots,a_n\in\mathbb{R}\}. \]Fix $P$ and $Q$. Let $V'$ be the vector space of polynomials of degree at most $d-1$: \[ V'=\{a_{d-1}x^{d-1}+\cdots+a_1x+a_0\mid a_0,a_1,\ldots,a_{d-1}\in\mathbb{R}\}. \]Let $T:V^2\rightarrow V'$ be a linear map given by \[ (A,B)\mapsto A+Q\cdot B\mod P. \]Since \[ \dim V^2=2\left(\left\lfloor\frac{d}{2}\right\rfloor+1\right)\geq d+1=\dim V'+1, \]by the rank-nullity theorem, there exists a nonzero pair $(A,B)\in V^2$ satisfying \[ A+Q\cdot B\mod P=0. \]The conclusion follows.

Cindy.tw wrote: If $deg Q \le \frac{d}{2}$, pick $B=1, A=-Q$. Let $d > deg Q>\frac{d}{2}$. $gcd(P, Q)=D$, if $deg D \le \frac{d}{2}$, by Bezout’s Theorem, we can just use Euclidean algorithm to construct $X, Y$ such that $PX+QY=D$. Then $deg Y \le deg P - deg Q <\frac{d}{2}$, and $A=D, B= -Y$ satisfies the condition. Else $deg D> \frac{d}{2}$, let $A=0, B= \frac{P}{D}$, notice that $ deg \frac{P}{D} < d-\frac{d}{2} =\frac{d}{2}$ so this also satisfies the condition, we’re done. but how can you make sure that $deg Y\le deg P - deg Q$

The condition essentially says $$Q(x)B(x)\equiv -A(x)\pmod{P(x)}.$$Thus, we are trying to show that there exists a polynomial $B$ with degree at most $d/2$ such that the remainder when $Q(x)B(x)$ is divided by $P(x)$ has degree at most $d/2$. Let $R(x)=\gcd(P(x),Q(x))$, so that there exists $B$ for which $$Q(x)B(x)\equiv R(x)\pmod{P(x)}.$$ This construction works as long as $R$ has degree at most $d/2$. If $R$ has degree more than $d/2$, then $\frac{P}{R}$ has degree less than $d/2$, which means that we can let $B=\frac{P}{R}$ and $A=0$.