-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)$?.

  • 0
    What is $g,a,b$?2012-07-06
  • 1
    Did you mean $p \equiv q \pmod{g},$ instead of $a \equiv b \pmod{g}?$2012-07-06
  • 0
    A relation other than the one furnished by the congruence?2012-07-06
  • 0
    Your question makes no sense unless you define what is $\,a,b,g(x)\,$ and what their relation to the first polynomials given is.2012-07-06
  • 0
    The ring $F[X]$ is a PID, so Bezout's identity holds. I'm not sure I understand what you mean by a polynomial lattice? Has that got something to do with the congruences you described?2012-07-06
  • 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?