問題
は3以上の素数であり，，は，をみたす整数であるとする．このときをで割った余りと，をで割った余りが等しければ，であることを示せ．
出典：京都大学 2003年度 前期日程 第2次学力試験 文系 第4問
方針
合同条件から を得る。ただし法が なので、偶奇の情報と での割り切れ方を分けて扱う。 という範囲を使い、 と の可能性を端点まで絞る。
解答
と を で割った余りが等しいので である。したがって が成り立つ。
まず法 で考えると である。整数は2で割った余りと2乗の余りが一致するので、 と は同じ偶奇である。
次に法 で考える。 は素数だから より である。
まず の場合を考える。 より であるから、 は のいずれかである。もし なら、 は または であり、 が奇数であるため の偶奇が異なる。これは先に得た同じ偶奇に反する。よって であり、 である。
次に の場合を考える。 であるから のいずれかである。ところが は同じ偶奇なので は偶数である。一方 は奇数だから、 は起こらない。したがって である。前者では 、後者では から となる。
いずれの場合も が従う。