Due Monday February 6th at 11pm. For problems involving Maple calculations and Maple programming, you should export your work to a .pdf file. Late Penalty:  -20% for up to 24 hours late. Zero after that.

Question 1 (15 marks): The Extended Euclidean Algorithm

Given a, b e E, a Euclidean domain, the extended Euclidean algorithm solves sa + tb = g for s, t e E and g = gcd(a, b). More generally, for k = 0, 1, ..., n, n+1 it computes (rk , sk , tk ) e E3 where r0  = a, r1  = b, rn+1  = 0 and sk a + tk b = rk  for 0 < k < n + 1.

(a) For integers a = 99, b = 28 execute the extended Euclidean algorithm by hand.  Use the tabular method presented in class that shows the values for rk , sk , tk , qk .  Identify b − 1    mod a.

(b) Program the extended Euclidean algorithm for Q[x] in Maple.  The input is two non-

zero polynomials a, b e Q[x].  The output is three polynomials (s, t, g) where g is the monic gcd of a and b and sa + tb = g holds.

Please print out the values of (rk , sk , tk ) that are computed after each division step so that we can observe the exponential growth in the size of the rational coefficients of the rk , sk , tk  polynomials.

Use the Maple commands quo(a,b,x) and/or rem(a,b,x) to compute the quotient and remainder of a divided b in Q[x]. Remember, in Maple, you must explicitly expand

products of polynomials using the expand( . . .) command.

Execute your Maple code on the following inputs.

>  a  :=  expand((x+1)*(2*x^4-3*x^3+5*x^2+3*x-1));

> b  :=  expand((x+1)*(7*x^4+5*x^3-12*x^2-x+4));

Check that your output satisfies sa + tb = g and check that your result agrees with Maple’s g  := gcdex(a,b,x,’s’,’t’); command.

(c)  Consider a(x) = x3 - 1, b(x) = x2 + 1, and c(x) = x2 . Apply the algorithm in the proof of Theorem 2.6 (as presented in class) to solve the polynomial diophantine equation σa + τ b = c for σ, τ e Q[x] satisfying deg σ < deg b - deg g where g is the monic gcd of a and b. Use Maple’s g  := gcdex(a,b,x,’s’,’t’); command to solve sa + tb = g for s, t e Q[x] or use your code from part (b).

Question 2 (15 marks): Multivariate Polynomials

(a)  Consider the polynomial

A = 3 + 4y5 + 7x3 z + 5x2y2 z2 + 9x2y3 + 6xy2 z .

Write A in graded lexicographical order with x > y > z .

Write A in pure lexicographical order with x > y > z .

Write A in pure lexicographical order with y > x > z .

For each case write down lc(A), lm(A) and lt(A).

See the MultiPolyDefinitions handout for lecture 6.

(b)  Consider the polynomials

A = 6 y2 x3 + 2 x2y2 + 5 yx2 + 3 xy2 + yx + y2 + x + y  and  B = 2 yx2 + x + y .

You are to divide the polynomials A by B over z. Write A e z[y][x] and test if B|A by doing the division in z[y][x] by hand.  If B|A determine the quotient Q of A ÷ B .

Note, the quotient must be a polynomial in z[y][x]. Show your working. Repeat the calculation using

A = 6 y2 x3 + 2 x2y2 + 6 yx2 + 3 xy2 + yx + y2 + x + y Check your answers using Maple’s divide command.

Question 3 (15 marks): The Primitive Euclidean Algorithm

Reference section 2.7

(a)  Calculate the content and primitive part of the following polynomial a e z[x, y], first as a polynomial in z[y][x] and then as a polynomial in z[x][y], i.e., first with x the main variable then with y the main variable. Use the Maple command gcd to calculate

the GCD of the coefficients. The coeff command will be useful.            >  a  :=  expand(  (x^4-3*x^3*y-x^2-y)*(8*x-4*y+12)*(2*y^2-2)  );

(b) By hand, calculate the pseudo-remainder  and the pseudo-quotient q˜ of the polyno- mials a(x) divided by b(x) below where a, b e z[y][x].

>  a  := 3*x^3+(y+1)*x;

> b  :=  (2*y)*x^2+2*x+y;

Now compute  and q˜ using Maple’s prem command to check your work.

(c)  Given the following polynomials a, b e z[x, y], calculate the GCD(a, b) using the prim- itive Euclidean algorithm with x the main variable.

>  a  :=  expand(  (x^4-3*x^3*y-x^2-y)*(2*x-y+3)*(8*y^2-8)  );

> b  :=  expand(  (x^3*y^2+x^3+x^2+3*x+y)*(2*x-y+3)*(12*y^3-12)  );               You may use the Maple commands prem, gcd and divide for intermediate calculations.