オイラーのφ関数とは簡単に言うと「自然数 n と互いに素な整数の個数」のことです. ただしこの互いに素な数は 1 から n までの整数という範囲で考えます.
例えば n = 5 とすると 5 と互いに素な整数は { 1, 2, 3, 4 } の4個ですからφ(5) = 4 と書き表し, n = 6 ならば 6 と互いに素な整数は { 1, 5 } の2個ですから φ(6) = 2 となります.
いろいろと発展性のある関数ですが, 今回は「 a と b が互いに素ならば, φ(ab) = φ(a)･φ(b) 」 という性質について見てみたいと思います. a と b が素数のときは (a-1)(b-1) の展開式を利用して簡単に証明できますので, まずそれに挑戦したあとに読んでみるのもいいかもしれません.
中高生向きの内容にしたいので 剰余(mod n)とか≡とか直積×とか全単射などの用語や剰余系の定理は避けていきたいので多少ゆるくなると思います. レベルの高いところを望む人はきちんとした証明法なりを検索することをお勧めします.
2つの整数が互いに素とは「2つの整数の最大公約数が 1 である」ということ.
別の言い方をすれば「共通因数を持たない」,「約分できない分子と分母の関係」ともいえます.
例）
13 と 8 はこれ以上同じ数で割ることができないので互いに素である.
14 と 8 は両方とも2で割ることができるので互いに素ではない.
上の数を 2 で割った 7 と 4 はこれ以上同じ数で割ることができないので互いに素である.
φ(ab) = φ(a)･φ(b) を手作業で確認してみることにします.
ひとまずいくつか書き出してみると
これを見ながら φ(ab) と φ(a)･φ(b) を見比べます.
φ(6) = φ(2･3) = 2, φ(2) = 1, φ(3) = 2 なので φ(6) = φ(2)･φ(3) が成り立っています.
同様に
φ(30) = φ(3･10) = φ(3)･φ(10) = 2･4 = 8.
互いに素ならよいので
φ(30) = φ(5･6) = φ(5)･φ(6) = 4･2 = 8 でも結果は同じです.
あたりまえですが, うまくいってます. しかしこれを一般的に証明するのは面倒です.
a, b, ab の各数と互いに素な整数の個数を具体的に数えられないからです.
直接数えられないのならば, 何か別のもの代わりに数えられるものを探さないといけません.
とはいってもいきなり a, b, ab ではどうしようもないので a = 3, b = 5, ab = 15 で考えてみたいと思います.
先ほどは具体的に φ(15) = φ(3)･φ(5)= 2･4 = 8 などとできましたが, 今はそれはできないものとしてやっていきます. 何をやろうとしているのかというと,
3 と互いに素な数 { 1, 2 } と, 5 と互いに素な数 { 1, 2, 3, 4 } から,
15 と互いに素な数 { 1, 2, 4, 7, 8, 11, 13, 14 } を生成する方法を探そう,
またその逆の方法も探そう!
ということです. それがあればその計算1回当たりが互いに素な数1個(1組)に対応するので, 対応の数を数えることで互いに素な数を間接的に数えることができます.
具体的にやってみましょう.
a = 3, b = 5, ab = 15 とし, 以下の決めごとをします
3 と互いに素な数に m と名前を付けます. つまり m は {1,2} の 1 や 2 を代表する数です.
5 と互いに素な数に n と名前を付けます. 同様に n は {1,2,3,4} を代表する数です.
15 と互いに素な数に x と名前を付けます. 同様に x は {1,2,4,7,8,11,13,14} を代表する数です.
さてこの (m, n) の組から x を作る方法(計算方法)を見つけたいわけですが, x は 15 と互いに素な数なのだから 3 でも 5 でも割り切れないはずです.
というわけでひとまず x = 5 m + 3 n としてみてはどうでしょうか. これで (m, n) の1組から x が1つ決まりますし x は 3 でも 5 でも割り切れません. これで対応を見てみましょう.
| ( m, n ) | x = 5 m + 3 n | |
| ( 1 , 1 ) | → | 8 |
| ( 1 , 2 ) | → | 11 |
| ( 1 , 3 ) | → | 14 |
| ( 1 , 4 ) | → | 17 |
| ( 2 , 1 ) | → | 13 |
| ( 2 , 2 ) | → | 16 |
| ( 2 , 3 ) | → | 19 |
| ( 2 , 4 ) | → | 22 |
x は {1,2,4,7,8,11,13,14} になってくれるとよいのですが 8, 11, 14 ぐらいしか出てきません.
ここでもうひとひねりします. 計算して出てきた x の各数はとりあえず 15 と互いに素な数なのでこれを 15 で割った余りに注目します.
| ( m, n ) | x = 5 m + 3 n | ： 15 で割った余り | |
| ( 1 , 1 ) | → | 8 | 8 |
| ( 1 , 2 ) | → | 11 | 11 |
| ( 1 , 3 ) | → | 14 | 14 |
| ( 1 , 4 ) | → | 17 | 2 |
| ( 2 , 1 ) | → | 13 | 13 |
| ( 2 , 2 ) | → | 16 | 1 |
| ( 2 , 3 ) | → | 19 | 4 |
| ( 2 , 4 ) | → | 22 | 7 |
x を 15 で割った余りは順序はばらばらですが {1,2,4,7,8,11,13,14} と一致しています.
というわけでここで x を x = 5 m + 3 n から変更して
x = ( 5 m + 3 n を 15 で割った余り )
と決めなおすことにします. これで (m, n) → x はうまくいきました.
今度は逆です. x から (m, n) を求める方法を考えます.
m と x の間に共通してあるのは 3 で割り切れないというこです.
このことから m = ( x を 3で割った余り ) としてみます.
同様に n = ( x を 5 で割った余り) とします.
これで計算してみると
| (x を 3 で割った余り) | (x を 5 で割った余り) | |||
| ( m, n ) | x | m | n | |
| ( 1 , 1 ) | → | 8 | 2 | 3 |
| ( 1 , 2 ) | → | 11 | 2 | 1 |
| ( 1 , 3 ) | → | 14 | 2 | 4 |
| ( 1 , 4 ) | → | 2 | 2 | 2 |
| ( 2 , 1 ) | → | 13 | 1 | 3 |
| ( 2 , 2 ) | → | 1 | 1 | 1 |
| ( 2 , 3 ) | → | 4 | 1 | 4 |
| ( 2 , 4 ) | → | 7 | 1 | 2 |
悪くはないのですが, もとの (m, n) には戻ってないようです. 順番がずれてます.
数字の場合は対応の数と x の個数があっているのが目で見てわかりますが, これを一般的に広げようとするとちょっと不安です. きちんと戻る対応を考えてみましょう.
いきなりですが x = ( -5 m + 6 n を15で割った余り) とおいて同じことをやってみます.
記号 ≡ の右辺は 左辺を 15 で割ったときの余りを表すことにします.
| (x を 3 で割った余り) | (x を 5 で割った余り) | |||
| ( m, n ) | x | m | n | |
| ( 1 , 1 ) | → | 1 ≡ 1 | 1 | 1 |
| ( 1 , 2 ) | → | 7 ≡ 7 | 1 | 2 |
| ( 1 , 3 ) | → | 13 ≡13 | 1 | 3 |
| ( 1 , 4 ) | → | 19 ≡ 4 | 1 | 4 |
| ( 2 , 1 ) | → | -4 ≡11 | 2 | 1 |
| ( 2 , 2 ) | → | 2 ≡ 2 | 2 | 2 |
| ( 2 , 3 ) | → | 8 ≡ 8 | 2 | 3 |
| ( 2 , 4 ) | → | 14 ≡14 | 2 | 4 |
今度はきれいに x から (m, n) に戻っています.
よって, (m, n) → x, x → (m, n) のどちらも 1 対 1 に対応しています.
言い換えると m と n の組み合わせの個数が x の個数と一致していることになります.
以下 φ(a) = φ(a)･φ(b)を確認します.
φ( ) による書き表し方と要素の個数を比較しているだけで, 要素を数えているわけではない事に注意してください.
3 と互いに素な数 m : {1,2} の個数は φ(3) 個,
5 と互いに素な数 n : {1,2,3,4} の個数は φ(5) 個,
よって m と n との組み合わせの個数は φ(3)･φ(5) 個.
15 と互いに素な数 x : {1,2,4,7,8,11,13,14} の個数は φ(15) 個.
よって φ(15) = φ(3)･φ(5) がいえます.
* x を直接数える代わりに (m, n) の組み合わせを数えて x の個数を知ろうという作戦です.
先ほどのx = ( -5 m + 6 n を 15 で割った余り)の出所が気になる人も多いかと思います.
うまくいかなかった最初の 5 m + 3 n を 3 で割ると 3 n は割り切れて余り 0 ですが, 5 m は
5 m = 3 m +2 m ･･･① と変形しても余りが 2 m になってしまって期待した m になりません.
①の変形を3·(整数)·m + m = {3·(整数) + 1 }mにしたいのです.
さらに「5の倍数である」･･･② ことも保持したいのでこの2つの条件に合う数を探してみると
①に合うものは：･･･ -8, -5, -2, 1, 4, 7, 10, ･･･
この中で②の条件に合うものは -5, 10 です.
一通りには決まらないようなので, まだ調べていけばいろいろ出てくるとは思いますが, とりあえず今回は -5 を採用しました.
同様に n の係数 6 も「5×(整数) + 1」と「3の倍数である」という条件から決められます.
こういうわけでx = ( -5 m + 6 n を 15 で割った余り)になったわけです.
ただし m と n の係数は互いに素になるように選ぶ必要があります. (最初の a, b に互いに素という条件があったので). 先ほどの別候補 10 を使って x = ( 10 m + 6 n を 15 で割った余り) としてはうまくいきません. 互いに素になるよううに, うまく選びなおして
x = ( 10 m + 21 n を 15 で割った余り) や x = ( 10 m - 9 n を 15 で割った余り)
とすればうまくいきます.
「 a と b が互いに素ならば, φ(ab) = φ(a)･φ(b)」を a = 3, b = 5, ab = 15 の場合で考えてみる.
3 と互いに素な数を m, ( mの個数は φ(3) 個 )
5 と互いに素な数を n, ( n の個数は φ(5) 個 )
15 と互いに素な数を x, ( x の個数は φ(15) 個 ) とする.
このとき,
・(m, n) → x を x = ( -5 m + 6 n を 15 で割った余り) で計算する.
・x → (m, n) を m = ( x を 3 で割った余り), n = ( x を 5 で割った余り) で計算する.
・1対1の対応が確認できたので, この対応の個数が x の個数となる.
・(m, n) の組み合わせの通り数が対応の数と一致する.
・(m, n) の組み合わせは φ(3)･φ(5) 個,
・x の個数は φ(15) 個.
・これらが一致するので φ(15) = φ(3)･φ(5) が成り立つ.
よって, この場合に限るのですが φ(ab) = φ(a)･φ(b) が成り立っているといえます.
以下のことに注意してください.
◆（その1）
特殊な場合である φ(15) = φ(3)･φ(5) ではなく, もっと一般的な φ(ab) = φ(a)･φ(b) が成り立っていることを証明したいものです.
15 を ab, 3 を a, 5 を b と置きなおせば, 今までやった手順とほぼ同じなのですが
「(m, n) → x を x = ( -5 m + 6 n を 15 で割った余り ) で計算する.」ときの m, n の係数を決めるところが難関です. もう 3 とか 5 とか具体的な数字ではなくなっているからです.
では x = ( □ m + △ n を 15 で割った余り ) の □ と △ はいったい何にすべきでしょうか？
まずは具体的にやったときのことを思い出してみると
□ は b の倍数で a·(整数) + 1 の形をしている･･･③
△ は a の倍数で b·(整数) + 1 の形をしている･･･④
といえます.
あとはこの条件を満たす □ と △ が分かるといいのですが, 文字が入ってくるので何が何だかわかりません. なので ③④より, □ は a で割って 1 余る数, △ は a の倍数なので整数 p, s を使って
□ = a s + 1, △ = a p とおいたり
□ は b の倍数, △ は b で割って 1 余る数なので整数 q, t を使って
□ = b q , △ = b t + 1
とおいたりする場面が出てきますので頭に入れておいてください.
---------------------------------------------------------------------------
◆（その２）
ある数Aをある数 ab で割ったときの商を Q 余りを R とすると
A = (ab) Q + R
の関係が成り立ちます. この式を少し見方を変えて
A = a (bQ) + R
とすると, これは
「ある数 A をある数 a で割ったときの商が bQ 余りが R である」
と言っていることになります. ただし余り R が R ≧ a のときは もう一度 R を a で割った余りが本当の余りとなります.
x = ( □ m + △ n を ab で割った余り ) をさらに a や b で割って余りを出す場面が出てきますが,
直接は計算できないので, □ m + △ n を a や b で割った余りを求めることで処理しています.
これは上のことが理由になってます.
以上に注意して 一般化へと進みます.
「 a と b が互いに素ならば, φ(ab) = φ(a)･φ(b)」を証明したい.
a と互いに素な数を m, ( m の個数は φ(a) 個 )
b と互いに素な数を n, ( n の個数は φ(b) 個 )
ab と互いに素な数を x, ( x の個数は φ(ab) 個 )
とする.
このとき (m, n) → x を
x = ( □ m + △ n を ab で割った余り ) で計算する (対応をとる).
前節③④より,
□ は b で割り切れるが, a で割り切れない.
△ は a で割り切れるが, b で割り切れない.
よって x は ab で割り切れない. つまり ab と互いに素な数である.
しかも m, n の一次式(一次関数的)になっているので, (m, n) 一組に対して x が一意に決まる.
よって (m, n) → x の対応が確定する.（逆の対応はまだ一意に決まるかどうかは分からない）
次に x → (m, n) を考える.
前節③④より,
□ は a で割って 1 余る数, △ は a の倍数なので整数 p, s を使って
□ = a s + 1, △ = a p とおくと
□ m + △ n = ( a s + 1 ) m + a p n = a ( s m + p n ) + m ･･･⑤.
m = ( x を a で割った余り ), n = ( x を b で割った余り ) で計算する(対応をとる).
x を a で割った余りは □ m + △ n を a で割った余りと一致する.
⑤を a で割ってみると確かに余りは m となる. ( m ≤ a も注意)
また同様に
□ は b の倍数, △ は b で割って 1 余る数なので整数 q, t を使って
□ = b q, △ = b t + 1 とおくと
□ m + △ n = b q m + ( b t + 1 ) n = b ( q m + t n ) + n
これを b で割ると確かに余りは n となる. ( n ≤ b も注意)
よって x → (m, n) の対応が確定する.
1対1の対応が確認できたので, この対応の個数が x の個数となり,
(m, n) の組み合わせの通り数が対応の数と一致する.
(m, n) の組み合わせは φ(a)･φ(b) 個, xの個数はφ(ab) 個.
これらが一致するのでφ(ab) = φ(a)･φ(b) が成り立つ.
x = ( □ m + △ n を ab で割った余り) において a, b が数字で □ や △ も具体的な数字で求めたいときは, □ = b q, △ = ap とおいて, p, q についての方程式 b q + a p = 1 を解きます.
この式の両辺を a や b で割ったときの余りが 1 になることを利用しています.
a, b が互いに素のときは, ユークリッドの拡張互除法により解があることが保証されているので p, q が求まり, それに a, bをかければ □ や △ が求まります.
例）a = 3, b= 5 の場合.
3 p + 5 q = 1 を解いて
( p, q ) = ( 2, -1 ). ←他にも解はあります. そのうちの一つです.
この解から
□ = b q = 5×(-1) = -5,
△ = a p = 3×2 = 6.
よって x =（ -5 m + 6 n を15で割った余り ）となります.
慣れない用語や定理をできるだけ使わないで, 具体的な数値から一般的な文字を使った式へと持って行ったつもりですが, かえって長くなって分かりにくくなってしまったかもしれません.
直感的には当たり前に見えるのですが, いざ説明せよといわれるとなかなか難しいのが整数関係の問題です. 雰囲気だけでもつかんでもらえればと思います.