ここから本文です

Eulerのφ関数について n以下の正の整数でnと互いに素になる整数の個数をφ(n)とす...

アバター

ID非公開さん

2017/7/1818:55:03

Eulerのφ関数について
n以下の正の整数でnと互いに素になる整数の個数をφ(n)とする.
このときnの素因数をp1,p2,...pkとしたときφ(n)をnとp1,p2,...pkで表すと

φ(n)=n(1-1/p1)(1-1/p2)...(1-1/pk)になることは調べて分かりました。
でもどこも解説が難しくてなぜこうなるのかわかりません。
どなたかわかりやすく解説していただけないでしょうか?

閲覧数:
37
回答数:
1

違反報告

ベストアンサーに選ばれた回答

h7n********さん

2017/7/1819:07:35

1, 2, …, n の n 個の中から 1 つ数を選んだときに

それが n と互いに素になる確率を考えましょう(*^^*)

いま互いに素である数は φ(n) 個としているので

その確率は φ(n)/n となりますね(b^-^)

ここで n は素因数として p₁, p₂, …, pk を

素因数にもっているため

選んだ数は p₁, p₂, …, pk の倍数ではありません☆

p₁ の倍数を選ぶ確率は 1/p₁ であり

逆に p₁ の倍数を選ばない確率は 1 - 1/p₁ です♪

よって選んだ数が p₁, p₂, …, pk の

いずれの倍数でもない確率は

(1 - 1/p₁)(1 - 1/p₂)…(1 - 1/pk) と書けます☆

以上より確率の式

φ(n)/n = (1 - 1/p₁)(1 - 1/p₂)…(1 - 1/pk)

が成り立つので両辺に n をかけてあげれば

φ(n) = n(1 - 1/p₁)(1 - 1/p₂)…(1 - 1/pk)

を導くことができますね(*◕ ◡◕)✿♫♬

アバター

質問した人からのコメント

2017/7/19 17:01:15

確率で考える方法もあるんですね!!
勉強になりました!

この質問につけられたタグ

みんなで作る知恵袋 悩みや疑問、なんでも気軽にきいちゃおう!

Q&Aをキーワードで検索:

Yahoo! JAPANは、回答に記載された内容の信ぴょう性、正確性を保証しておりません。
お客様自身の責任と判断で、ご利用ください。
本文はここまでです このページの先頭へ

「追加する」ボタンを押してください。

閉じる

※知恵コレクションに追加された質問は選択されたID/ニックネームのMy知恵袋で確認できます。

不適切な投稿でないことを報告しました。

閉じる