金沢大学 2002年度 過去問・解答

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

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

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

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

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

2. 解答

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

   9 で割った余り	7n を 27 で割った余り
   n ≡ 1	7
   n ≡ 2	22
   n ≡ 3	19
   n ≡ 4	25
   n ≡ 5	13
   n ≡ 6	10
   n ≡ 7	16
   n ≡ 8	4
   n ≡ 0	1

答え： n を 9 で割った余りが 1, 2, …, 8, 0 のとき、それぞれ 7, 22, 19, 25, 13, 10, 16, 4, 1（周期 9）

3. 検算

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

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