3の100乗を19で割った余りを平方剰余の相互法則で求める方法

数論における余り計算の典型例として、3^100 を 19 で割った余りを求める問題があります。ここでは平方剰余の相互法則を使った解法の考え方を整理します。

1. フェルマーの小定理を利用する

19 は素数なので、フェルマーの小定理より 3^18 ≡ 1 (mod 19) となります。100 を 18 で割った余りを求めると、100 = 18×5 + 10 なので 3^100 ≡ 3^10 (mod 19) です。

2. 3^10 の計算

3^2 ≡ 9 (mod 19), 3^4 ≡ 9^2 ≡ 5 (mod 19), 3^8 ≡ 5^2 ≡ 6 (mod 19) と計算できます。よって 3^10 ≡ 3^8 × 3^2 ≡ 6 × 9 ≡ 54 ≡ 16 (mod 19) となります。

3. 平方剰余の相互法則を用いた解法のヒント

平方剰余の相互法則では、3^((p-1)/2) ≡ ±1 (mod p) を用いることで 3 が 19 の法で平方剰余か否かを判定できます。この場合 3^9 ≡ 7 ≢ ±1 (mod 19) なので、3 は平方剰余ではありません。この情報を使って累乗の指数を半分に分けて効率的に計算する方法も考えられます。

まとめ

3^100 mod 19 を求めるには、フェルマーの小定理で指数を簡略化し、平方剰余の性質を用いることで計算を短縮できます。最終的な余りは 16 です。