以下の問いに答えよ。
(1) 正の奇数 , と正の整数 , が を満たしているとする。 を で割った余りが を で割った余りと等しいならば， を で割った余りは を で割った余りと等しいことを示せ。
(2) 正の整数 , が を満たしているとする。このとき，, に対して となるような正の奇数 , が存在することを示せ。
(3) , は (2) の通りとし，さらに が で割り切れるとする。 を で割った余りは を で割った余りと等しいことを示せ。
(4) を で割った余りを求めよ。
と は で割った余りが同じですから と書けます。 に入れると 、つまり です。
左辺は の倍数です。 は奇数で と互いに素ですから、 が割り切るのは のほうです。
よって です。これで (1) が示せました。
奇数を掛けても で割った余りの情報は消えない、というのがこの小問の中身です。あとは、うまい奇数を見つける話になります。
を奇数 , で作れるのは、 と が持つ の個数が同じときです。そのとき を の奇数部分、 を の奇数部分に取れば足ります。
を、 以下の奇数の積 と偶数の積に分けます。偶数の積は です。
これを の つの階乗に当てると、 の部分は奇数どうしの比になり、残りが になります。
同じことをもう 度すると に落ちます。 の個数は と で等しく、奇数 , が取れます。これで (2) が示せました。
(3) では、その と が で割って同じ余りを持つことを見ます。どちらも どうしの積で書けています。
奇数 , , , , は で割った余りが , , , と交互です。だから最初の 個の積は と同じ余りになります。
は 、 は と同じ余りです。 側の指数は 、 側は になります。
が偶数なら と の偶奇がそろい、 が成り立ちます。指数が一致するので 、(1) から (3) が出ます。
、 です。 は偶数ですから (3) が使えます。
よって です。添字が一気に小さくなりました。
もう 度使います。、 で も偶数ですから、 です。
です。答えは です。