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 !

  • $\begingroup$ start with two extremes: first, squarefree numbers $pq,$ then $pqr.$ $\endgroup$ – Will Jagy Sep 28 '16 at 17:02
  • $\begingroup$ @WillJagy later I will post an advancement. But we'll see where the problem is ;) $\endgroup$ – Maman Sep 28 '16 at 17:04

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.

  • 1
    $\begingroup$ Where does $\frac{n}{2}$ comme from ? $\endgroup$ – Maman Sep 30 '16 at 23:04
  • $\begingroup$ $f(x)$ has at most $n$ roots mod $p$, counted by multiplicity. A root that has multiplicity $m>1$ could correspond to $p^{a-1}$ roots mod $p^a$, while any with multiplicity $1$ just get one root mod $p^a$. The worst case is that you have $n/2$ distinct roots, each of multiplicity $2$, resulting in $p^{a-1}n/2$ roots mod $p^a$. $\endgroup$ – Robert Israel Sep 30 '16 at 23:54
  • $\begingroup$ For a root of multiplicity 2, why is p^(a-1) the upper bound (per double root)? The number of solutions to x^2=0 mod p^a is about p^(a/2). $\endgroup$ – zyx Oct 1 '16 at 0:20
  • $\begingroup$ It seems that with this answer the maximum case is not reached when each equation $\pmod {p_i^{a_i}}$ has $n$ distinct solutions. I'm confused... $\endgroup$ – Maman Oct 1 '16 at 0:52
  • $\begingroup$ Maybe it is $p^{a/2}$: that's $\le p^{a-1}$ if $a \ge 2$, so my bound stands. $\endgroup$ – Robert Israel Oct 1 '16 at 1:32

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.