Extended Euclidean Algorithm

Extended Euclidean Algorithm for $d(x)=\gcd (a(x),b(x))=a(x)p(x)+b(x)q(x)$ for $0\leq deg(b(x))<deg(a(x))$ .

(a)

let $\overline{u}= \langle a(x),1,0\rangle$

(b)

let $\overline{v}=\langle b(x),0,1\rangle$

(c)

Repeat:

• let $\overline{w}= \overline{u}-quo( u_{1},v_{1}) \overline{v}$ ,
• let $\overline{u}= \overline{v}$ ,
• let $\overline{v}= \overline{w}$ ,

while $v_{1}\neq 0$

(d)

let $d(x)=u_1$ , $p(x)=u_{2}$ , $q(x)= u_{3}$

(e)

return $d(x),p(x),q(x)$ .

The repeat loop in step (c) means to continue every step until you see $v_1=0$ . This algorithm does not always yield a monic polynomial for $d(x)$ (the gcd is always monic), so it doesn't always yield the correct answer. However, the polynomial $d(x)$ it produces is a constant times the correct gcd.

Example 2.2.19   Let $a(x)=(x+1)(3x^3+1)$ , $b(x)=(x+1)(x^2+1)$ , so $gcd(a(x),b(x))=x+1$ . We have

$$\begin{array}{c} u=[\left (x+1\right )\left (3 {x}^{3}+1\ri... ...}+1\right ),0,1],\\ w=[1-2 x-3 {x}^{2},1,-3 x], \end{array}$$

since $quo(a,b)=3x$ . We have

$$\begin{array}{c} u=[\left (x+1\right )\left ({x}^{2}+1\right... ...}}+{\frac {10}{9}} x,x/3 +1/9, -{x}^{2}-x/3 +1], \end{array}$$

since $quo(\left (x+1\right )\left ({x}^{2}+1\right ), 1-2 x-3 {x}^{2})=-x/3-1/9$ . We have

$$\begin{array}{c} u=[1-2 x-3 {x}^{2},1,-3 x],\\ v=[{\frac... ...10}}, -{\frac {27}{10}} {x}^{3} -{\frac {9}{10}}], \end{array}$$

since $quo(1-2 x-3 {x}^{2}, {\frac {10}{9}}+{\frac {10}{9}} x) =(-27x/10+9/10)$ . We have

$$\begin{array}{c} u=[{\frac {10}{9}}+{\frac {10}{9}} x,x/3 ... ...10}}, -{\frac {27}{10}} {x}^{3} -{\frac {9}{10}}]. \end{array}$$

We can stop now since $v_1=0$ . We read off $p(x)=x/3+1/9$ , $q(x)=-{x}^{2}-x/3+1$ , $d(x)={\frac {10}{9}}+{\frac {10}{9}} x$ (which must be multiplied by $9/10$ to make it monic).

