『オイラーの関数』解答

◆広島県　清川　育男さんからの解答。

○問題１

φ（９）＝φ（３²）＝３²-３¹＝９−３＝６
９と互いに素になる数は、１，２，４，５，７，８の６個。

φ（１０）＝φ（２×５）
　　　　　＝φ（２）×φ（５）
　　　　　＝（２−１）×（５−１）
　　　　　＝４

１０と互いに素になる数は、１，３，７，９の４個。

φ（１１）＝１１−１＝１０
１１と互いに素になる数は、１，２，３，４，５，６，７，８，９，１０の１０個。

○問題２

φ（ｐ）のとき、ｐの約数は、ｐ　１個だけ。
φ（ｐ）＝ｐ−１

φ（ｐ^m）のとき、ｐ^mの約数は、ｐ，２ｐ，......，ｐ^m-1ｐ。
　ｐ^m-1個。したがって、
ｐ^mと互いに素になる数の個数は、ｐ^m-ｐ^m-1

φ（ｐ^m）＝ｐ^m-ｐ^m-1

○問題３　保留。

○問題４

　φ（１４００）
＝φ（８×１７５）
＝φ（８）×φ（１７５）
＝φ（２³）×φ（２５）×φ（７）
＝φ（２³）×φ（５²）×φ（７）
＝（２³-２²）×（５²-５¹）×（７−１）
＝（８−４）×（２５−５）×６
＝４×２０×６
＝４８０

【コメント】

　はい、見事正解です。
細かいことを言うと、問題２で、

「φ（ｐ）のとき、ｐの約数は、」
「φ（ｐ^m）のとき、ｐ^mの約数は、」

という表現はおかしいですから

「φ（ｐ）のとき、ｐの約数は、」を
「φ（ｐ）のとき、ｐ以下のｐと互いに素でない数は」に、

「φ（ｐ^m）のとき、ｐ^mの約数は、」

を
「φ（ｐ^m）のとき、ｐ^m以下のｐ^mと互いに素でない数は」

に直してください。

この法則を使えば、φ（１４００）がかなり簡単に計算できるのが数学のすばらしいところですね。

◆愛知県の高校生　Sparking さんからの解答。

【おまけの解答】

問題はａとｂが互いに素のとき
ａ^φ(b)≡１　（ｍｏｄ．ｂ）…(1)を証明することである。

今

φ(ｐm)＝ｐm×

p-1 ―――― p

＝(ｐ−１)ｐm-1

なので、

ｂ＝ｐ^mのときは問題は、

ａ^φ(b)＝ａ^{(ｐ−１)ｐm-1}≡１　（ｍｏｄ．ｐ^m）…(2)

これをまず示すことにする。

ｍ＝１のとき、(2)は
ａ^p-1≡１　（ｍｏｄ．ｐ）…(2)´

今、二項定理より、
ａ^p

＝(ａ−１)p＋１＋

p-1 Σ k=2

pＣk(ａ−１)k

≡(ａ−１)^p＋１
（∵_pＣ_kはｐの倍数）
≡(ａ−２)^p＋２
……　
≡１＋（ａ−１）
＝ａ（ｍｏｄ．ｐ）

∴ａ^p−ａ≡０（ｍｏｄ．ｐ）

ａ（ａ^p-1−１）≡０　（ｍｏｄ．ｐ）

ａにｐの因数は含まれないので、

ａ^p-1−１≡０　（ｍｏｄ．ｐ）

よって(2)´は示された。

つまり、ｍ＝１のとき(2)は成り立つ。

ｍ＝z@のとき(2)が成り立つとき、

ａ^(p-1)pz@-1≡１　（ｍｏｄ．ｐ^z@）

∴適当な整数Ｑを用いて、

ａ^(p-1)pz@-1＝Ｑｐ^z@＋１と書ける。

両辺をｐ乗して、

