整数論では、オイラー関数や合同式の計算が頻繁に登場します。特に大学入試や情報系・暗号理論の学習では、オイラーの定理を利用した計算問題が重要です。この記事では、Φ(63)の求め方と2^40 mod 63の計算を途中式を含めて解説します。
オイラー関数Φ(n)とは
オイラー関数Φ(n)は、1からnまでの整数のうち、nと互いに素な整数の個数を表します。
nの素因数分解が分かれば、次の公式で計算できます。
Φ(n) = n × (1 – 1/p₁) × (1 – 1/p₂) × …
ここでp₁、p₂はnの異なる素因数です。
Φ(63)を求める
まず63を素因数分解します。
63 = 3² × 7
したがって、オイラー関数の公式より
Φ(63) = 63 × (1 – 1/3) × (1 – 1/7)
= 63 × (2/3) × (6/7)
= 36
よって Φ(63) = 36 です。
オイラーの定理を利用する
2と63は互いに素なので、オイラーの定理を利用できます。
オイラーの定理は次のようになります。
2^Φ(63) ≡ 1 (mod 63)
Φ(63)=36なので
2^36 ≡ 1 (mod 63)
これを利用して2^40を変形します。
2^40 = 2^36 × 2^4
したがって
2^40 ≡ 1 × 2^4 (mod 63)
≡ 16 (mod 63)
別解として直接確認する方法
オイラーの定理を使わなくても計算できます。
2^6 = 64 ≡ 1 (mod 63)
すると
2^40 = 2^(6×6+4)
= (2^6)^6 × 2^4
≡ 1^6 × 16 (mod 63)
≡ 16 (mod 63)
こちらの方が計算量は少なく、実際の試験では素早く解ける場合があります。
合同式計算で意識したいポイント
合同式では、大きな指数をそのまま計算する必要はありません。
周期性やオイラーの定理、フェルマーの小定理などを利用することで効率的に計算できます。
| 計算対象 | 結果 |
|---|---|
| Φ(63) | 36 |
| 2^36 mod 63 | 1 |
| 2^40 mod 63 | 16 |
このような手法はRSA暗号など現代暗号理論の基礎にもなっています。
まとめ
63を素因数分解すると63=3²×7であり、オイラー関数はΦ(63)=36となります。
また、オイラーの定理より2^36≡1(mod63)が成立するため、2^40=2^36×2^4≡16(mod63)となります。
したがって最終的な答えは、Φ(63)=36、2^40 mod 63=16です。合同式の問題では、素因数分解と周期性を見抜くことが重要になります。
コメント