Polynomial Version of Thue's Lemma on Linear Congruences

Polynomial version of Thue's lemma on "small" solutions to "ratio" congruences

This is an example of the analogy between integers and polynomials.

(The usual Thue's lemma is covered elsewhere in the map.). But we won't actually need that integer stuff in our discussion here. :)

First, what are we even trying to do here? Let's recall the state of the usual Thue's lemma:

(Thue's lemma/theorem) If $m>0$ and $c$ is an integer relatively prime to $m$, then there exists a pair $(a,b)\in\{1,2,\ldots,\lfloor\sqrt{m}\rfloor\}^2$ of "small" integers solving the linear "ratio" congruence $a\equiv \pm cb\pmod{m}$.

Try to formulate an analog yourself, before reading below!

It turns out the following analog holds:

(MOP TSTST 2014 Problem 4) If $M(x)$ is a nonzero polynomial (over any field, such as the rationals, reals, complex numbers, or integers modulo a prime) and $C(x)$ is a polynomial relatively prime to $M(x)$, then there exists a pair $(A(x),B(x))\in\{\text{polynomials of degree }\le\frac{\deg{M}}{2}\}^2$ of "small" polynomials solving the linear "ratio" congruence $A(x)\equiv C(x)B(x)\pmod{M(x)}$.

As an example, consider the $n=7$ case of Lucas's theorem on cyclotomic polynomials: the identity $$x^6-x^5\pm\cdots-x+1 = \Phi_7((-1)^{(7-1)/2}x) = C_7(x)^2 - 7x D_7(x)^2,$$ where $C_7(x) = x^3+3x^2+3x+1$ and $D_7(x) = x^2+x+1$.

Let $M(x) = x^6 - x^5\pm\cdots-x+1$ and $C(x)$ be a square root of $7x$, in the sense that $C^2 \equiv 7x \pmod{M}$. (Why does this square root exist? How many square roots are there, and can you compute all of them?) Then the identity tells us that $$C_7(x) \equiv \pm C(x)D_7(x)\pmod{M},$$ where the sign depends on the choice of square root $C(x)$. Notice also that $C_7$ has degree $3 = \frac{7-1}{2}$, the largest integer less than $\frac{\deg{M}}{2} = \frac{7}{2}$.

(We can do something similar with Gauss's cyclotomic formula; see also Wikipedia.)