京大の問題に、私の得意な分野があったので、それだけチャレンジしました。
【問題】
x^2023-1をx^4+x^3+x^2+x+1で割った余りを求めよ。
【解】
x^5-1=(x-1)(x^4+x^3+x^2+x+1)より、
x^5≡1 (mod x^4+x^3+x^2+x+1)
x^2023=(x^5)^404×x^3≡x^3
よって、
x^2023-1≡x^3-1
(mod x^4+x^3+x^2+x+1)
【別解】
x^5-1=(x-1)(x^4+x^3+x^2+x+1)より、
x^5=(x-1)(x^4+x^3+x^2+x+1)+1
P=(x-1)(x^4+x^3+x^2+x+1)とする。
x^5=P+1
x^2020=(x^5)^404=(P+1)^404
=P^404+…+404P+1
=P×(P^403+…+404)+1
x^2023-1=x^3×P×(P^403+…+404)+x^3-1
よって、余りはx^3-1
(2023/2/28)
