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: 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{displaymath}
\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}\end{displaymath}

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

\begin{displaymath}
\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}\end{displaymath}

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

\begin{displaymath}
\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}\end{displaymath}

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

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

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

$\displaystyle 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

$\displaystyle 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

$\displaystyle 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

\begin{displaymath}
\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).
\end{displaymath}

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

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



david joyner 2008-04-20