Congruence Equations

For a prime $p$ and an integer $e>1$, let the integer-coefficient polynomial be $f(x)=\sum_{i=0}^na_ix^i~(p^e\nmid a_n)$, and let $f'(x)=\sum_{i=1}^nia_ix^{i-1}$ be its derivative. Let $x_0$ be a solution of

Then:

1. If $f'(x_0)\not\equiv 0\pmod p$, there exists an integer $t$ such that

   $$x=x_0+p^{e-1}t \tag{3}$$

   is a solution of

   $$f(x)\equiv 0\pmod{p^e} \tag{4}$$

2. If $f'(x_0)\equiv 0\pmod p$ and $f(x_0)\equiv 0\pmod{p^e}$, then for $t=0,1,\dots,p-1$, every $x$ determined by equation $(3)$ is a solution of equation $(4)$.

3. If $f'(x_0)\equiv 0\pmod p$ and $f(x_0)\not\equiv 0\pmod{p^e}$, then no solution of equation $(4)$ can be constructed from equation $(3)$.

Assume that equation $(3)$ is a solution of equation $(4)$, that is,

Rearranging gives

Therefore

1. If $f'(x_0)\not\equiv 0\pmod p$, equation $(5)$ in $t$ has a unique solution $t_0$, and substituting into equation $(3)$ verifies that it is a solution of equation $(4)$.
2. If $f'(x_0)\equiv 0\pmod p$ and $f(x_0)\equiv 0\pmod{p^e}$, every $t$ makes equation $(5)$ hold, and substituting into equation $(3)$ verifies that each is a solution of equation $(4)$.
3. If $f'(x_0)\equiv 0\pmod p$ and $f(x_0)\not\equiv 0\pmod{p^e}$, equation $(5)$ has no solution, so no solution of equation $(4)$ can be constructed from equation $(3)$.

For the $p$, $e$, $f(x)$, and $x_0$ of Theorem 1:

1. If $s$ is a solution of $f(x)\equiv 0\pmod p$ and $f'(s)\not\equiv 0\pmod p$, there exists $x_s\in\mathbf{Z}_{p^e}$ with $x_s\equiv s\pmod p$ such that $x_s$ is a solution of equation $(4)$.
2. If $f(x)\equiv 0\pmod p$ and $f'(x)\equiv 0\pmod p$ have no common solution, then equation $(4)$ and $f(x)\equiv 0\pmod p$ have the same number of solutions.

If

has $k$ distinct solutions $x_1,x_2,\dots,x_k~(k\leq n)$, then

where $\deg g=n-k$ and $[x^{n-k}]g(x)=a_n$.

Apply mathematical induction on $k$.

• When $k=1$, perform polynomial division with remainder: $f(x)=(x-x_1)g(x)+r$, where $r\in\mathbf{Z}$.

  Since $f(x_1)\equiv 0\pmod p$, we have $r\equiv 0\pmod p$, and therefore $f(x)\equiv(x-x_1)g(x)\pmod p$.

• Assume the claim holds for $k-1$ ($k>1$). Now suppose $f(x)$ has $k$ distinct solutions $x_1,x_2,\dots,x_k$. Then $f(x)\equiv(x-x_1)h(x)\pmod p$, and therefore

  $$(\forall i=2,3,\dots,k),~~0\equiv f(x_i)\equiv (x_i-x_1)h(x_i)\pmod p$$

  Thus $h(x)$ has $k-1$ distinct solutions $x_2,x_3,\dots,x_k$. By the induction hypothesis,

  $$h(x)\equiv g(x)\prod_{i=2}^k(x-x_i)\pmod p$$

  where $\deg g=n-k$ and $[x^{n-k}]g(x)=a_n$.

  The claim follows.

For a prime $p$,

