Question

How many distinct congruence classes are there modulo ${\mathit{x}}^{\mathbf{3}}\mathbf{+}\mathit{x}\mathbf{+}\mathbf{1}\mathbf{}\mathit{i}\mathit{n}\mathbf{}{\mathbf{\mathbb{Z}}}_{\mathbf{2}}\left[x\right]$a ? List them.

Short answer

There are eight congruence classes.

Step-by-step solution

Corollary statement

Assume that p (x) is a non-zero polynomial of degree n in F [x] and that congruence modulo p (x).

1. When f(x) is divided by p (x), we have $\left[f\left[x\right]\right]=\left[r\left(x\right)\right]$,where r (x) is the remainder and $f\left(x\right)\in F\left[x\right]$.
2. Let S be the set of all polynomials whose degrees are less than the degree of p (x), then each congruence class modulo p (x) is also the class of some polynomial in S, where each class is distinct.

Proof part

The given expression is $x^3+x+1in{\mathrm{\mathbb{Z}}}_2\left[\mathrm{x}\right]$.

Here, n is 3, which is a prime.

There can be eight congruence classes as per the stated corollary in step 1.

So, the eight congruence classes can be:

$0,1,x,x+1,x^2,x^2+1,x^2+x,x^2+x+1$

Hence, there are eight congruence classes.