ふと，次の定理の帰納法による証明は，所謂「個数に関する帰納法」のとても良い例ではないかと思った。
自然数$n$に対して，$1$から$n$までの自然数のうちで$n$と互いに素であるものの個数を$\varphi(n)$と表す。これは普通，オイラー(Euler)の関数と呼ばれる。さて，$n$を素因数分解して，
\[ n=p^aq^b\,\cdots\, r^c \]
と表したとき，$\varphi(n)$は
\[ \varphi(n)=n\Bigl(1-\frac{1}{p}\Bigr)\Bigl(1-\frac{1}{q}\Bigr)\,\cdots\,\Bigl(1-\frac{1}{r}\Bigr)\]
と表される。
もちろん，組合せ論で定番の包除原理でも証明できるし，数論的な証明もあるが，素因数の個数に関する帰納法による証明もすっきりしている。
さっぱり理解できない
知ってるのは因数分解と素因数と自然数と関数という言葉。
この公式って何を求める時に使うのですか？
＞sayakoさん
しまった，突っ込まれましたね(笑)。例えば，n=12 とします。1から12までの自然数のうち，12と互いに素(共通の素因数を持たないという意味です)なのは何個あるか？という事なのです。この場合は，12=2 x 2 x 3 なので，2で割れるものと3で割れるものを除きます。それが何個あるか数えるのです。
1(OK) 2(ダメ，2で割れる)，3(ダメ，3で割れる)，4(ダメ，だって2で割れる)，5(OK), 6(ダメ，だって2で割れるし，3でも割れちゃう)，7(OK), 8(ダメ，2で割れるから)，9(ダメ，3で割れるから)，10(ダメ，2で割れる)，11(OK)，12(アハハ，自分自身はダメに決まってますね)
という具合で，結局，12と互いに素なのは，
1 5 7 11
の4個になります。これをこの公式で計算すると
12(1-1/2)(1-1/3) =12 x 1/2 x 2/3 = 4
となるってわけです。12じゃつまんないですが，大きい数字だと威力が分かります。
計算してしまいました
たとえばn=30 だったらどうなるかな、と思って……。
で、中一の頃勉強した「素因数分解」なるものを思い出して、
30=2×3×5
それから、１～30までの数字の中で、２、３、５で割れるものを消去した、
残った数の個数が８コでした。
これを、その公式に当てはめると、
30×(1-1/2)(1-1/3)(1-1/5)=30×1/2×2/3×4/5＝8 でした♪
だけど「何でこの公式が成り立つの？」となると、私には分かりません……。
それは、専門家Sukarabeさんの分野でしょうね 😉
あ、私・音の森ですが、音楽をやる人の例外ではなく、数学・算数がけっこう好きなのです。テレビ番組や新聞で、算数の問題を見つけると時々解いています。そろばんにも興味があります。高校の数学をやり直したい、いづれは大学レベルの数学まで勉強してみたいという夢がありますが、いつになることでしょうね^^; 🙄
＞音の森＠カシオペア さん
おお、数学ネタにコメントありがとうございます～
ワタシ、専門家ってわけじゃありませんけど(笑)、まあ愛好家(？)ってことで
一般の場合の証明はちょっと面倒ですが、素数の種類が2つのときは、次のように説明できます。例として、n=12=2×2×3 を考えましょう。1から12までの自然数は全部で12個あります。このうち、2で割り切れるものは
2、4、6、8、10、12
の6個です。この6個というのは12÷2でも求められます。この6個を除きます。次に3で割り切れるものは
3、6、9、12
の4個です。4＝12÷3 ですね。これも除きます。あれ？6と12はダブルで除かれてしまってます。これはまずい～ 😯 というわけで、もどします。ダブルで除かれてしまった6と12というのは、2でも3でも割り切れるものなんですね。つまり、2×3=6で割り切れるものです。だから、戻すべき個数の2というのは、12÷6＝12÷(2×3) と計算されます。
以上から、1から12までの自然数のうち2でも3でも割り切れないものの個数は
12－6－4＋2＝4個
です。これを、上で説明したことに基づいて、計算式で書いてみると、
12 – 12/2 + 12/3 + 12/(2×3)
となります。12でくくると
12 ( 1 – 1/2 + 1/3 +1/(2×3) )
ですが、括弧の中は次のように積の形で書けるのです。
12 ( 1 – 1/2 ) ( 1 – 1/3 )
分配法則で展開してみると正しいことが分かります。
具体例で説明しましたが、以上の話は素数が2と3以外でも通用しますから、素数の種類が2つのときはこれで大体の説明がすんだと思います。じゃあ、3つ以上のときは？ということですが、大体同じ方針で説明できますが、けっこうめんどくさいです。ではでは～。
「何でこの公式が成り立つの？」の私の疑問に、
「よくわかるかいせつ～」（from:平成教育委員会。笑）をありがとうございます！
ちゃんと自分で紙に書いてみて、時間は掛かりましたが納得しました 💡
最後の、因数分解と展開でちょっと迷いましたが、高校数学の基礎中の基礎なんですよね、ようやく思い出しました(笑)。
こういったレベルで説明していただけるなら、Sukarabeさんの数学ネタ、えっちらおっちら、ついてけます
＞音の森＠カシオペア さん
上手く説明できるか心配だったのですが、分かっていただけたようで安心しました。数学ネタは(他のもですが・・・)備忘録というか、自分のメモみたいなものですので、なんじゃこりゃ、ってことも多いかと思いますが、ご容赦を。じゃあ、Webで書くなよってことなんですけどね(汗)。
検索していて出会いました。はじめてメール差し上げます。
ネットで、ゼータ関数で確率だと云っている人がいたので、まえまえから判りにくいなと思っていたオイラー関数もそうではないかと思い。考えてみましたが、どう思われますか？
—————-
１／ζ（ｓ）はｓ個の整数を勝手に選んだとき、同時に割り切ることのできる１でない数が存在しない確率であることがわかります。すなわち、２つの整数が互いに素である確率は１／ζ（２）＝６／π2 （６１％）となります
互いに素となる整数
１つの数が素数ｐ_i によって割り切れる確率は１／ｐ_i 、両方の数が同じ素数で割り切れる確率は１／(ｐ_i)^2になります。２つの数がどちらもｐ_i で割り切れない確率は
１－(１／(ｐ_i)^2)ですから、互いに素である確率はΠ（１－１／(ｐ_i)^2）。
ここで、Π１／（１－１／(ｐ_i)^2 ）＝Π（１＋１／(ｐ_i)^2＋１／(ｐ_i)^4＋・・・）＝Σ１／(ｎ^2) ＝ζ（２）
したがって、２つの整数が互いに素である確率は１／ζ（２）＝６／π2 （０．６０８）、同様にして３つの整数が互いに素である確率は１／ζ（３）＝０．８３２、４つの整数が互いに素である確率は１／ζ（４）＝９０／π4 （０．９２３９）を得ることができます。
http://www.geocities.jp/ikuro_kotaro/koramu/oira-.htm
————————-
1,2,3,..nの中にある素な数の個数を与える、オイラーの関数φ(n)についても確率と考えて、（もとの数）ｘ（素である確率）で、オイラーの関数が求まります。
φ(p)=p(1-1/p)=p-1
φ(p^(e))=p^(e)(1-1/p)=
φ(n)=n(1-1/p)(1-1/q)(1-1/r)…
ここで、n=p^(e1)q^(e2)r^(e3)
と考えるとまことにすっきりしました。
例えば、15=3*5
φ(15)=15(1-1/3)(1-1/5)=15*(2/3)(4/5)=8 と
１５が３と５で割り切れる確率をのぞいたものになります。
また、Σ[d|n] φ(n)=n
についても、n=pqとすると、
φ(pq)= pq(1-1/p)(1-1/q),
φ(p)= p(1-1/p), φ(q)= q(1-1/q), φ(1)=1
より、
φ(pq)+φ(p)+φ(q)+φ(1)= pq(1-1/p)(1-1/q) +p(1-1/p)+ q(1-1/q)+1
n=pq{(1-1/p)(1-1/q) +(1-1/p)(1/q)+(1-1/q)(1/p)+(1/p)(1/q)}
と見てみると、｛ ｝の中は、
p,q両方と素であるもの、p(q)と素でｑ(p)とは素でないもの,両方とも素でないもの、の数の確率の合計ですから、１となります。
15
=3*5{(1-1/3)(1-1/5)+(1-1/3)(1/5)+(1-1/5)(1/3)+(1/3)(1/5)} ①
=3*5{2/3*4/5+2/3*1/5+4/5*1/3+1/15}
=3*5*(8/15+2/15+4/15+1/15)
=3*5*(15/15)
①式は次と同じ意味です。
φ(15)+φ(5)+φ(3)+φ(1)
＞kamoto さん
はじめまして。ふーん、なるほど～と思いつつ、確率に自信のないワタシとしては今ひとつ確信がもてません。独立性とかは大丈夫なんでしょうか。3で割り切れないことと5で割り切れないことは独立かな？とか。よく考えてないのに中途半端なコメントで申し訳ないのですが、そのあたりがクリアーされれば大丈夫かなと思います。では。
sukarabeさん、
「個数に関する帰納法」というのが、備忘録だったわけでしたね。
失礼しました。素数が一つの時は成り立つ。素数がK個で成り立つとする。もうひとつ素数Ｗ増えてK+1この素数になっても成り立つ。したがってこの式は成り立つ。
これは、ある数M’までは成り立っているとすると、素数が一つ増えて、
M=M’wになっても成り立つ。
たしかにその時のオイラー関数は、
φ(M）=φ(M’w）=φ(M’）φ（w）＝φ(M’）(w-1)=φ(M’）w(1-1/w)
ここで、φ(M’）=M'(1-1/p)…(1-1/r)とすると、
なので、φ(M）=M’w(1-1/p)…(1-1/r)(1-1/w)
たいていの教科書にオイラー関数の紹介の次に、
Σ[d|n] φ(n)=n
の例が載っていて、これが、正直、なかなか、理解できなかった。
件の「初等整数論講義」にもありますね。これを最近理解してやろうと思っていたのでした。
例えば、ある数(例として１２を考えます）を、
2と3の素数で割りきることを考える場合というのは以下の４通り。
両方ともで割り切れない、片一方で割り切れる（２，３の双方２通り）、両方とも割り切る。
(1-1/2)(1-1/3) +(1-1/2)(1/3)+(1/2)(1-1/3)+(1/2)(1/3)
=2/6+1/6+2/6+1/6=1
でこれが、どんな無数の素数の組み合わせになっても、場合を尽くせば１になると、云えるのではないかと思いました。
同じ素数が重なる場合（１２の例だと２＾２）はその中の一つだけを取り出せば十分だと思います。
2項目は、３で割り切れるけれども２では割り切れない。3,9,
３項目は、２で割り切れるけれども３では割り切れない。 2,4,8,10
４項目は、２と３の両者で割り切れる。6,12
１項目は残ったもので、1,5,7,11の４つ
この第一項(1-1/2)(1-1/3)=2/6=1/3だけを取り出す。
これはご説明の
( 1 – 1/2 – 1/3 +1/(2×3) ) と同じです。
φ(6)=φ(2*3)=6*(1-1/2)(1-1/3)=2 ；{１，５}
φ(12)=φ(2^2*3)=12*(1-1/2)(1-1/3)=4
φ(24)=φ(2^3*3)=24*(1-1/2)(1-1/3)=8
φ(18)=φ(2*3^2)=18*(1-1/2)(1-1/3)=6
とここまで書いて、当初の記事を再読して、云われている「組合せ論で定番の包除原理」を理解しようとしていただけだったのではと思い至りました。
お騒がせしました。でもすっきりしてきました。
——————
以下は、連想です。
素数は、それぞれ独立しているので、それらが混じり合ったこんがりかたも起こらないではないのかと、思いました。こんがらがるときはさらに分解して独立性を保てるイデアル論ということになっていったのではと夢想。。。
「引きすぎたところは戻してあげて」という所など、場合分けを考えて、確率を計算することによく似ていますね。例えば、以下のページには、ゼータ関数の逆数とオイラー積の関係でメビウス関数の取り方が瞬間によく判りました。
http://mathworld.wolfram.com/EulerProduct.html
確かに数論の問題は決定論的なのでありましょうが、1/2等の数字が問題になる場合は、それは、偶奇は同じ確率だよね。などと夢想するところから着想が広がるのかなと思いました。以下の記事を最近知りました。
——
次のような遊技がA r t i n により考えられた。F ( x , y ) = 0 という数式を考える。F は整係数の多項式とし, これをm o d （p）で試みて, 0 に合同なら勝ち, 合同でなければ負けとする。この式の取り得る値は, 0 , 1,…, p-1,のp個であるから, 勝つ確率は1/pである。x , y の, 0 , 1 ,…,p-1という値の組合せは, p^2 個あるから,p回勝ち, p^2-p回負けることが予想される。実際に勝った回数をp+r, 負けた回数をp^2-p-rとすれば,rは誤差を表わすわけである. A r t i n は, 遊技の専門家だから確率論的に,rが√pのo r d e r であると考えた. 後に, この直覚が正しいことがわかったのである. 実際この予想を, よリー般的な場合に,巌密に証明できるのである。
A.Weil「ゼータ函数の育成について」数学,７巻４号,１９５６,
——-
（上のp回勝ち,は、p^2(1/p)。 p^2-p回負ける はp^2(1-1/p)といっているのだと理解しました。これは、例えば、9, 25 (p=3,5)のオイラー関数とも見えてきて、それぞれ、負けるとき、つまり「素となる数」の数は6, 20）
メビウス関数が+1になるときと、-1になるときとは、同じ確率であろう。などとも同記事にありました。確率というと語弊がれば、同じ程度に起こる。あるいは組み合わせを尽くすとの事でありましょう。