余りは高々一次式だからax+bと置けて、
x^15+1=(x^2+x+1)Q(x)+ax+b
と表せる。ここにx^2+x+1=0の解を代入してa,bを求めればよい。
一見計算が大変そうだけど、
x^2+x+1=0⇒(x-1)(x^2+x+1)=x^3-1=0
なので、x^2+x+1=0の解は3乗すると1になるので、15乗しても1。だから大したことない。