Exercise 2.2.20   Let $F=\mathbb{Z}/p\mathbb{Z}$ denote the field having $p$ elements and let $f(x)=x^p-x\in F[x]$ . Show that for all $x\in F$ , $f(x)=0$ . (Hint: Use Fermat's Little Theorem.)

Exercise 2.2.21   Let $F$ be a field and let $F(x)$ denote the set of all rational functions (i.e., expressions of the form ${p(x)\over q(x)}$ where $p(x),q(x)\in F[x]$ and $q(x)\not= 0$ ). Show that $F(x)$ is a field.

Exercise 2.2.22   Let $F=\mathbb{F}_5$ and let $f(x)=2^x$ , so $f:F\rightarrow F$ . Use the interpolation formula to find a polynomial representation of $f$ .

Exercise 2.2.23   Use the extended Euclidean algorithm to find the gcd $d(x)$ of $a(x)=x^2-1$ and $b(x)=x^3-1$ in $\mathbb{Q}[x]$ . Also, find $u(x),v(x)$ such that

$$u(x)(x^2-1)+v(x)(x^3-1)=d(x).$$

Exercise 2.2.24   Use the extended Euclidean algorithm to find the gcd $d(x)$ of $a(x)=x^3-1$ and $b(x)=x^4-1$ in $\mathbb{F}_5 [x]$ . Also, find $u(x),v(x)$ such that

$$u(x)(x^3-1)+v(x)(x^4-1)=d(x).$$

Exercise 2.2.25   Use the extended Euclidean algorithm to find the gcd $d(x)$ of $a(x)=x^3-1$ and $b(x)=x^4-1$ in $\mathbb{F}_5 [x]$ . Also, find $u(x),v(x)$ such that

$$u(x)(x^3-1)+v(x)(x^4-1)=d(x).$$

Exercise 2.2.26   Show that $p(x)=x^2-2$ has no roots in $F={\mathbb{F}}_3$ .

Exercise 2.2.27   Show that $p(x)=x^2+1$ has no roots in $F={\mathbb{F}}_3$ .

Exercise 2.2.28   Show that $p(x)=x^2+1$ has two roots in $F={\mathbb{F}}_5$ (namely, $\overline{2}$ and $\overline{3}$ ).

Exercise 2.2.29   Show that $p(x)=x^3-x$ has $6$ roots in $\mathbb{Z}/6 \mathbb{Z}$ .

Exercise 2.2.30   Show that $p(x)=x^3-x$ has $3$ roots in ${\mathbb{F}}_3$ .

Exercise 2.2.31   Show that $p(x)=x^{p-1}-1$ has $p-1$ roots in $\mathbb{Z}/p\mathbb{Z}$ . (This is a restatement of Fermat's little theorem.)

Exercise 2.2.32   Let $p(x)=x^2+1$ in $R[x]$ , where $R=\mathbb{Z}/4\mathbb{Z}$ .

(a) Let $c=1$ . Find $q(x)$ satisfying Lemma 2.2.5.

(b) Find all roots of $p(x)$ in $R$ .

Exercise 2.2.33   Let $p(x)=x^2-1$ in $R[x]$ , where $R=\mathbb{Z}/6\mathbb{Z}$ .

(a) Let $c=1$ . Find $q(x)$ satisfying Lemma 2.2.5.

(b) Find all roots of $p(x)$ in $R$ .

Exercise 2.2.34   Let $p(x)=x^4+4$ in $F[x]$ , where $F=\mathbb{F}_5$ .

(a) Let $c=1$ . Find $q(x)$ satisfying Lemma 2.2.5.

(b) Find all roots of $p(x)$ in $F$ .

Exercise 2.2.35   Use the Euclidean algorithm to compute the gcd of $a(x)=x^2-1$ and $b(x)=x^3-1$ in $\mathbb{Q}[x]$ .

Exercise 2.2.36   Use the Euclidean algorithm to compute the gcd of $a(x)=x^3-1$ and $b(x)=x^4-1$ in $\mathbb{F}_5 [x]$ .

Exercise 2.2.37   Use the Euclidean algorithm to compute the gcd of $a(x)=x^3-1$ and $b(x)=x^4-1$ in $\mathbb{Q}[x]$ .

Exercise 2.2.38   Prove Theorem 2.2.15. (Hint: Modify the proof of 1.4.3.)

Exercise 2.2.39   Carry out each step of the ``reformulated'' Euclidean algorithm for $a(x)=x^2-1$ and $b(x)=x^3-1$ in $\mathbb{Q}[x]$ . Verify

$$\det \left( \begin{array}{cc} u_k(x) & r_k(x)\\ u_{k+1}(x) & r_{k+1}(x) \end{array}\right) =(-1)^{k+1}a(x).$$

Exercise 2.2.40   Use the ``reformulated'' Euclidean algorithm to compute the gcd $d(x)$ of $a(x)=x^2-1$ and $b(x)=x^3-1$ in $\mathbb{Q}[x]$ and $u(x),v(x)$ such that

$$u(x)(x^2-1)+v(x)(x^3-1)=d(x).$$