1. ## Polynomial help!!

I've been given this question as homework and i dont really understand the steps/how to work it out!! it is...

Two integers are said to be relatively prime if their highest common factor is 1. If 'a' and 'b' are relatively prime it is possible to find integer 'x' and 'y' such that ax + by = 1.

For example... 51 and 44 are relatively prime.

Repeated use of the division identity leads to:

51 = 44 x 1 + 7
44 = 7 x 6 + 2
7 = 3 x 2 + 1

1 = 7 - 3 x 2
= 7 - 3(44 - 7 x 6)
= 19 x 7 - 3 x 44
= 19(51 - 44 x 1) - 3 x 44
= 19 x 51 - 22 x 44

question...

a) use this method to find integers 'a' and 'b' such that 87a + 19b = 1.

b) using the method, find the polynomials, A(x) and B(x) such that:
A(x)(x(squared) - x) + B(x)(x(power of 4) + 4x(squared) - 4x + 4) = 1

it's mainly the part in bold that i dont really get but i also dont know how to find the answer!!

thanks tons!!

2. Division with remainders?

1) 87/19 = 4 R 11 so 87 = 19*4 + 11 We're done with 87, but 19 and 11 moves on.

2) 19/11 = 1 R 8 so 19 = 11*1 + 8 We're done with 19, but 11 and 8 move on.

3) 11/8 = 1 R 3 so 11 = 8*1 + 3 We're done with 11, but 8 and 3 move on.

4) 8/3 = 2 R 2 so 8 = 3*2 + 2 We're done with 8, but 3 and 2 move on.

5) 3/2 = 1 R 1 so 3 = 2*1 + 1 Whew!! We finally found a 1!

Now backwards. I'll let you do it, but with one hint. RESIST the temptation to simplify as you go. You may want to do a couple of things, but remember that the point of the exercise is to UNsimplify the expression.

It shouldn't be too different for the polynomials.

3. thanks for that... but how would i do part b??? i cant really see how to use the same pattern...

thanks again!!

4. It's only slightly more complicated. Remember that we use generally a "Base 10 Positional System", $\displaystyle 1423 = 1*10^{3} + 4*10^{2} + 2*10^{1} + 3$. If you think of the polynomials as a "Base 'x' Positional System" you are on your way. The ONLY significant complication is that you can get negative coefficients. You can't do that with non-polynomial constructs. 1(-4)23 would look pretty weird, but it DOES work that way, sort of, in Roman Numerals. "VL" is 45 -- That "V" is a negative value when it appears out of descending order. Just move on with long divisions as let's see what you get.

5. Originally Posted by sir nerdalot

For example... 51 and 44 are relatively prime.

Repeated use of the division identity leads to:

51 = 44 x 1 + 7
44 = 7 x 6 + 2
7 = 3 x 2 + 1

1 = 7 - 3 x 2
= 7 - 3(44 - 7 x 6)
= 19 x 7 - 3 x 44
= 19(51 - 44 x 1) - 3 x 44
= 19 x 51 - 22 x 44

question...

a) use this method to find integers 'a' and 'b' such that 87a + 19b = 1.

b) using the method, find the polynomials, A(x) and B(x) such that:
A(x)(x(squared) - x) + B(x)(x(power of 4) + 4x(squared) - 4x + 4) = 1
Originally Posted by sir nerdalot
thanks for that... but how would i do part b??? i cant really see how to use the same pattern...
It's "simple" (but ugly to write out)

You start by taking $\displaystyle x^2 - x$ and $\displaystyle x^4 + 4x^2 - 4x + 4$

So:
$\displaystyle x^4 + 4x^2 - 4x + 4 = (x^2 - x)(x^2 + x + 5) + (x + 4)$

$\displaystyle x^2 - x = (x + 4)(x - 5) + 20$

Now, in the problem with the integers we wanted a problem that ended with a 1. For the polynomials we want a problem that ends with an 0th degree polynomial, such as 20. So we are done here.

Now reverse the process:
$\displaystyle 20 = (x^2 - x) - (x + 4)(x - 5)$

$\displaystyle 20 = (x^2 - x) - ([(x^4 + 4x^2 - 4x + 4) - (x^2 - x)(x^2 + x + 5)])(x - 5)$

Expand:
$\displaystyle 20 = (x^2 - x) - (x^4 + 4x^2 - 4x + 4)(x - 5) + (x^2 - x)(x^2 + x + 5)(x - 5)$

Collect terms:
$\displaystyle 20 = (x^2 - x)[1 + (x^2 + x + 5)(x - 5)] - (x^4 + 4x^2 - 4x + 4)(x - 5)$

$\displaystyle 20 = (x^2 - x)(x^3 - 4x^2 - 24) + (x^4 + 4x^2 - 4x + 4)(-x + 5)$<-- We are supposed to be adding the last term, so I changed the sign on the last polynomial.

We almost have what we wanted. We wanted the RHS to equal 1. But hey, all we need to do now is divide both sides by 20:
$\displaystyle 1 = (x^2 - x)\left ( \frac{1}{20}x^3 - \frac{1}{5}x^2 - \frac{6}{5} \right ) + (x^4 + 4x^2 - 4x + 4) \left ( -\frac{1}{20}x + \frac{1}{4} \right )$

Voila! It's exactly the same problem as with the integers done by exactly the same method. (Compare them.) It's just that the "book-keeping" is a tad messier.

-Dan