<s>[INST] What is the remainder on division of $z^{400} + z^{303} + 1$ by $z^4-1$? I am asked to determine the remainder when the polynomial $f(z)=z^{400}+z^{303}+1$ is divided by the polynomial $g(z)=z^4-1$.
I expressed f as $f(z) = h(z)(z^4-1) + r(z)$ where $r(z)$ is a polynomial
Realising that $z^4-1 = (z^2-1)(z^2+1) = (z-1)(z+1)(z^2+1)$, I expressed f as 
$f(z) = h(z)(z-1)(z+1)(z^2+1) + r(z)$
I also wrote f as $f(z) = q(z)(z-1) + 3$, since $f(1)=3$, and q is some polynomial.
So I had $f(z)= q(z)(z-1) + 3 = h(z)(z-1)(z+1)(z^2+1) + r(z)$
Hence, for some constant k, $q(z)=h(z)(z+1)(z^2+1) + k$
We know $f(-1) = 1$
From $f(z) = q(z)(z-1) + 3$, we have $f(-1)=q(-1)(-2) + 3 = 1$, which implies
$q(-1) = 1$.
Then $q(-1)=h(-1)(0) + k = 1$. Thus, $k=1$
We then have $q(z)=h(z)(z+1)(z^2+1) + 1$, and from this, we have
$f(z)= q(z)(z-1) + 3 = (h(z)(z+1)(z^2+1) + 1)(z-1) + 3$
Which simplifies to $f(z) = h(z)(z^4-1) + z+2$
And gives $r(z) =z+2$.
But I am given the answer is $r(z) = z^3+ 2$. What is going wrong here? Can I use modular arithmetic instead? How?
 [/INST] Note that we can write $f(z)=h(z)(z^4-1)+r(z)$ where $r(z)$ is a polynomial of degree at most three (one less than the degree of $z^4-1$).
An unknown polynomial of degree $3$ has four coefficients to be determined. If we successively use $z=1, z=-1, z=i, z=-i$ - the four roots of $z^4-1$ the term involving $h(z)$ will vanish.
This gives us $f(1)=r(1)=3$, $f(-1)=r(-1)=1$, $f(i)=r(i)=2-i$, $f(-i)=r(-i)=2+i$
If $r(z)=az^3+bz^2+cz+d$ we have $$a+b+c+d=3$$$$-a+b-c+d=1$$
From which we obtain $b+d=2$ and $a+c=1$
Also $$-ai-b+ci+d=2-i$$ From which $-b+d=2$ so $b=0, d=2$ and $-a+c=-1$ so that $a=1, c=0$
$$r(z)=z^3+2$$

Where you seem to have gone wrong is when you get to 
$$f(z)=q(z)(z-1)+3=h(z)(z-1)(z+1)(z^2+1)+r(z)$$
From this you can conclude that $(z-1)\left(q(z)-h(z)(z+1)(z^2+1)\right)=r(z)-3$ but that does not mean that the term in large brackets is a constant. It is that assumption which puts you off track.
</s>