第200回 からみあう素数(後編)

「きらりーん!☆ ユーリひらめいちゃった!」とユーリは叫ぶ。「整数に誘われて」シーズン第5章後編。
【お休みの予告】

結城浩です。いつもご愛読ありがとうございます。 おかげさまでこのWeb連載も今回で第200回を迎えることになりました!

第200回!!

みなさまの応援に感謝します。

さて、たいへん恐れ入りますが、さらなるパワーアップをはかるため、 このWeb連載の更新を2017年8月4日までお休みさせてください。

日程は以下の通りです。ご迷惑をおかけしますが、よろしくお願いいたします。

Web連載「数学ガールの秘密ノート」予定

・2017年6月30日(金)第200回更新
・2017年7月7日(金)お休み
・2017年7月14日(金)お休み
・2017年7月21日(金)お休み
・2017年7月28日(金)お休み
・2017年8月4日(金)第201回更新
・(以後、毎週金曜日更新)
登場人物紹介

:数学が好きな高校生。

ユーリのいとこの中学生。 のことを《お兄ちゃん》と呼ぶ。 論理的な話は好きだが飽きっぽい。
$ \newcommand{\SQRT}[1]{\sqrt{\mathstrut #1}} \newcommand{\HIRANO}{\unicode[sans-serif,STIXGeneral]{x306E}} \newcommand{\UL}[1]{\underline{#1}} \newcommand{\FBOX}[1]{\fbox{$#1$}} \newcommand{\GEQ}{\geqq} \newcommand{\LEQ}{\leqq} \newcommand{\UP}{\uparrow} \newcommand{\SO}{\text{○}} \newcommand{\NO}{\text{●}} $

僕の部屋

ここはの部屋。ユーリはオイラーの関数$\varphi(n)$についておしゃべりをしている(第199回の続き)。

「$\varphi(n)$について、こんな問題を考えることができるわけだよ!」

オイラーの関数$\varphi(n)$

オイラーの関数$\varphi(n)$は、 $1,2,3,\ldots,n$のうち、$n$と互いに素な整数の個数を表す。

もしも、$p,q$が素数で$p < q$として、$n = pq$が成り立つ場合には、 $$ \varphi(n) = \varphi(pq) = (p-1)(q-1) $$ がいえる。

それでは、$n = pq$と表せないときも含めて考えると、 $$ \varphi(n) $$ はどんな式で表すことができるだろうか。

ユーリ「うわー、めんどくさそー……んにゃ、わかった。数えればいーんじゃん。だって$\varphi(n)$は《$1,2,3,\ldots,n$で$n$と互いに素な整数の個数》なんだから、 $1$から$n$まで調べて数えていけば……やっぱめんどい?」

「《$1,2,3,\ldots,n$で$n$と互いに素な整数の個数》だから、いいかえると《$1,2,3,\ldots,n$で、$n$との最大公約数が$1$になっている整数の個数》を調べればいいよね。 《互いに素》は《最大公約数が$1$》という意味だから。 $n$が小さいうちはめんどうじゃないよ」

ユーリ「$\varphi(1) = 1$でしょ?」

「そうだね。$1$と互いに素なのは$1$という$1$個だけ」

$$ \begin{array}{c|cccccc} n & 1 & \cdots \\ \hline \varphi(n) & 1 & \cdots \\ \end{array} $$

ユーリ「$n$が素数のときは、$n-1$になるんだよね?」

「そうそう。素数の定義を考えればそうなる。$n$が素数だったら、 $1$から$n$までのうちで$n$の約数は$1$と$n$しかない。 ということは、$1,2,3,\ldots,n-1$のどれを選んでも$n$との公約数は$1$しかない。公約数が$1$しかないんだから、 最大公約数も$1$しかない」

ユーリ「$\varphi(n)$の表で$n$が素数のところはすぐわかる!」

「それから、さっきの$\varphi(pq) = (p-1)(q-1)$を使えば、二素数の積になっている場合もすぐわかる」

ユーリ「そだね。$6 = 2\cdot3$とか、$10=2\cdot5$とか……」

「$\varphi(4)$は数えればすぐにわかる」

ユーリ「$4$と互いに素なのは、$1$と$3$だけだよね。だから$2$個で、$\varphi(4) = 2$」

「$\varphi(8)$は……」

ユーリ「$1$は互いに素、$2$は違う。$3$は互いに素、$4$は違う……あ、これ、奇数かどうか調べればいーんじゃない?」

「表にしてみようよ」

$1,2,3,\ldots,8$のうち、$8$と互いに素になるものはどれか



$8$と互いに素なら$\SO$で、互いに素じゃないなら$\NO$とした。

ユーリ「うん、だから、$\varphi(8) = 4$ってことでしょ。次は$\varphi(9)$だね!」

「ちょっと待って、ユーリ。先に進む前に考えようよ」

ユーリ「何を?」

「《例示は理解の試金石》だから、具体的な$n$で$\varphi(n)$の例を作るのは大事だけど、 例をどんどん作っていくだけじゃつまらないよ。 具体例をもとにして一般的に考えなくちゃ」

ユーリ「出たな一般化」

「$\varphi(8) = 4$を求めたけど、$n = 8$からどうやって$\varphi(8) = 4$がわかったんだろう」

ユーリ「$8$と互いに素なのは奇数だから」

「うん、そうだね。そして$1,2,3,\ldots,8$の中で奇数は$4$個だから$\varphi(8) = 4$になった。じゃあ、$8$と互いに素なのは奇数ってどうしてわかったんだろう」

ユーリ「試したから」

「……」

ユーリ「だって、偶数だったら$8$との公約数は$2$とか$4$とかになっちゃうから、 互いに素になんないでしょ?」

「そうだね。その《偶数だったら》というユーリのアイディアはどこから来たんだろう」

ユーリ「試したから。試したから……うん、そっか! 素因数分解だ! $8 = 2^3$だよね。だから、$2$があるのはだめなんだね!」

「うん、その通り。$8$は、$8 = 2^3$と素因数分解できる。だから、$8$は《$2$という素因数》を持つことがわかる。 ということは、$1,2,3,\ldots,8$のうち、 $2$という素因数を持っている整数は、$8$と互いに素にはなれない。 $2$以上の公約数が作れてしまうから」

ユーリ「そだね。ユーリもそー言いたかったの」

「素因数分解は強力だよ……」

そうなんだ。素因数分解は強力だ。整数の構造を明らかにしてくれる。 はそのことをきっと忘れない。 だって……(『数学ガール/フェルマーの最終定理』参照)。

ユーリ「お兄ちゃん?」

「あ、うん。素因数分解を使えば、$\varphi(n)$を求める大きなヒントが得られそうだよ」

ユーリ「$n$が偶数だったら、$1,2,3,\ldots,n$のうち偶数のものは、$n$と互いに素になれない?」

「うん、それは正しいけど、それだけだと弱い。だって、$n$が偶数のとき、 $1,2,3,\ldots,n$のうち奇数だからといって、$n$と互いに素とは限らないし」

ユーリ「えっ? 何いってるですか?」

「$n = 6$という偶数のとき、$3$は奇数だけど、$6$と$3$は互いに素じゃないよね?」

ユーリ「あー……」

「さっきの$n = 8$では$8$は素因数に$2$しかなかった。$$ 8 = 2^3 = 2\times2\times2 $$ だから、$1,2,3,\ldots,8$のうち、 奇数は$8$と互いに素で、偶数は$8$と互いに素じゃないといえたんだ」

ユーリ「あー……ちょっとしゃべるのやめて。わかったから、わかったから!」

ユーリは、の話を制して、しばらく表を見ていた。
$1,2,3,\ldots,8$のうち、$8$と互いに素になるものはどれか



$8$と互いに素なら$\SO$で、互いに素じゃないなら$\NO$とした。

「……」

ユーリ「……あのね、こうなる! $p$を素数とするじゃん? そして、$n$が$p$の……何ていうの?」

「冪乗(べきじょう)のことかな。累乗(るいじょう)ともいうけど。$p^j$の形になった数のことだろ?」

ユーリ「すごい! お兄ちゃんテレパシーだ!」

「超能力者だから」

ユーリ「それはさておき。$n$が素数$p$の冪乗だとするじゃん? $n = p^j$とか。そのとき、$\varphi(n)$は$p^{j-1}(p-1)$になるんじゃない?」

「おお、いきなりの一般化だなあ。ユーリがいうのは、$p$が素数で、$j$が$1$以上の整数のとき、$$ \varphi(p^j) = p^{j-1}(p-1) $$ ということだね?」

ユーリ「そーそー!」

「$8$で検算すると、$8 = 2^3$だから、$p = 2, j = 3$ということ。すると、$$ p^{j-1}(p-1) = 2^{3-1}(2-1) = 4 $$ そして実際$\varphi(8) = 4$になってる。いいね!」

ユーリ「それにね、それにね、$j = 1$のとき! $p^0$って$1$でしょ? だから、$$ p^{j-1}(p-1) = p^{0}(p-1) = p-1 $$ になるけど、ちゃーんと、$p$が素数のとき、$\varphi(p) = p-1$になってるんだよ!」

「すごい! うまいな……ところで、ユーリは、$$ \varphi(p^j) = p^{j-1}(p-1) $$ が成り立つことを証明できる?」

ユーリ「できるよん。だって、$p^j$までで$p-1$を何回繰り返せるかを考えればわかるでしょ?」

「うん、そうだね。僕にはユーリが何を考えてそういってるかはわかる。でもそれだと証明とはいえないなあ」

ユーリ「じゃ、どーすればいーの?」

「うん、まずは、証明したい命題を書いてみようか。これがユーリの証明したいこと」

命題(素数の冪乗とオイラー関数)

$p$を素数とし、$j$を$1$以上の整数とする。このとき、 $$ \varphi(p^j) = p^{j-1}(p-1) $$ が成り立つ。

ユーリ「ふんふん」

「証明は、こんな感じかなあ」

証明(素数の冪乗とオイラー関数)

$p^j$の素因数は$p$だけなので、 「整数が$p$の倍数ではないこと」と 「整数が$p^j$と互いに素であること」とは同値である。

《$1,2,3,\ldots,p^j$》という$p^j$個の整数のうち、《$p$の倍数になるもの》は$p^{j-1}$個ある。 《$p$の倍数にならないもの》は、 $$ p^j - p^{j-1} $$ 個ある。

したがって、 $$ \varphi(p^j) = p^j - p^{j-1} = p^{j-1}(p - 1) $$ がいえる。 (証明終わり)

ユーリ「うわーめんどい……けど、これ、ユーリが考えていたのと同じことかも」

「ユーリはどんなふうに考えたの?」

ユーリ「さっきのこれでわかったの」

この続きは有料会員登録をすると
読むことができます。
cakes・note会員の方はここからログイン

1週間無料のお試し購読する

cakesは定額読み放題のコンテンツ配信サイトです。簡単なお手続きで、サイト内のすべての記事を読むことができます。cakesには他にも以下のような記事があります。

人気の連載

おすすめ記事

ケイクス

この連載について

初回を読む
数学ガールの秘密ノート

結城浩

数学青春物語「数学ガール」の女子高生たちが数学トークをする楽しい読み物です。中学生や高校生の数学を題材に、 数学のおもしろさと学ぶよろこびを味わってください。本シリーズはすでに何冊も書籍化されている人気連載です。 (毎週金曜日更新)

この連載の人気記事

関連記事

関連キーワード

コメント

chibio6 整数nに含まれるnと互いに素な数であるオイラーの関数φ(n)が理解できた。互いに素という関係から様々な式が生み出されるということに奥の深さを感じた。 3ヶ月前 replyretweetfavorite

heliac_arc 互いに素になる確率につながっていくところがすごくいい・・・ そして第200回達成おめでとうございます!!! 3ヶ月前 replyretweetfavorite

tkooler_lufar 先週φ(n)を再帰で書いてくれた方のプログラム読んでループの手段に再帰使っただけじゃんと思い、もっと素敵な実装を1週間考えて思いつかなかったやつ 3ヶ月前 replyretweetfavorite

aramisakihime 200回おめでとうございます! オイラー関数はミルカさんの方で覚えていたので、勉強になりました。次シーズンも楽しみです。 3ヶ月前 replyretweetfavorite