9

Is there a package like polynom for typesetting polynomial long division but over a finite field such as GF(2). If not, how to manually typeset long division in general?

Thanks.

Addendum:

I attempted the following solution! However, the vertical spacing between each line and exponents of the equation below it is quite small, how to increase it? I tried \vspace but received errors. Thanks.

\[
\begin{array}{m{3.5em}ccccccccc}
&    &    &    &    &+x^4&+x^3&    &  &+1\\
\cline{2-10}
\multicolumn{2}{l}{x^3+x+1\big)}
     &+x^7&+x^6&+x^5&    &    &+x^2&+x&  \\
&    &+x^7&    &+x^5&+x^4&    &    &  &  \\
\cline{3-6}
&    &    &+x^6&    &+x^4&    &    &  &  \\
&    &    &+x^6&    &+x^4&+x^3&    &  &  \\
\cline{4-7}
&    &    &    &    &    &+x^3&+x^2&+x&  \\
&    &    &    &    &    &+x^3&    &+x&+1\\
\cline{7-10}
&    &    &    &    &    &    &+x^2&  &+1\\
\end{array}
\]
Improve this question
7
  • @Weaam Please see tex.stackexchange.com/questions/14634/decimal-long-division. If this answers your question please add a comment so that this post can be treated as duplicate and redirect future users to the correct page.
    – yannisl
    Commented Jun 21, 2011 at 13:11
  • @Yiannis: Thank you, but I don't see how it is relevant. I also checked the documentation for the xlop package but I couldn't see how it is of any use here. If it were useful, then a non-trivial explanation is needed!
    – Weaam
    Commented Jun 21, 2011 at 13:31
  • 1
    @Yannis: The linked question is neither about polynomials nor about arithmetic in finite fields.
    – Caramdir
    Commented Jun 21, 2011 at 13:31
  • @Weaam @Caramdir Sorry! Read the question too quickly. Try this kambing.ui.ac.id/ctan/macros/latex/contrib/polynom/polynom.pdf. Can you post an image or a link with an example of what you want to typeset?
    – yannisl
    Commented Jun 21, 2011 at 15:04
  • 1
    @Yiannis: Why did you use a mirror in your url? It is potentially shutdown.
    – Display Name
    Commented Jun 21, 2011 at 18:33

2 Answers 2

Reset to default
7

I'm afraid there isn't such a package to do calculations over finite fields. Arithmetic over finite fields GF(p^n) may be too complex for TeX. GF(2) and GF(p) are much easier, but there seems no such a package either.

To typeset long division manually, you can simply use an array. For example:

\documentclass{article}
\usepackage{amssymb}

\begin{document}

\[
x^3 - x + 1 = (x-1)(x^2+x) + 1 \in \mathbb{F}_3[x]
\]

\[
\renewcommand\arraystretch{1.2}
\begin{array}{*2r @{\hskip\arraycolsep}c@{\hskip\arraycolsep} *4r}
  &    &&    &  1 &  1 & 0 \\
\cline{3-7}
1 & -1 &\big)& 1 &  0 & -1 & 1 \\
  &    &&  1 & -1 \\
\cline{4-6}
  &    &&    &  1 & -1 \\
  &    &&    &  1 & -1 \\
\cline{5-7}
  &    &&    &    &    & 1 \\
\end{array}
\]

\end{document}

enter image description here

If you need a lot of these long divisions, it is worth to write a program (not necessarily in TeX) to generate the code. It's not very difficult for polynomials over GF(p).

For edited question:

To increase the vertical space between array lines, you can redefine the factor \arraystretch as showed above. Or you can use makecell package to add a gap.

Improve this answer
4
  • Can we change \big) to a vertical line that perfectly touches the horizontal line?
    – Display Name
    Commented Jun 21, 2011 at 18:42
  • @xport: Yes, you can use \vline here. And \Big) is also better.
    – Leo Liu
    Commented Jun 22, 2011 at 3:59
  • +1 @Leo: one more, how to make the width of all columns equal?
    – Display Name
    Commented Jun 22, 2011 at 5:38
  • 1
    @xport: Use p{1cm}, tabularx's X, or \makebox[1cm]{...}, or any other method.
    – Leo Liu
    Commented Jun 22, 2011 at 14:27
2

Based on Leo's answer but I

  • removed one column.
  • replaced the \big) with a vertical rule.
  • made all rows have equal width.

enter image description here

\documentclass{article}
\usepackage{amssymb}
\usepackage{array}

\newcommand{\x}[1]{\multicolumn{1}{|r}{#1}}

\begin{document}

\[
x^3 - x + 1 = (x-1)(x^2+x) + 1 \in \mathbb{F}_3[x]
\]

\[
\renewcommand\arraystretch{1.2}% specify the vertical stretch
\begin{array}{*{6}{>{\hfill}m{7mm}}}%specify the column width
&
    &
        &
            1&
                1&
                    0\\\cline{3-6}
1&
    -1&
        \x{1}&
                0&
                    -1&
                        1\\
&
    & 
        1&
            -1&
                &
                    \\\cline{3-5}
&
    &
        &
            1&
                -1&
                    \\
&
    &
        &
            1&
                -1&
                    \\\cline{4-6}
&
    &
        &
            &
                &
                    1\\
\end{array}
\]

\end{document}
Improve this answer
4
  • This is quite useful, I was wondering about how to do that too. I think if using ")" showed inconsistencies, I'll follow this convention. Thank you.
    – Weaam
    Commented Jun 22, 2011 at 13:35
  • 1
    @Weaam: I just updated this answer. Please see, all columns have equal width.
    – Display Name
    Commented Jun 22, 2011 at 13:50
  • Great. But I must work with variable (a matter of convention) and therefor I wouldn't consider setting all columns with equal width. Thanks again, truly appreciate it!
    – Weaam
    Commented Jun 22, 2011 at 17:43
  • @xport as per your suggestion, all minus symbols are changed to hyphen character, is it possible to fix?
    – MadyYuvi
    Commented Apr 4, 2018 at 6:26

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .