MACM 401/MATH 701讲解、辅导Java，Python编程设计、辅导Dropoff box留学生

2019.02.06 - 首页 >> 其他

MACM 401/MATH 701/MATH 819

Assignment 2, Spring 2019.

Michael Monagan

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.

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.

Question 3 (15 marks): The Primitive Euclidean Algorithm

Reference section 2.7

(a) Calculate the content and primitive part of the following polynomial a ∈ 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 r and the pseudo-quotient q of the polynomials

a(x) divided by b(x) below where a, b ∈ Z[y][x].

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

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

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

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 command prem, gcd and divide for the intermediate calculations.

Question 4 (20 marks): Chinese Remaindering and Interpolation

Reference section 5.3, 5.6 and 5.7

(a) By hand, find 0 ≤ u < M where M = 5 × 7 × 9 such that

u ≡ 3 mod 5, u ≡ 1 mod 7, and u ≡ 3 mod 9

using the “mixed radix representation” for u and also the “Lagrange representation”

for u.

(b) By hand, using Newton’s method, find f(x) ∈ Z5[x] such that f(0) = 1, f(1) =

3, f(2) = 4 such that degx f < 3.

2 + 12) and b = (13y + 23)x

2 + (21y 11)x + (11y 13)

be polynomials in Z[y][x]. Compute the product a × b using modular homomorphisms

φpi

then evaluation homomorphisms φy=βj

and φx=αk

so that you end up multiplying

in Zp. The Maple command Eval(a,x=2) mod p can be used to evaluate the polynomial

a(x, y) at x = 2 modulo p. Then use polynomial interpolation and Chinese

remaindering to reconstruct the product in Z[y][x].

First determine how many primes you need and put them in a list. Use P = [23, 29, 31, 39, ...].

Then determine how many evaluation points for x and y you need. Use x = 0, 1, 2, . . .

and y = 0, 1, 2, . . . .

The Maple command for interpolation modulo p is Interp(...) mod p;

The Maple command for Chinese remaindering is chrem(...);

The Maple command for putting the coefficients of a polynomial a in the symmetric

range for Zm is mods(a,m);

Question 5 (10 marks): Recurrence Relations

(a) Solve the recurrence relation T(n) = T(n 1) + 2n with initial value T(1) = 1.

(b) Below is a recursive Maple procedure that has as inputs an array A with n > 0 entries.

Let T(n) be the number of times the comparsion A[i] = x is executed. Write down

a recurrence relation for T(n) and a suitable initial value. You do not need to know

what the procedure is doing to answer this question.

f := proc(A::Array,n::posint)

local i,x,flag1,flag2;

if n=1 then return false; fi;

flag1 := false;

x := A[n];

for i from 1 to n-1 do if A[i] = x then flag1 := true fi; od;

flag2 := f(A,n-1);

return flag1 or flag2;

end;