関西大学 1995年度 過去問・解答

今日の一問 ── 解答と考え方

型の宣言：累乗の余りは必ず循環します。だから「一般の n で求めよ」と言われたら、実際に何乗かして1 に戻るまでの周期を見つけるのが定石です。

1. なぜその一手を選ぶのか

余りは 0 から 15 の 16 通りしかありません。だから 5¹, 5², … の余りを並べていけば、いつか必ず同じ値が現れて循環します（鳩の巣原理）。

実際に計算すると、5⁴ ≡ 1 (mod 16) で 1 に戻ります。つまり周期は 4。あとは n を 4 で割った余りだけ見れば答えが決まります。

2. 解答

1. 5¹ ≡ 5 、5² ≡ 9 、… と順に計算する。
2. 5⁴ ≡ 1 (mod 16) となり、ここから同じ並びが繰り返される。周期は 4。
3. n を 4 で割った余りで分類すると下表のとおり。

   4 で割った余り	5n を 16 で割った余り
   n ≡ 1	5
   n ≡ 2	9
   n ≡ 3	13
   n ≡ 0	1

答え： n を 4 で割った余りが 1, 2, …, 3, 0 のとき、それぞれ 5, 9, 13, 1（周期 4）

3. 検算

n = 1 のとき 5 を 16 で割った余りは 5 で、表の「余り1」の欄と一致します。また n = 5 のときも 5 に戻るはずで、実際 5⁵ ≡ 5 。周期の主張は「1周した先が最初に戻る」ことを1点だけ確かめれば足ります。

この型の一般化：累乗の余りは a と法が互いに素なら、周期はフェルマーの小定理（法が素数 p なら a^p−1 ≡ 1）やオイラーの定理で上から押さえられます。ただし実際の周期はそれより短いことが多いので、試験では素直に計算して 1 に戻る回数を探すのが速い。互いに素でないとき（今回のような）は循環に入る前の助走がつくことがあるので、必ず n = 1 から書き出します。第2章 整数で合同式の使い分けを整理しています。