Skip to content

Congruence Equations

Definition

Congruence Equation

For a positive integer \(m\) and a univariate polynomial with integer coefficients \(f(x)=\sum_{i=0}^n a_ix^i\), where the unknown \(x\in\mathbf{Z}_m\), an equation of the form

\[ f(x)\equiv 0\pmod m\tag{1} \]

is called a congruence equation modulo \(m\) with unknown \(x\).

If \(a_n\not\equiv 0\pmod m\), then the above equation is called a congruence equation of degree \(n\).

Systems of congruence equations can be defined similarly.

For content related to linear congruence equations and systems, please refer to Linear Congruence Equation and Chinese Remainder Theorem.

This article first studies the solvability and solution set structure of congruence equations, and then briefly introduces methods for solving higher-degree congruence equations.

From the Chinese Remainder Theorem, solving a congruence equation modulo a composite number \(m\) can be reduced to solving modulo prime powers. Therefore, only the theory related to congruence equations modulo prime powers and modulo primes is introduced below.

Congruence Equations Modulo Prime Powers

Here we assume the modulus is \(m=p^e~(p\in\mathbf{P},~e\in\mathbf{Z}_{>1})\).

Note that if \(x_0\) is a solution to the equation

\[ f(x)\equiv 0\pmod{p^e} \]

then \(x_0\) is also a solution to the equation

\[ f(x)\equiv 0\pmod{p^{e-1}} \]

This inspires us to try constructing solutions for higher moduli from solutions for lower moduli. We have the following theorem:

