Definition:Polynomial Congruence
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.