• $(\forall x\in\mathbf{Z}),~~x^{p-1}-1 \equiv \prod_{i=1}^{p-1}(x-i)\pmod p$.
• (Wilson's theorem) $(p-1)! \equiv -1 \pmod p$.

Equation $(6)$ has at most $n$ distinct solutions.

Suppose $f(x)$ has $n+1$ distinct solutions $x_1,x_2,\dots,x_{n+1}$. By Theorem 2, for $x_1,x_2,\dots,x_n$,

Let $x=x_{n+1}$. Then

However, the right-hand side is clearly not a multiple of $p$, a contradiction.

If the number of solutions of the congruence equation $\sum_{i=0}^nb_ix^i\equiv 0\pmod p$ is greater than $n$, then

If the number of solutions of equation $(6)$ is not $p$, then there must exist a polynomial satisfying $\deg r [!note]+ Proof

Without loss of generality, let $n\geq p$. Divide $f(x)$ by x^p-x with remainder

where $\deg r By [Fermat's little theorem](/knowledge-pages/math-number-theory-fermat), for every integer$x$,$x^p\equiv x\pmod p$, so:

• If $r(x)\equiv 0\pmod p$, then by Corollary 2, $f(x)$ has $p$ distinct solutions.
• If $r(x)\not\equiv 0\pmod p$, then $f(x)\equiv r(x)\pmod p$ shows that $f(x)$ and $r(x)$ have the same solution set.

Let $n\leq p$. Then equation

has $n$ solutions if and only if there exist integer-coefficient polynomials $q(x)$ and $r(x)~(\deg r < n)$ such that

• Necessity: polynomial division gives integer-coefficient polynomials $q(x)$ and $r_1(x)~(\deg r_1 < n)$ such that

  $$x^p-x=f(x)q(x)+r_1(x).$$

  If equation $(7)$ has $n$ solutions, then $r_1\equiv 0\pmod p$ also has the same $n$ solutions. By Corollary 3, there is an integer-coefficient polynomial $r(x)$ satisfying $r_1(x)=pr(x)$, proving the claim.

• Sufficiency: If equation $(8)$ holds, then by Fermat's little theorem, for every integer $x$,

  $$0\equiv x^p-x\equiv f(x)q(x)\pmod p.$$

  Thus the equation $f(x)q(x)\equiv 0\pmod p$ has $p$ solutions.

  Let the number of solutions of equation $(7)$ be $s$. By Lagrange's theorem, $s\leq n$.

  Since $\deg q=p-n$, Lagrange's theorem shows that the number of solutions of $q(x)\equiv 0\pmod p$ is at most $p-n$. The solution set of $f(x)q(x)\equiv 0\pmod p$ is the union of the solution sets of $f(x)\equiv 0\pmod p$ and $q(x)\equiv 0\pmod p$, so $s+(p-n)\geq p$, and $s\geq n$.

  Therefore $s=n$.

Let $n\mid p-1$ and $p\nmid a$. Then equation

has a solution if and only if

Moreover, if $(9)$ has a solution, the number of solutions is $n$.

For the concrete structure of the solution set of equation $(9)$, see k-th power residues.

• Necessity: If equation $(9)$ has a solution $x_0$, then

  $$a^{\frac{p-1}{n}}\equiv {\left(x_0^n\right)}^{\frac{p-1}{n}}\equiv 1\pmod p$$

• Sufficiency: If $a^{\frac{p-1}{n}}\equiv 1\pmod p$, then

  $$\begin{aligned} x^p-x&=x\left(x^{p-1}-1\right)\\ &=x\left(\left(x^n\right)^{\frac{p-1}{n}}-a^{\frac{p-1}{n}}+a^{\frac{p-1}{n}}-1\right)\\ &=\left(x^n-a\right)P(x)+x\left(a^{\frac{p-1}{n}}-1\right)\\ \end{aligned}$$

  where $P(x)$ is an integer-coefficient polynomial. Therefore, by Theorem 5, equation $(9)$ has $n$ solutions.