オイラー関数Φ(n)や合同式（mod計算）は数論の基本ですが、実際の計算問題になると「どこから手をつければいいのか」が分かりにくい分野でもあります。本記事では、Φ(612)、Φ(63)の求め方と、それを利用した累乗のmod計算の考え方を整理して解説します。
オイラー関数Φ(n)とは何か
オイラー関数Φ(n)とは、1からnまでの整数のうちnと互いに素な数の個数を表す関数です。
例えばnが素数pの場合はΦ(p)=p−1となります。
また、素因数分解を使うことで一般の数でも計算できます。
Φ(612)の求め方
まず612を素因数分解すると 612 = 2^2 × 3^2 × 17 となります。
オイラー関数の公式Φ(n)=n(1−1/p)(1−1/q)…を使うと、Φ(612)=612×(1−1/2)×(1−1/3)×(1−1/17)となります。
計算すると Φ(612)=612×1/2×2/3×16/17=192 になります。
5^200 mod 612の考え方
オイラーの定理より、gcd(5,612)=1なので 5^Φ(612) ≡ 1 (mod 612) が成り立ちます。
つまり5^192 ≡ 1 (mod 612) なので指数を192で割った余りに注目します。
200≡8 (mod 192)より、5^200 ≡ 5^8 (mod 612) を計算すればよいことになります。
5^8 mod 612の実際計算
5^2=25、5^4=625≡13 (mod 612) と段階的に計算します。
さらに5^8=13^2=169 となります。
したがって 5^200 mod 612 = 169 です。
Φ(63)の求め方
63は 3^2×7 に分解できます。
Φ(63)=63×(1−1/3)×(1−1/7)=63×2/3×6/7 です。
計算すると Φ(63)=36 になります。
2^40 mod 63の解き方
gcd(2,63)=1なのでオイラーの定理より 2^36 ≡ 1 (mod 63) が使えます。
40≡4 (mod 36)なので 2^40 ≡ 2^4 (mod 63) に変換できます。
2^4=16より、答えは16です。
まとめ
オイラー関数は素因数分解から計算し、累乗modはオイラーの定理で指数を簡単化できます。
Φ(612)=192、Φ(63)=36を使うことで大きな累乗も小さく扱うことが可能です。
数論の問題は「指数を減らす」という発想が重要なポイントになります。
コメント