問題
以下の問いに答えよ。
(1) 正の奇数，と正の整数，がを満たしているとする。を4で割った余りがを4で割った余りと等しいならば，を4で割った余りはを4で割った余りと等しいことを示せ。
(2) 正の整数がを満たしているとする。このとき，，に対してとなるような正の奇数，が存在することを示せ。
(3) は(2)の通りとし，さらにが2で割り切れるとする。を4で割った余りはを4で割った余りと等しいことを示せ。
(4) を4で割った余りを求めよ。
方針
(1) は奇数が4を法として逆元をもつことを使う。(2) は を積の形で書き， の倍数番目の因子がちょうど を作ることを利用する。残った因子では，奇数番目は奇数どうし， で割って2余る番目は分子分母がともに2でちょうど1回割れるため，全体の比は奇数どうしの比になる。(3) は が偶数のとき，2で割った後の奇数部分まで4を法として一致することを示し，(1) に接続する。(4) はこの縮約を2回適用する。
解答
(1)
は正の奇数であり，仮定より である。奇数 については なので， は4を法として逆元をもつ。 より である。ここで だから，両辺に の逆元をかければ を得る。したがって を4で割った余りと を4で割った余りは等しい。
(2)
とおく。まず であり，さらに である。
この積のうち である因子だけを取り出すと
となる。したがって
である。
右辺の各因子を2で割れる回数について見る。 が奇数なら， も も奇数である。 なら， も も2では割れるが4では割れない。したがって，右辺全体では分子と分母に含まれる2の個数が一致する。
よって右辺を約分して と書いたとき， はともに正の奇数にできる。すなわち となる正の奇数 が存在する。
(3)
(2) で作った について を示せば，(1) から結論が従う。
(2) の積で の因子を考える。 が奇数のときは であるから，分子側と分母側の奇数因子は4を法として一致する。
次に のとき，分子分母をそれぞれ2で割った後の奇数因子は である。いま は偶数なので であり，したがって である。
また である。以上より，(2) で得た奇数部分の分子と分母は4を法として等しい。すなわち である。よって (1) より が成り立つ。
(4)
であり， は偶数である。したがって (3) より である。
さらに であり， も偶数であるから，再び (3) を用いて である。
最後に であり， だから である。よって求める余りは である。