Verified answer

1.By induction:

We write x^n+x+1=(x^2+1)Qn+Rn for any integer n≧2

After some tries we can conjecture that Rn=x when n even and Rn=1 when n odd.

Now we prove it by induction.

x^(n+1)+x+1=x(x^n+x+1)-x^2+1

=x((x^2+1)Qn+Rn)-(x^2+1) cause -1=1 over Z2

=(x^2+1)(xQn-1)+xRn

Then you can finish the induction.

So we've proved that

Rn=x when n even.

2.First, we list all quadratic polynomials over Z3, there are 2*3*3=18 (2 choices for the coefficient in front of x^2, 3 for x, 3 for the constant)

Then we observe that all polynomials whose leading coefficient is 2 can be written as a polynomial whose leading coefficient is 1 multiplied by 2 (cause Z3 is a group, every number is invertible). For example we can write 2x^2+x+1 as 2(x^2+2x+2).

So we've reduced the number into 3*3=9.

Then we write all the factorization possible over Z3. They are:

x*x, x*(x+1), x(x+2), (x+1)(x+1), (x+1)(x+2), (x+2)(x+2).

Finally we delete these polynomials from the list. And we get the answer:

x^2+1, x^2+x+2, x^2+2x+2