# Question about polynomials and congruences

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

-
What is $g,a,b$? –  Generic Human Jul 6 '12 at 16:19
Did you mean $p \equiv q \pmod{g},$ instead of $a \equiv b \pmod{g}?$ –  user2468 Jul 6 '12 at 16:35
A relation other than the one furnished by the congruence? –  rschwieb Jul 6 '12 at 16:50
Your question makes no sense unless you define what is $\,a,b,g(x)\,$ and what their relation to the first polynomials given is. –  DonAntonio Jul 6 '12 at 16:57
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. –  Jyrki Lahtonen Jul 6 '12 at 18:32

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?