  (Solution) 189-235A: Basic Algebra I Assignment 3 Due: Monday, October 21 1. Perform The Euclidean Algorithm To Nd The Gcd Of F (x) = X4 + 3x3 + 16x2 + 33x + 55... | Snapessays.com

(Solution) 189-235A: Basic Algebra I Assignment 3 Due: Monday, October 21 1. Perform the Euclidean algorithm to nd the gcd of f (x) = x4 + 3x3 + 16x2 + 33x + 55...

8. Let p be a prime and let F denote the field Z/pZ with p elements. let g(x) be a polynomial in F[x]. Show that the gcd (x^(p)-x, g(x)) is a polynomial whose degree is equal to the number of distinct roots of g(x) in F.

9. Use the result of question 8 to show that the polynomial x^(2)+1 has no roots in Z/pZ when p is a prime of the form 3+4m.

10. Use the result of question of 8 to describe a realistic algorithm for computing the number of roots of a polynomial g(x) in F=Z/pZ.

(by realistic we mean that a computer could perform the calculation in a number of seconds for p a prime of around 20 or 30 digits and g a polynomial of degree 10 or so.)189-235A: Basic Algebra I

Assignment 3

Due: Monday, October 21

1.

Perform the Euclidean algorithm to Fnd the gcd of

f

(

x

) =

x

4

+ 3

x

3

+

16

x

2

+ 33

x

+ 55 and

g

(

x

) =

x

3

+

x

2

-

x

-

10 in the polynomial ring

Q

[

x

].

Write this greatest common divisor as a linear combination of

f

(

x

) and

g

(

x

)

with coe±cients in

Q

[

x

].

2.

Same question as 1, with

f

(

x

) =

x

6

+

x

4

+

x

+ 1 and

g

(

x

) =

x

6

+

x

5

+

x

4

+

x

3

+

x

2

+

x

+ 1 in

Z

/

2

Z

[

x

].

3. List all the irreducible polynomials of degree 4 in

Z

/

2

Z

[

x

].

4.

If

p

is an odd prime of the form 1 + 4

m

, use Wilson’s Theorem to show

that

a

= (2

m

)! is a root in

Z

/p

Z

of the polynomial

x

2

+ 1 in

Z

/p

Z

[

x

].

5.

In class, we showed that a polynomial of degree

d

with coe±cients in a

Feld

F

has at most

d

roots. Show that this statement ceases to be true when

F

is replaced by an arbitrary ring, such as the ring

Z

/n

Z

of residue classes

modulo

n

with

n

a composite integer.

6.

Let

d

be a Fxed integer.

Let

n

=

pq

?

Z

be an integer which is a

product of two distinct primes,

p

and

q

, and let

f

?

Z

/n

Z

[

x

] be a monic

polynomial with coe±cients in

Z

/n

Z

of degree

d

.

Give a “best possible”

general upper bound (as a function of

d

) for the number of distinct roots

that such a polynomial could have over

Z

/n

Z

, and show with an example

that your estimate is indeed best possible.

(I.e., describe a judicious choice

of

f

having the maximal number of distinct roots.)

7.

Write down the powers of

x

in the ring

Z

/

2

Z

[

x

]

/

(

x

3

+

x

+ 1) and show

that every non-zero element in this ring can be expressed as a power of

x

.

1

Solution details:
STATUS
QUALITY
Approved

This question was answered on: May 23, 2022 Solution~00021147603011.zip (25.37 KB)

This attachment is locked

Our expert Writers have done this assignment before, you can reorder for a fresh, original and plagiarism-free copy and it will be redone much faster (Deadline assured. Flexible pricing. TurnItIn Report provided)

STATUS

QUALITY

Approved

May 23, 2022

EXPERT

Tutor