Re: Math question [polynomial division]

From: Tom St Denis (tomstdenis_at_iahu.ca)
Date: 12/30/03 

Date: Tue, 30 Dec 2003 19:43:14 GMT

"Marcel Martin" <mm@ellipsa.no.sp.am.net> wrote in message
news:3FF1CB37.B7CD45EB@ellipsa.no.sp.am.net...
> When multiplying the intermediate remainders, one must also multiply
> the intermediate quotients (assuming the final quotient is wanted).

One more lingering question...

In the case of our answer there

Q = 21x + 1
R = 40

What would be the point of this? Obvious the GCD over Z[x] is 1 since the
factors of the dividend are (x+1)(3x + 1) neither of which are a multiple[or
divisor] of 7x + 9

If we used the trivial algorithm, e.g.

A = 3x^2 + 4x + 1
B = 7x + 9

while (B > 0) {
    r = A mod B
    A = B
    B = r
}

we get

1. r = A mod B = 40, A = B, A = 7x + 9, B = r, B = 40

(7x + 9)/40 ...

So multiply A by 40 to get 280x + 360, subtract 7x*40 to get 360, which
divides nicely to 9, remainder zero.

2. r = A mod B = 0, A = B, A = 40, B = r, B = 0

3. Terminate, return A

so the GCD of the two is apparently 40?

But over Z[x] 40 doesn't divide either!!

Obviously I'm missing something [like say an undergrad education, ba da dum,
rimshot!] but I'd say the GCD really ought to be 1.

Tom