>>90続きです。たとえば
P(x)=(x-1)(x-2)(x-3)Q(x)+a(x-2)(x-3)+bx+c と置く形で解けば、
R(x)=a(x-2)(x-3)+bx+c とすれば、

P(x)を(x-1)(x-2)、(x-2)(x-3)、(x-3)(x-1)で割った余りと
R(x)をそれぞれの式で割った余りが等しいことから
a(x-2)(x-3)+bx+c = a(x-1)(x-2)+3 = a(x-3)(x-1)+3x
と書け、

xの係数と定数項が全て等しくなるようなa,b,cを確かめることで
確かにそのようなP(x)やQ(x)が存在することを確認した上で余りを
求めることができます(前述のような「矛盾する設定」を発見する
こともできます）

前レスのような解法をとった場合、何らかの後処理でこのような
P(x)やQ(x)の存在性が必要となるのではないのか、と思うのですが。