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