# Using Division Algorithm on Polynomials in Finite Field

From Ideals, Varieties, and Algorithms - Cox, Little, O'Shea.

Chapter 1, Section 4. Ideals, Exercise 13 (b).

Show that every $f \in \mathbb{F}_{2}[x,y]$ can be written as $f = A(x^2-x) + B(y^2-y) + axy + bx +cy +d$, where $A,B \in \mathbb{F}_{2}[x,y]$ and $a,b,c,d \in \mathbb{F}_{2}$. Hint: Write $f$ in the form $\sum_i p_i(x) y^i$ and use the division algorithm to divide each $p_i$ by $x^2-x$. From this, you can write $f = A(x^2-x) + q_1(y)x +q_2(y)$. Now divide $q_1$ and $q_2$ by $y^2-y$.

Although it is standard, I include for brevity the text's exact statement of the division algorithm they allude to.

Let $k$ be a field and let $g$ be a non zero polynomial in $k[x]$. Then for every $f \in k[x],$ $\exists$! $q,r \in k[x]$ such that
$$f = qg+r,$$ with either $r$ = 0 or deg($r$) < deg($g$).

Algorithm for finding $q,r$:

Input: $f,g$
Output: $q,r$
$q:= 0; r:= f$
WHILE $r \neq 0$ AND LT($g$) divides LT($r$) DO
$\hspace{2cm} q:= q +$LT($r$)/LT($g$)
$\hspace{2cm} r:= r - g($LT($r$)/LT($g$)

My specific questions are:

1) I am not entirely sure I get where the form $f = \sum_i p_i(x) y^i$ came from.

2) Regardless of whether or not I accept the suggested form I am not seeing how to put the monomials from the principal ideal domain through the algorithm to get the desired outcome.

Any assistance appreciated, verbosity is nice. In the case that someone inquires what I have tried, I will upload a photo of the chalkboard to display my fruitless efforts.

• 1) $f(x,y) = \sum_i \sum_j c_{i,j} x^j y^i = \sum_i (\sum_j c_{i,j} x^j) y^i = \sum_i p_i(x) y^i$ – reuns Jun 19 '16 at 5:19
• This makes sense, thank you. Using this I might actually be able to get the $2^{nd}$ part. – Prince M Jun 19 '16 at 5:28
• No such luck. Still looking for a walk through of question 2. – Prince M Jun 19 '16 at 5:40
• I don't get your question 2). And the polynomial division works well in $K[x]$ when $K$ is a field, no problem for writing $p_i(x) = q_i(x) (x^2-x) + r_i(x)$ where $deg(r_i) < deg(x^2-x)$ i.e. $r_i(x) = ax+b$ – reuns Jun 19 '16 at 5:44
• Oh my goodness, I see now. I was horribly misinterpreting what I was being asked to do and overcomplicating it... thanks @user1952009 – Prince M Jun 19 '16 at 5:57