Theorem 1 (Hensel's Lemma)

For a prime \(p\) and integer \(e>1\), take a polynomial with integer coefficients \(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 to the equation

\[ f(x)\equiv 0\pmod{p^{e-1}}\tag{2} \]

Then:

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

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

    is a solution to the equation

    \[ 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\), the \(x\) determined by formula \((3)\) are all solutions to equation \((4)\).

  3. If \(f'(x_0)\equiv 0\pmod p\) and \(f(x_0)\not\equiv 0\pmod{p^e}\), then solutions to equation \((4)\) cannot be constructed from formula \((3)\).
Proof

Assume formula \((3)\) is a solution to equation \((4)\), i.e.,

\[ f(x_0+p^{e-1}t)\equiv 0\pmod{p^e} \]

Rearranging gives

\[ f(x_0)+p^{e-1}tf'(x_0)\equiv 0\pmod{p^e} \]

Hence,

\[ tf'(x_0)\equiv -\frac{f(x_0)}{p^{e-1}}\pmod p\tag{5} \]
  1. If \(f'(x_0)\not\equiv 0\pmod p\), then equation \((5)\) for \(t\) has a unique solution \(t_0\), which when substituted into formula \((3)\) can be verified as a solution to equation \((4)\).
  2. If \(f'(x_0)\equiv 0\pmod p\) and \(f(x_0)\equiv 0\pmod{p^e}\), then any \(t\) satisfies equation \((5)\), and substituting into formula \((3)\) verifies they are all solutions to equation \((4)\).
  3. If \(f'(x_0)\equiv 0\pmod p\) and \(f(x_0)\not\equiv 0\pmod{p^e}\), then equation \((5)\) has no solution, so solutions to equation \((4)\) cannot be constructed from formula \((3)\).

Consequently, we have a corollary:

Corollary 1

For \(p\), \(e\), \(f(x)\), \(x_0\) from Theorem 1,

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

Thus, we can reduce congruence equations modulo prime powers to congruence equations modulo primes.

Congruence Equations Modulo Primes

Here let \(p\in\mathbf{P}\), and \(f(x)=\sum_{i=0}^na_ix^i\) be a polynomial with integer coefficients, where \(p\nmid a_n\), \(x\in\mathbf{Z}_p\).

Theorem 2

If the equation

\[ f(x)\equiv 0\pmod p\tag{6} \]

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

\[ f(x)\equiv g(x)\prod_{i=1}^k(x-x_i)\pmod p, \]

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

Proof

Use 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\), so \(f(x)\equiv(x-x_1)g(x)\pmod p\).

  • Assume the proposition 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 we have

    \[ (\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\).

    Therefore, the proposition is proved.

Corollary 2

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\).

Theorem 3 (Lagrange's Theorem)

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

Proof

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

\[ f(x)\equiv a_n\prod_{i=1}^n(x-x_i)\pmod p \]

Let \(x=x_{n+1}\), then

\[ 0\equiv f(x_{n+1})\equiv a_n\prod_{i=1}^n(x_{n+1}-x_i)\pmod p \]

The right side is clearly not divisible by \(p\), so the assumption leads to a contradiction.

Corollary 3

If the congruence equation \(\sum_{i=0}^nb_ix^i\equiv 0\pmod p\) has more than \(n\) solutions, then

\[ (\forall i=0,1,\dots,n),~~p\mid b_i. \]

Theorem 4

If the number of solutions to equation \((6)\) is not \(p\), then there exists a polynomial \(r(x)\) with integer coefficients satisfying \(\deg r<p\) such that \(f(x)\equiv 0\pmod p\) and \(r(x)\equiv 0\pmod p\) have the same solution set.

Proof

Assume \(n\geq p\). Perform polynomial division on \(f(x)\):

\[ f(x)=g(x)\left(x^p-x\right)+r(x) \]

where \(\deg r<p\).

By Fermat's Little Theorem, for any integer \(x\), \(x^p\equiv x\pmod p\). Thus,

  • 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 from \(f(x)\equiv r(x)\pmod p\), \(f(x)\) and \(r(x)\) have the same solution set.

We can use this theorem to reduce the degree of a congruence equation.

Theorem 5

Let \(n\leq p\). Then the equation

\[ x^n+\sum_{i=0}^{n-1}a_ix^i\equiv 0\pmod p\tag{7} \]

has \(n\) solutions if and only if there exist polynomials \(q(x)\), \(r(x)\) with integer coefficients (\(\deg r < n\)) such that

\[ x^p-x=f(x)q(x)+pr(x). \tag{8} \]
Proof

  • Necessity: By polynomial division, there exist polynomials \(q(x)\), \(r_1(x)\) with integer coefficients (\(\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 \(n\) identical solutions. Then by Corollary 3, there exists a polynomial \(r(x)\) with integer coefficients such that \(r_1(x)=pr(x)\), proving the claim.

  • Sufficiency: If equation \((8)\) holds, then by Fermat's Little Theorem, for any integer \(x\),

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

    That is, the equation \(f(x)q(x)\equiv 0\pmod p\) has \(p\) solutions.

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

    Since \(\deg q=p-n\), by Lagrange's Theorem, \(q(x)\equiv 0\pmod p\) has at most \(p-n\) solutions. 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\). Hence, \(s+(p-n)\geq p\), so \(s\geq n\).

    Therefore, \(s=n\).

For non-monic polynomials, since \(\mathbf{Z}_p\) is a field, we can convert them to monic polynomials, making this theorem applicable.

Theorem 6

Let \(n\mid p-1\), \(p\nmid a\). Then the equation

\[ x^n\equiv a\pmod p\tag{9} \]

has a solution if and only if

\[ a^{\frac{p-1}{n}}\equiv 1\pmod p. \]

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

Note

The specific structure of the solution set of equation \((9)\) can be found in k-th Residue.

Proof

  • 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 some polynomial with integer coefficients. Therefore, by Theorem 5, equation \((9)\) has \(n\) solutions.

Methods for Solving Higher-Degree Congruence Equations (Systems)

First, we can use the Chinese Remainder Theorem to transform solving a system of congruence equations into solving congruence equations, and to transform solving a congruence equation modulo a composite \(m\) into solving congruence equations modulo prime powers. Then, using Theorem 1, we reduce solving congruence equations modulo prime powers to solving congruence equations modulo primes.

Combining the theorems for congruence equations modulo primes, we only need to consider solving equations of the form

\[ x^n+\sum_{i=0}^{n-1}a_ix^i\equiv 0\pmod p \]

where \(p\) is prime and \(n<p\).

We can eliminate the \(x^{n-1}\) term by substituting \(x\) with \(x-\dfrac{a_{n-1}}{n}\). Thus, we only need to consider solving equations of the form

\[ x^n+\sum_{i=0}^{n-2}a_ix^i\equiv 0\pmod p\tag{10} \]

where \(p\) is prime and \(n<p\).

References

  1. Congruence Equation -- from Wolfram MathWorld
  2. Lagrange's theorem (number theory) - Wikipedia
  3. Pan Chengdong, Pan Chengbiao. Elementary Number Theory.
  4. Feng Keqin. Elementary Number Theory and Its Applications.
  5. Min Sihe, Yan Shijian. Elementary Number Theory.
本页面最近更新：，更新历史
发现错误？想一起完善？ 在 GitHub 上编辑此页！
本页面贡献者：OI-wiki
本页面的全部内容在 CC BY-SA 4.0 和 SATA 协议之条款下提供，附加条款亦可能应用