Hello, dear friend, you can consult us at any time if you have any questions, add WeChat: THEend8_
Assignment
Due Monday February 4th at 4pm. Please hand in to Dropoff box 1b outside AQ 4100
Late Penalty: 20% for up to 48 hours late. Zero after that.
For problems involving Maple calculations and Maple programming, you should submit a
printout of a Maple worksheet of your Maple session.
Question 1 (15 marks): Univariate Polynomials
Reference section 2.5.
(a) Program the extended Euclidean algorithm for Q[x] in Maple. The input is two nonzero
polynomials a, b ∈ 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 at each division step so
that we can observe the exponential growth in the size of the rational coefficients 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-2*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.
(b) 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 σ, τ ∈ 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 ∈ Q[x] or your algorithm from part (a) above.
1
Question 2 (15 marks): Multivariate Polynomial Division
(a) Consider the polynomials
A = 6 y2x
2 + 5 yx2 + 3 xy2 + yx + y
2 + x + y and B = 2 yx2 + x + y.
Write A ∈ Z[y][x] and test if B|A by doing the division in Z[y][x] by hand. Show your
working. If B|A determine the quotient Q of A ÷ B. Check your answer using Maple’s
divide command.
(b) Given two polynomials A, B ∈ Z[x1, x2, . . . , xn] with B 6= 0, give pseudo code for the
multivariate division algorithm for dividing A by B. The pseudo code should begin
like this
Algorithm DIVIDE(A,B)
Inputs A, B ∈ Z[x1, x2, . . . , xn] satisfying B 6= 0 and n ≥ 0.
Output Q ∈ Z[x1, x2, . . . , xn] s.t. A = BQ or FAIL meaning B does not divide A.
I suggest you start with my pseudo code for the division algorithm in F[x] and modify
it to work in D[x1] where D = Z[x2, . . . , xn]. The algorithm will make a recursive call
to divide the leading coefficients in D. Because the algorithm is recursive you need a
base of the recursion.