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

	Are you a 5sos fan? By Rylee Minllic Start Quiz
	9 AP 09 Joints MCQ Quiz By OpenStax Start Quiz
©flickr:	Morphology By Jugnu Khan Start Quiz
	15 Biology 15 Genes and Proteins MCQ By OpenStax Start Quiz
©flickr:	Arctic Ease Telemarketing Campaign Quiz By Nicole Duquette Start Quiz
	Socialism Command Economy By Robert Murphy Start Test
©flickr: Steve	C Programming Language By JavaChamp Team Start Quiz
	PE Power Enigeering Safety By Gerr Zen Start Quiz
©flickr: Hey	Anatomy Physiology Final By Joli Julianna Start Test
	Pre-class Online Quiz - Case Control Studies By Mucho Mizinduko Start Quiz