1.1 A brief introduction to computational algebraic geometry (Page 16/20)

The art of the pfug Page 16 / 20

\begin{matrix} f (t) & = a_{n} t^{n} + a_{n - 1} t^{n - 1} + \dots + a_{1} t + a_{0}, and \\ g (t) & = b_{m} t^{m} + b_{m - 1} t^{m - 1} + \dots + b_{1} t + b_{0} \end{matrix}

of degrees $n$ and $m$ respectively, we already know how to determine whether $f$ and $g$ have a common factor: we simply preform Euclid's algorithm on $f$ and $g$ (or, to say the same thing in a rather silly way, we compute a Gröbner basis for the ideal $⟨ f, g ⟩$ ). If the coefficients of $f$ or $g$ were changed, however, we would have to start over with Euclid's algorithm, i.e. we can't just preform Euclid's Algorithm on the general polynomials of degree $n$ and $m$ . It might be useful then if it were possible to write down (for fixed $n$ and $m$ ) a polynomial in the coefficients of $f$ and $g$ which is zero precisely when $f$ and $g$ have a common factor.

In order to do this, we look again at a question we've studied before: given polynomials $f (t)$ and $g (t)$ of degrees $n$ and $m$ respectively and another polynomial $h (t)$ , what are the solutions to the equation

u f + v g = h

for polynomials $u (t)$ and $v (t)$ ? Let us first assume that $f$ and $g$ have no common factors. Then it is possible to solve the equation

\tilde{u} f + \tilde{v} g = 1

and hence we may solve the equation for any polynomial $h$ : certainly $(u_{0}, v_{0}) = (h \tilde{u}, h \tilde{v})$ is a solution. To find all the solutions, we just note that any two solutions must differ from one another by a solution $(c (t), d (t))$ to the equation

c f + d g = 0 .

This equation, however, is much easier to solve: we can rewrite it as $c f = - d g$ and since $f$ and $g$ have no factors in common, this means that the solutions to this equation are $(c, d) = (q g, - q f)$ , The fact that if $f | d g$ and $f$ and $g$ have no common factors, then $f | d$ of course follows from the uniqueness of the factorization of a polynomial into irreducible polynomials, but we can also show it directly. We know from Euclid's Algorithm that we can write

\tilde{u} f + \tilde{v} g = 1,

so that multiplying both sides by

d

yields

d \tilde{u} f + d \tilde{v} g = d .

The term

d \tilde{u} f

is clearly divisible

f

and

d \tilde{v} g

is divisible by

f

since

d g

is. Thus

d

must be divisible by

f

as well. and that the general solution to the original equation is

u_{q} = u_{0} + q g

and

v_{q} = v_{0} - q f

, i.e.

(u_{0} + q g) f + (v_{0} - q f) g = h

parametrized by an arbitrary polynomial $q$ .

If we want to find a solution that minimizes the degree of $v = v_{0} - q f$ , we simply note that there are unique polynomials $q$ and $r$ such that $v_{0} = q f + r$ and $deg r < deg f = n$ by the division algorithm. Thus we see that there is a unique solution to the original equation in which $deg v < n$ . Similarly, it can be shown that there is a unique solution in which $deg u < m$ . Moreover, if $deg h < n + m$ , then these two solutions are the same, since if $deg v < n$ , then $deg v g < n + m$ so $deg u f = deg (h - v g) < n + m$ , and $deg u < m$ as well.

Proposition Let $f, g \in k [t]$ be polynomials over a field $k$ of degrees $n > 0$ and $m > 0$ , respectively. Then for any $h \in k [t]$ of degree less than $n + m$ , there are unique polynomials $u, v \in k [t]$ with $deg u < m$ and $deg v < n$ such that

u f + v g = h

if and only if $f$ and $g$ have no common factors.

We've just shown that if $f$ and $g$ are relatively prime, then the above equation has a unique solution. We are left with the “only if” part: we must show $f$ and $g$ do have a common factor, then either the existence or the uniqueness of the solutions must fail.

In fact, both fail. Existence fails because we can not solve the equation $u f + v g = 1$ , since any common factor of $f$ and $g$ must also divide 1. Uniqueness fails even for $h$ where a solution exists because if $d$ is a common factor of $f$ and $g$ , then $\frac{g}{d} f + \frac{- f}{d} g = 0$ is another solution to $c f + d g = 0$ with $deg u < m$ and $deg v < n$ .

<< Chapter < Page Page > Chapter >>

Read also:

Get Jobilize Job Search Mobile App in your pocket Now!

100% Free Mobile Applications
Receive real-time job alerts and never miss the right job again

Source: OpenStax, The art of the pfug. OpenStax CNX. Jun 05, 2013 Download for free at http://cnx.org/content/col10523/1.34

Google Play and the Google Play logo are trademarks of Google Inc.

Notification Switch

Would you like to follow the 'The art of the pfug' conversation and receive update notifications?

Ask

	39 Biology 39 The Respiratory System MCQ By OpenStax Start Quiz
	19 AP 19 Cardiovascular System Heart MCQ By OpenStax Start Quiz
	2 Muscular System MCQ By Nick Swain Start Quiz
	College physics for ap® courses By OpenStax Read Online Course
	Anatomy & Physiology By OpenStax Read Online Course
	16 AP Key Terms 16 Neurological Exam By OpenStax Start Key Terms
	1 Physiotherapy Flashcards Set 1 By Rhodes Start Flashcards
	23 AP Key Terms 23 The Digestive System By OpenStax Start Key Terms
©flickr: Gareth	Resume Writing MCQ By Abby Sharp Start Quiz
	Anthropology Religion Culture By Richley Crapo Start Assignment