Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

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

share|cite|improve this question
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
up vote 1 down vote accepted

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?

share|cite|improve this answer

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.