-1
$\begingroup$

Let be $m(X), n(X), a(X), b(X), m(X), n(X), g(X) \in F[X]$ a polynomials, where $F$ is a finite field with characteristic 2. Let be a relations $a \equiv b \mod g(X)$ and $m \equiv n \mod g(X)$. Are there any relation, property, etc, between $a(X), b(X), m(X), n(X)$?.

  • 1
    I am gambling that the OP has problems understanding the meaning of congruence in a polynomial ring as well as problems with the English language.2012-07-06

1 Answers 1

1

Let $F=\mathbb{F}_2$. The congruence $ p(X)\equiv q(X)\pmod{g(X)} $ means simply that there exists a polynomial $r(X)\in F[X]$ such that $ p(X)-q(X)=r(X) g(X). $ For example we can say that $ X^8\equiv X \pmod{X^3+X+1}, $ because $ X^8-X=X(X^7-1)=X(X-1)(X^3+X^2+1)(X^3+X+1), $ (as an exercise check that the product on the right hand side is what I claim it to be) so $r(X)=X(X-1)(X^3+X^2+1)$ works. Note that this is exactly analogous to the definition of congruence of integers: $a\equiv b \pmod{n}$ means that $a-b=rn$ for some integer $r$.

The ring $F[X]$ is a PID meaning that in their concepts like "greatest common divisor", "factorization into products of primes irreducible polynomials" and "Bezout's identity" make sense. As an example I claim here that the two polynomials that appeared, $a(X)=X^3+X^2+1$ and $b(X)=X^3+X+1$, have no common factors. IOW $\gcd(a(X),b(X))=1$. This follows because they are both irreducible: an eventual factorization would include a linear factor, but such a fact cannot exist, because then $a$ or $b$ would have a zero in $F$. Bezout the commands me to produce polynomials $u,v\in F[X]$ such that the identity $ ua+bv=1 $ is true. As is always the case in Bezout's identity, the left hand side will be divisible by any common factor of $a$ and $b$, so that common factor will also be a factor of the right hand side - here 1. A little bit of tinkering (we can run the generalized Euclidean algorithm here, if we can't do without) shows us that $ (X+1)a+(X)b=(X^4+X^2+X+1)+(X^4+X^2+X)=1, $ so the choices $u=X+1$ and $v=X$ work.

So this hopefully gives you an idea what congruence and Bezout's identity mean in the ring $F[X]$. Is that what you really wanted to ask? Also, why did you include the coding-theory -tag? What did you mean by lattices here?