技能一覧 › 大学数学 整数論

メビウス関数と反転公式

メビウス関数 の値を求め、、乗法的な に対する 、反転公式 を使って和や関数の値を求められる

前提

この技能までの道筋(28 技能)
算数中学高校大学大学院

読み込み中…

右端(太枠)がこの技能です。左へドラッグすると、さらに前の前提をさかのぼれます。技能を押すと、そこまでの道筋が光ります。

一覧で見る(前提が先)
  1. 分数のたし算・ひき算 (算数 計算と数のきまり)
  2. 小数の四則計算 (算数 計算と数のきまり)
  3. 正負の数の加法・減法 (中学数学 数と式)
  4. 分数のかけ算・わり算 (算数 計算と数のきまり)
  5. 四則の混じった計算の順序 (算数 計算と数のきまり)
  6. 正負の数の乗除・累乗と四則混合 (中学数学 数と式)
  7. 分配法則を使った計算のくふう (算数 計算と数のきまり)
  8. 文字式の計算(同類項・分配法則) (中学数学 数と式)
  9. 乗法公式による展開 (中学数学 数と式)
  10. 因数分解 (中学数学 数と式)
  11. 約数の見つけ方 (算数 整数の性質)
  12. 文字式で表した整数の性質 (中学数学 数と式)
  13. 余りによる整数の分類 (数学A 整数の性質)
  14. 樹形図で数え上げる (算数 場合の数)
  15. 積の法則と和の法則 (算数 場合の数)
  16. 和の法則・積の法則と樹形図 (数学A 場合の数と確率)
  17. 合同式 (数学A 整数の性質)
  18. 最大公約数と最小公倍数 (算数 整数の性質)
  19. 素因数分解と約数の個数 (算数 整数の性質)
  20. 最大公約数と最小公倍数 (数学A 整数の性質)
  21. 互いに素な法への分解 (数学A 整数の性質)
  22. 順列・円順列・重複順列 (数学A 場合の数と確率)
  23. 組合せ (数学A 場合の数と確率)
  24. 確率の定義と和事象・余事象 (数学A 場合の数と確率)
  25. 包除原理 (数学A 場合の数と確率)
  26. オイラー関数の計算 (大学数学 整数論)
  27. 約数の個数と総和 (数学A 整数の性質)
  28. 乗法的関数と約数にわたる和 (大学数学 整数論)

説明

メビウス関数 は、約数にわたる和を「打ち消す」ための関数です。 のように約数全体で足し合わせた量 がわかっていれば、もとの を取り出せます。これをメビウスの反転公式といいます。 の形の和も、素因数ごとの積としてまとめて計算できます。条件を満たすものの個数を数える問題や、オイラー関数のような数論的関数の式を求める場面で使います。

なぜそうしてよいのか

定義と乗法性. 正の整数 に対して とします。 のときは素因数分解を見て決めます。ある素数の 2 乗で割り切れる(平方因子をもつ)なら です。相異なる 個の素数の積なら です。たとえば 、、 です。素数べきでは で、 なら です。

は乗法的です。つまり なら が成り立ちます。理由は次のとおりです。 または なら、 なので明らかです。 か が平方因子 をもてば も で割り切れるので、両辺とも です。 がともに平方因子をもたないとし、 が相異なる 個の素数の積、 が相異なる 個の素数の積だとします。互いに素なので共通の素因数はありません。よって は相異なる 個の素数の積で、平方因子をもちません。したがって です。

基本の等式. は、乗法的関数 と定数関数 の約数和なので、前提の技能から乗法的です。素数べき ()での値は です。よってこの和は、 のとき 、 のとき です。これを と書きます( は、中の条件が真なら 1、偽なら 0)。

同じ考え方で、 が乗法的なら も乗法的です。 での和は になります。したがって です。積は の相異なる素因数 にわたり、 なら値は 1 とします。これは包除原理の「素因数ごとに引いて、重なりを足し戻す」操作を式にしたものです。

反転公式. すべての正の整数 で が成り立つとします。このとき

です。2 つ目の等号では、 を満たす組 全体を、 を先に固定して数え直しています。3 つ目の等号では、内側の和が なので、 の項だけが残ります。

逆向きも示します。すべての で が成り立つとします。 と書き、組 を 固定で数え直すと

となります。ここでも内側の和は なので、 の項だけが残ります。

例: オイラー関数. に反転公式を使うと、 です。ここで とおきます。 で、どんな でも なので、 は乗法的です。 なので積の公式が使え、 が得られます。

手順

  1. を素因数分解し、相異なる素因数 を確認する。 となる約数 は、これらの素数のいくつかを 1 個ずつ掛けたもの(全部で 個)だけである。

  2. 使う形を見分ける。 なら答えは 。乗法的な との和 なら 。 から を求めたいなら反転公式を使う。

  3. 反転公式では と書き、 となる (平方因子をもたない約数)だけを列挙する。

  4. 各項の符号を決める。 が偶数個の素数の積なら 、奇数個なら とする( は )。そのうえで の値を代入して足し合わせる。

  5. 可能なら検算する。たとえば が乗法的になる場合は、素数べきでの値の積と一致するかを確かめる。

例題

関数 が、すべての正の整数 に対して を満たすとする。 を求めよ。

例題の解答

手順1: なので、相異なる素因数は です。 となる約数は の 4 個です。 です。

手順2: とおくと、条件は です。ここから を求めたいので、反転公式を使います。

手順3: です。

手順4:、、 を使うと

です。

手順5(検算):素数べきでは です。よって 、 です。 は乗法的関数 と の約数和なので乗法的です。したがって となり、手順4の結果と一致します。

答え:

よくある誤り

この説明は AI が書き、別の AI が例題を独立に解いて答えを確かめ、説明を一歩ずつ査読しました。

入口の問題

この技能を使う問題

この技能の次に学べること