# Polynomial Long Division over GF(p)

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.

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}$

-
@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. –  Yiannis Lazarides Jun 21 '11 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 Jun 21 '11 at 13:31
@Yannis: The linked question is neither about polynomials nor about arithmetic in finite fields. –  Caramdir Jun 21 '11 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? –  Yiannis Lazarides Jun 21 '11 at 15:04
@Yiannis: Why did you use a mirror in your url? It is potentially shutdown. –  xport Jun 21 '11 at 18:33

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}


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.

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

Based on Leo's answer but I

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

\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}

-
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 Jun 22 '11 at 13:35
@Weaam: I just updated this answer. Please see, all columns have equal width. –  xport Jun 22 '11 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 Jun 22 '11 at 17:43