第200回 シーズン20 エピソード10

からみあう素数（後編）

僕の部屋

僕「$\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$ 個だけ」

ユーリ「$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$ は違う……あ、これ、奇数かどうか調べればいーんじゃない？」

僕「表にしてみようよ」

ユーリ「うん、だから、 $\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$ と互いに素じゃないといえたんだ」

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

僕「……」

ユーリ「……あのね、こうなる！　 $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$ を何回繰り返せるかを考えればわかるでしょ？」

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

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

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

ユーリ「ふんふん」

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

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

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

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