Definition:Polynomial Congruence

From ProofWiki
Jump to navigation Jump to search

Definition

Let $\map P x$ be an integral polynomial.


Then the expression:

$\map P x \equiv 0 \pmod n$

is known as a polynomial congruence.


Linear Congruence

A linear congruence is a polynomial congruence of the form:

$a_0 + a_1 x \equiv 0 \pmod n$

That is, one where the degree of the integral polynomial is $1$.


Such a congruence is frequently encountered in the equivalent form:

$a x \equiv b \pmod n$


Solution

A solution of $\map P x \equiv 0 \pmod n$ is a residue class modulo $n$ such that any element of that class satisfies the congruence.


Number of Solutions

Let $S = \set {b_1, b_2, \ldots, b_n}$ be a complete set of residues modulo $n$.

The number of solutions of $\map P x \equiv 0 \pmod n$ is the number of integers $b \in S$ for which $\map P b \equiv 0 \pmod n$.


Also see

  • Results about polynomial congruences can be found here.