（ａ^(p-1)pz@-1）^p＝（Ｑｐ^z@＋１）^p

ａ^{(p-1)pz@-1×p}

＝

p-1 Σ k=2

pＣk（Ｑｐz@）k＋ｐ（Ｑｐz@）1＋１

ａ^(p-1)pz@-1+1
＝ｐ^z@+1｛��_pＣ_k(Ｑ^k・ｐ^(k-1)z@-1)＋Ｑ｝＋１

∴ａ^{(p-1)p(z@+1)-1}≡１　（ｍｏｄ．ｐ^z@+1）
より(2)はｍ＝z@＋１でも成立。

数学的帰納法より全てのｍについて、(2)がいえる。

つまり、ｂ＝ｐ^mと表せるとき、ｂと互いに素な整数ａとすると、
ａ^φ(b)≡１　（ｍｏｄ．ｂ）…(3)

αとβが互いに素であり、γをβと互いに素でかつ
０＜γ≦αを満たす自然数φ（α）個の中の一つとするとき、β個の整数の集合
Ａ｛ｋα＋γ｜ｋ＝０，１，２，……，β−１｝を考えるとき、要素は全てαと互いに素。

この中にβで割った剰余が等しい２つの要素があったと仮定し、
それをk₁α＋γ，k₂α＋γとすると仮定から、

k₁α＋γ≡k₂α＋γ　（ｍｏｄ．β）
α（k₁−k₂）≡０　　（ｍｏｄ．β）

αとβは互いに素よりαにβの因数は含まれないので、

k₁≡k₂（ｍｏｄ．β）

今k₁，k₂は相異なるβ未満０以上の整数であることからこれはあり得ない。

∴要素をβで割った剰余は全て異なる。

よって，β個の剰余の集合Ｂは０からβ−１までの中の相異なるβ個の整数の集合である。

今βで割った剰余がβと互いに素なら，被除数もβと互いに素であることおよび、
Ｂの中にβと互いに素であるものはφ（β）個あることから，Ａにもφ（β）個ある。

βと互いに素であるγ１個につきａともβとも互いに素である整数はφ（β）個、
そうではないγの場合全てαと互いに素ではない。

∴αとβが互いに素のとき、
φ（αβ）＝φ（β）φ（α）……(4)

どんなbでも適当な素数p₁，p₂，…，p_nを使って、

ｂ＝p₁^m₁・p₂^m₂・……・p_n^m_nと素因数分解できる。
（m₁，m₂，……，m_n＝１，２，……）

このときp₁^m₁，p₂^m₂，……，m_n^m_nはそれぞれ互いに素だから、(4)より(1)は、

ａ^{φ（p₁m₁）・φ（p₂m₂）・……φ（p_nm_n）}≡1　（ｍｏｄ．ｂ）と書ける。……(5)

左辺をp_k^m_kで割ったあまりを考えると、
（ｋ＝１，２，……，ｎ）

（(5)の左辺）
＝｛ａφ（pkmk）｝φ（p1m1）・……・φ（pk-1mk-1）・φ（pk+1mk+1・……・φ（pnmn）
≡｛１｝（省略）
＝１　　（ｍｏｄ．pkmk）

このとき
p₁^m₁，p₂^m₂，……，m_n^m_nはそれぞれ互いに素だから、(6)が成り立つためには、整数Ζを使って

（(5)の左辺）−１
＝Ζ×（p₁^m₁）・（p₂^m₂）・……・（p_n^m_n）と書けなければならない。

φ（p₁^m₁）・φ（p₂^m₂）・……φ（p_n^m_n）＝φ（ｂ），
p₁^m₁・p₂^m₂・……p_n^m_n＝ｂを戻すと、

ａ^φ(b)−１＝Ζ×ｂ≡０　（ｍｏｄ．ｂ）

よって(1)は成り立つ。
（証明終わり）

　『オイラーの関数』へ

　数学の部屋へもどる