>>16
x^1000 = (x^3 + x^2 +x+1)P(x) + Q(x)

P(x) = (x-1)R(x) + a とすると
x^1000 = (x^3 + x^2 +x+1)P(x) + Q(x)
= (x^4 -1)R(x) + a (x^3 + x^2 +x+1) + Q(x)

x^1000 = (x^4)^250 = (x^4 -1)R(x) + 1