【 問 題 １ 】

　次のように、２の累乗を 7 で割った余りは、累乗数に関して周期 3 である。
　　　　MOD ( 2¹, 7 ) ＝ 2　　つまり　　2¹　≡　2　( mod 7 )
　　　　MOD ( 2², 7 ) ＝ 4　　つまり　　2²　≡　4　( mod 7 )
　　　　MOD ( 2³, 7 ) ＝ 1　　つまり　　2³　≡　1　( mod 7 )
　　　　MOD ( 2⁴, 7 ) ＝ 2　　つまり　　2⁴　≡　2　( mod 7 )
　　　　MOD ( 2⁵, 7 ) ＝ 4　　つまり　　2⁵　≡　4　( mod 7 )
　　　　MOD ( 2⁶, 7 ) ＝ 1　　つまり　　2⁶　≡　1　( mod 7 )
　　　　MOD ( 2⁷, 7 ) ＝ 2　　つまり　　2⁷　≡　2　( mod 7 )
　　　　　　　　　　　　　　　　・
　　　　　　　　　　　　　　　　・
　　　　　　　　　　　　　　　　・
　このことを証明せよ。

　【 解 答 】

　7 で割ると n 余る数 から 7 で割ると n 余る数 を引くと、7 で割り切れる数 になる。
　2ⁿ⁺³ − 2ⁿ　＝→　2ⁿ ( 2³ − 1 )　＝→　2ⁿ × 7　だから、 2ⁿ⁺³ − 2ⁿ　は 7 で割り切れる。
　よって、2ⁿ⁺³ を 7 で割った余り と 2ⁿ を 7 で割った余り は等しい。
　したがって、２の累乗を 7 で割った余りは、累乗数に関して周期 3 である。

【 問 題 ２ 】

　２つの素数 n と m ( n ＜ m ) があるとき、 MOD ( n^m, m ) ＝ n であることを証明せよ。

　【 解 答 】

　数理論 ＞ フェルマーの小定理　をご覧ください。

( 備 考 )
　　例えば、n＝3, m＝7 のときを考えてみよう。
　　　　MOD ( 3¹, 7 ) ＝ 3　　つまり　　3¹　≡　3　( mod 7 )
　　　　MOD ( 3², 7 ) ＝ 2　　つまり　　3²　≡　2　( mod 7 )
　　　　MOD ( 3³, 7 ) ＝ 6　　つまり　　3³　≡　6　( mod 7 )
　　　　MOD ( 3⁴, 7 ) ＝ 4　　つまり　　3⁴　≡　4　( mod 7 )
　　　　MOD ( 3⁵, 7 ) ＝ 5　　つまり　　3⁵　≡　5　( mod 7 )
　　　　MOD ( 3⁶, 7 ) ＝ 1　　つまり　　3⁶　≡　1　( mod 7 )
　　　　MOD ( 3⁷, 7 ) ＝ 3　　つまり　　3⁷　≡　3　( mod 7 )　←

次の式が成立すると予想できる。
　　　MOD ( n^a, m ) ＝ MOD ( n^a+(m−1), m )
よって、
　　　MOD ( n^a+(m−1)−n^a, m ) ＝ ０
つまり、
　　　MOD ( n^a( n^(m−1)−1 ) , m ) ＝ ０
したがって、
　　　n^(m−1) は m で割ると 1 余る数である。

【 問 題 ３ 】

　2022²¹ を 7 で割った余りを求めよ。

　【 解 答 】

　2022 ＝→　7 × 288 ＋ 6　だから、2022 を 7 で割ると 6 余る。
　7 で割ると n 余る数 を m 乗した数を 7 で割った余りは、n を m 乗した数を 7 で割った余りに等しい。
　したがって、2022²¹ を 7 で割った余りは、6²¹ を 7 で割った余りに等しい。
　6²¹ ＝→　( 6² )¹⁰ × 6　＝→　36¹⁰ × 6
　36 は 7 で割ると 1 余る数である。
　36¹⁰ を 7 で割った余りは、1 を 10 乗した数を 7 で割った余りに等しい。
　1 を 10 乗した数は 1 だから、36¹⁰ を 7 で割った余りは 1 である。
　7 で割ると 1 余る数 を m 倍した数を 7 で割った余りは、m を 7 で割った余りに等しい。
　よって、 36¹⁰ × 6 を 7 で割った余りは 6 である。
　よって、 6²¹ を 7 で割った余りは 6 である。
　したがって、2022²¹ を 7 で割った余りは 6 である。