問題
を2以上の自然数とし，整式をで割った余りをとする．
(1) ，を求めよ．
(2) ，をとを用いて表せ．
(3) 各に対して，との公約数で素数となるものをすべて求めよ．
出典：東北大学 2007年度 前期日程 第2次学力試験 文理共通 文系第1問・理系第1問
方針
と見て余りの係数を更新する。(3)は，素数 p が をともに割ることを，p で割った余りだけに注目したとき の余りが 0 になることと読み替える。すると が を割る必要があり， を割り切る最高次係数1の2次式は だけなので，， から に限られる。最後に が実際に成り立つことも確認する。
解答
(1)
割る式から である。したがって を で割った余りは であり， である。
(2)
を割った余りが であるから と書ける。両辺に x を掛けると である。ここで なので である。したがって である。
(3)
素数 p が と の公約数であるとする。このとき，p を法として考えると を で割った余りは 0 である。つまり，係数を p で割った余りだけで考えると， は を割り切る。
ところが の因数は x だけからできているので， を割り切る最高次係数1の2次式は に限られる。したがって でなければならない。よって を同時に満たす素数 p だけが候補であり， である。
逆に のときは である。 では は で割り切れるから，余りは 0 であり， はともに p で割り切れる。したがって求める素数は である。