Generalization of Lagrange's theorem $(1768)$?

Question

Here's the theorem :

Let $p$ a prime number and $u_0,...,u_n$, a list of integers such that $p\not \mid u_n$. Then : $u_nx^n+...+u_1x+u_0 \equiv 0\pmod p$ admits at most $n$ solutions $\pmod p$.

The proof can by done using induction on $n$ and the property of the prime number $p$.

Now, I was wondering how it will work if we consider an integer $k$ instead of $p$. The statement will give :

Let $k$ an integer and $u_0,...,u_n$, a list of integers such that $\gcd(k,u_n)=1$. Then how many solutions $\pmod k$ the equation : $u_nx^n+...+u_1x+u_0 \equiv 0\pmod k$ admits ?

I think we can start with the decomposition theorem $k=p_1^{a_1}...p_l^{a_l}$. Maybe it will give a system in CRT style.

Here's my attempt :

First important fact : if $k\mid u_n\Leftrightarrow p_1^{a_1}...p_l^{a_l}\mid u_n\Rightarrow \exists i\in \{1,...,l\}, \ p_i^{l_i}\mid u_n$.

For a factor $p_i^{a_i}$ we try to find the number of solutions $\pmod{p_i^{a_i}}$ of the equation : $u_nx^n+...+u_1x+u_0\equiv 0 \pmod{p_i^{a_i}}$.

By induction on $n$ I have :

-For $n=0$ : the equation becomes : $u_1x\equiv -u_0 \pmod{p_i^{a_i}}$.

The equation becomes $u_1x\equiv -u_0 \pmod{p_i^{a_i}}$. But we have $\gcd(u_1,p_i)=1$ and by property of Bézout we can deduce that $\gcd(u_1,p_i^{a_i})=1$. So $u_1$ has an inverse element and we can take $x\equiv -u_1^{-1}u_0 \pmod{p_i^{a_i}}$ which represents one solution (the only one).

-For $n=n+1$ : the equation becomes $u_{n+1}x^{n+1}+u_nx^n+...+u_1x+u_0\equiv 0 \pmod{p_i^{a_i}}$.If I consider $y$ a solution of the equation with the multiplicity $e=1$ (for instance) we have the fact that we can factorize the equation by $(x-y)^{e}$ .

It gives $(x-y)^{e}P(x)\equiv 0 \pmod{p_i^{a_i}}$ with $P$ a degree $n$ polynomial and with highest coefficient $u_{n+1}$ such that $\gcd(p_i^{a_i},u_{n+1})=1$. So the equation admits at most $n+1$ solutions $\pmod{p_i^{a_i}}$.

So there is at most $n$ solutions for $\pmod{p_i^{a_i}}$ and for each $i\in \{1,...,l\}$.

If I want to use the CRT it gives a systeme of $l$ lines where each polynomials admit at most $n$ solutions. How can I conclude $\pmod k$ (it's not a field) ?

If we suppose that for each $p_i^{a_i}$ there are at most $n$ solutions we can factorize the $l$ lines with $n$ factors.

Unfortunately this fact is false (look at $(x-1)(x-2)(x-4)\equiv 0 \pmod{9}$ which have $4$ solutions instead of $3$).

Here is the main system :

$\left\{\begin{array}{rl} u_{n}(x-x_{1_1})(x-x_{1_2})...(x-x_{1_n}) &\equiv 0 \pmod{p_1^{a_1}} \\ &\vdots \\ u_{n}(x-x_{i_1})(x-x_{i_2})...(x-x_{i_n}) &\equiv 0 \pmod{p_i^{a_i}} \\ &\vdots \\ u_{n}(x-x_{l_1})(x-x_{l_2})...(x-x_{l_n}) &\equiv 0 \pmod{p_l^{a_l}} \\ \end{array} \right.$

And for instance by Euclid's lemma (for the case of $(a_i)_{i\{1,...,l\}}=1$) to count the number of systems : for $u_{n}(x-x_{1_1})$ we have $(n^{(l-1)})$ systems possible with one solution. It's the same for each $u_{n}(x-x_{i_j})$ with $j\in \{1,...,n\}, \ i=1$ right.If it's the case it will give $n^l$ solutions.

Thanks in advance !

Answer 1

By CRT, the number of solutions mod $k$ is the product of the numbers of solutions mod $p_i^{a_i}$. So we reduce to working mod $p^a$. But you want to make your assumption $\gcd(k, a_n) =1$, not $k \not\mid a_n$.

Suppose your polynomial $f(x)$ has degree $n$. Mod $p$ it may have up to $n$ linear factors, counted by multiplicity. Each solution mod $p^{a}$ is also a solution mod $p$. Hensel's lemma says if $f(r) \equiv 0 \mod p$ and $f'(r) \not\equiv 0 \mod p$, there is a unique solution of $f(x)=0 \mod p^a$ such that $x \equiv r \mod p$. But if $f'(r) \equiv 0 \mod p$ (i.e. $r$ is a multiple root mod $p$), there may be more: maybe as many as $p^{a-1}$. So if $a > 1$ we get a bound of $p^{a-1} n/2$ solutions mod $p^a$. This is probably not best possible, but it's a start.