初等整数論/数論的関数のソースを表示

{{Nav}}

== オイラーのφ関数 ==
オイラーのφ関数とは、次のように定義される関数である。

<math>\varphi(n) = </math> ( n 以下の自然数のうち n と互いに素な数の個数 )


より厳密に定義するならば、

<math>
\psi(d, n) = 
\begin{cases}
1 \ \ ( \ gcm(d,n) = 1 \ ) \\
0 \ \ (otherwise)
\end{cases}</math>

とし、<math>\varphi(n) = \sum_{d = 1}^{n} \psi(d, n)</math> とすればよい。このように、値が整数や自然数のときにしか意味を持たない関数を'''数論的関数'''という。広義には値が整数や自然数のときに意味を持つ関数をそう呼ぶ。


'''例'''

<math>
\begin{align}
\varphi(1) & = 1 \ \ \ \{ 1 \} \\
\varphi(2) & = 1 \ \ \ \{ 1 \} \\
\varphi(3) & = 2 \ \ \ \{ 1, 2 \} \\
\varphi(4) & = 2 \ \ \ \{ 1, 3 \} \\
\varphi(5) & = 4 \ \ \ \{ 1, 2, 3, 4 \} \\
\varphi(6) & = 2 \ \ \ \{ 1, 5 \} \\
\varphi(7) & = 6 \ \ \ \{ 1, 2, 3, 4, 5, 6 \} \\
\varphi(8) & = 4 \ \ \ \{ 1, 3, 5, 7 \} \\
\varphi(9) & = 6 \ \ \{ 1, 2, 4, 5, 7, 8 \} \\
\varphi(10) & = 4 \ \ \{ 1, 3, 7, 9 \} \\
\end{align}
</math>

さて、このオイラーのφ関数について簡単に以下のことが分かる。

<math>p</math> が素数のとき、

<math>\begin{align}
\varphi(p) & = p-1 \ \ ( \, \{ 1, 2, \cdots , p-1 \} \, ) \\
\varphi(p^n) & = p^{n-1}(p-1)
\end{align}</math>

第二の式について、互いに素でないものは <math>1 \cdot p, 2 \cdot p, \cdots , p^{n-1}p</math> の <math>p^{n-1}</math> 個であるから、<math>p^n</math> から引いて <math>p^{n-1}</math> をくくりだして式を得る。

====== 定理 3.1 ======

<math>a, b</math> が互いに素ならば <math>\varphi(ab) = \varphi(a)\varphi(b)</math>

'''証明 1'''<br />
証明の前に、φ関数の意味を広げる。

<math>n</math> は、<math>n</math> を法とするある類の任意の数 <math>a</math> と一定の最大公約数を持つ。つまり、

<math>(n, r) = (n, a+nt)</math> である。まずはこのことを証明しよう。


<math>(n, a) = 1</math> とする。任意の自然数 <math>t</math> について <math>(n, a + nt) = 1</math> であることを証明する。

仮にある数 <math>k</math> においてこれが成り立たず <math>(n, a + nk) = d > 2</math> であるとする。仮定より <math>n = dn', a + nk = da'</math> とすれば、

<math>(a + nk) - nk = dn' - da' \iff a = d(n' - a')</math> となり <math>n, a</math> は公約数 <math>d > 2</math> を持つことになるが、これは矛盾である。

次に、<math>(n, a) = d > 2</math> とする。仮定より、<math>n = dn'', a = da'', (n'', a'') = 1</math> となる。

<math>a + nt = da'' + dn''t = d(a'' + n''t)</math> となる。<math>(n'', a'') = 1</math> なので、先ほど証明した互いに素の場合を適用して、<math>(n'', a'' + n''t) = 1</math> となるので、<math>(dn'', da'' + dn''t) = d \iff (n, a+nt) = d.</math>


さて、以上に証明されたことによって、類は法と一定の最大公約数を持つ。さて、法 <math>n</math> が類の数と互いに素なとき、この類を'''既約類'''といい、既約類全てを'''既約剰余系'''ということにしよう。すると、<math>1, 2, \cdots, n-1, n</math> の数を類の代表の元と考えれば <math>\varphi(n)</math> の値とは、<math>n</math> を法としたときの既約剰余系の類の数である。そのような立場からこの定理を考える。

さて、<math>a, b</math> は互いに素なので、[[初等整数論/整除性#定理 1.9|定理 1.9]] から、任意の数を <math>ax + by = k</math> という形に表せる。<math>x, y</math> をそれぞれ <math>b, a</math> の倍数だけ増減しても、それらは <math>ab</math> を法として合同である。そこで、<math>y</math> に <math>a</math> を法とする類の <math>a</math> 個の代表の元を与え、<math>x</math> に <math>b</math> を法とする類の <math>b</math> 個の代表の元を与えるときに、<math>ax + by</math> の式から出る <math>ab</math> 個の数は、<math>ab</math> を法とした剰余系にならなければならない。

なぜかというと、同じ類の数を与えても <math>ax + by</math> から出てくる数は同じ類に属すことは先ほどの通りで、逆に <math>ax + by</math> から出てくる数が同じ類に属せば <math>x, y</math> は同じ類に属すからである。後者については、出てくる数は <math>ab</math> 同じ類に属するので <math>ax' + by' = k, ax'' + by'' = k + abt</math> と表せ、

<math>abt = a(x'-x'') + b(y'-y'') \iff b \{ at - (y'-y'') \} = a(x'-x'')</math> となるので、<math>(a,b) = 1</math> から、[[初等整数論/整除性#公倍数・公約数|定理 1.6]] より <math>at - (y'-y'')</math> は <math>a</math> の倍数だと分かる。したがって <math>y-y'</math> は <math>a</math> の倍数、すなわち

<math>y' \equiv y'' \pmod{a}</math> となる。同様にして

<math>abt = a(x'-x'') + b(y'-y'') \iff a \{ bt - (x'-x'') \} = b(y'-y'')</math> として、<math>x' \equiv x'' \pmod{b}</math> が分かる。つまり、<math>a, b</math> をそれぞれ方とした類の組合わせと、<math>ab</math> 法とした類は、<math>ax + by</math> によって一対一の対応ができている。 

<math>(x, b) = 1, (y, a) = 1</math> とすれば、<math>(a, b) = 1 \Rightarrow (a, by) = 1 \Rightarrow (a, ax + by) = 1</math> となる（最後には冒頭で証明した事項を用いた）。

また同様にして <math>(b, ax + by) = 1</math> より、[[初等整数論/整除性#定理 1.13|定理 1.13]] から <math>(ab, ax + by) = 1</math> となる。

以上によって、<math>x</math> に <math>b</math> を法とした <math>\varphi(b)</math> 個の既約剰余系の代表元、<math>y</math> に <math>a</math> を法とした <math>\varphi(a)</math> 既約剰余系の代表元、を与えれば、<math>ab</math> を法とする <math>\varphi(ab)</math> 個の既約剰余系が得られるのだが、ここに一対一の対応ができているため、<math>\varphi(a)\varphi(b) = \varphi(ab).</math>

'''証明 2'''<br />
<math>\alpha_1, \alpha_2, \cdots , \alpha_m \ \ ( \, m = \varphi(a) \, ), \ \ \beta_1, \beta_2, \cdots , \beta_n \ \ ( \, n = \varphi(b) \, )</math> をそれぞれ <math>a, b</math> を法としたときの既約剰余系とすれば、

<math>\alpha_k, \beta_l</math> の <math>mn</math> 個の組み合わせについて、<math>(a, b) = 1</math> より[[初等整数論/合同の応用#中国の剰余定理|中国の剰余定理]]から

<math>\begin{cases}
\gamma \equiv \alpha_k \pmod{a} \\
\gamma \equiv \beta_l \pmod{b} \\
\end{cases}</math>

となる <math>\gamma</math> が <math>ab</math> を法としてただひとつ存在する。

<math>\gamma \equiv \alpha_k \pmod{a}</math> より、<math>\gamma = \alpha_k + at</math> となる。<math>(a, \gamma) = (a, \alpha_k + at)</math>

ここで、証明 1 の冒頭に証明されたことから、<math>(a, \alpha_k + at) = (a, \alpha) = 1</math> となり、つまり <math>(a, \gamma) = 1.</math>

同様に <math>(b, \gamma) = 1</math> したがって[[初等整数論/整除性#定理 1.13|定理 1.13]] より <math>(ab, \gamma) = 1.</math>

逆に、<math>(\gamma, ab) = 1</math> とすれば、<math>(\gamma, a) = 1, (\gamma, b) = 1</math> より、

<math>\begin{cases}
\gamma \equiv \alpha \pmod{a} \\
\gamma \equiv \beta \pmod{b} \\
\end{cases}</math>

なる <math>\alpha, \beta</math> がただひとつ定まる。つまり、<math>ab</math> を法とする既約剰余系は <math>a</math> を法とする既約剰余系と <math>b</math> を法とする既約剰余系の組み合わせと一対一対応ができている。すなわち、

<math>\varphi(ab) = \varphi(a)\varphi(b).</math>

====== 定理 3.2 ([[w:オイラーの定理 (数論)|オイラーの定理]]) ======
<math>(a, n) = 1</math> としたときに

<math>a^{\varphi(n)} \equiv 1 \pmod{n}</math>

'''証明'''<br />
<math>\varphi</math> 関数は既約剰余系の数を表す関数だった。ここで <math>x_1, x_2, \cdots , x_{\varphi(n)}</math> を既約剰余系とおく。このとき、<math>(a, n) = 1</math> より <math>ax_1, ax_2, \cdots , ax_{\varphi(n)} \cdots (1)</math> は <math>n</math> で割り切れない。

<math>ax_k \equiv ax_l \Rightarrow x_k \equiv x_l \pmod{n}</math> である。対偶をとって <math>x_k \not\equiv x_l \Rightarrow ax_k \equiv ax_l \pmod{n}</math>

よって (1) は既約剰余系をなす。

よってどちらも合同な一対一対応ができるので、全てをかけ合わせて

<math>ax_1 \, ax_2 \cdots ax_{\varphi(n)} \equiv x_1 \, x_2 \cdots x_{\varphi(n)} \pmod{n}</math>

<math>x_1, x_2, \cdots , x_{\varphi(n)}</math> は既約剰余系なので

<math>a^{\varphi(n)} \pmod 1 \pmod{m}</math> となり目的の式を得た。

====== 定理 3.3 ======
<math>a = p_0^{a_0}p_1^{a_1} \cdots p_n{a_n}</math> と素因数分解したとき、

<math>\varphi(a) = a \left( 1-\frac{1}{p_0} \right) \left( 1-\frac{1}{p_1} \right) \cdots \left( 1-\frac{1}{p_n} \right)</math>

'''証明'''<br />
<math>\varphi(a) = \varphi(p_0^{a_0}p_1^{a_1} \cdots p_n{a_n}) \cdots (1)</math>

ここで、<math>p_0^{a_0}, p_1^{a_1} \cdots p_n{a_n}</math> は同じ素因数を持たず互いに素なので、定理 3.1 より、

<math>(1) \iff \varphi(a) = \varphi(p_0^{a_0})\varphi(p_1^{a_1} \cdots p_n{a_n})</math> となる。これを繰り返し行えば、

<math>\begin{align}
\varphi(a) & = \varphi(p_0^{a_0})\varphi(p_1^{a_1}) \cdots \varphi(p_n^{a_n}) \\
& = (p_0^{a_0} - p_0{a_0-1})(p_1^{a_1} - p_1{a_1-1}) \cdots (p_n^{a_n} - p_n{a_n-1}) \\
& = p_0^{a_0}p_1^{a_1} \cdots p_n^{a_n} \left( 1-\frac{1}{p_0} \right) \left( 1-\frac{1}{p_1} \right) \cdots \left( 1-\frac{1}{p_n} \right) \\
& = a \left( 1-\frac{1}{p_0} \right) \left( 1-\frac{1}{p_1} \right) \cdots \left( 1-\frac{1}{p_n} \right)
\end{align}</math>


----

さて、オイラーのφ関数を少し発展させたことを考える。

ある数 <math>n</math> とその1つの約数を <math>d_0</math> とおき、<math>n</math> 以下の数のうち、最大公約数が <math>d_0</math> であるものの個数について考慮しよう。任意の数 <math>k \leqq n</math> をおき、<math>(n, k) = d_0</math> となるような自然数 <math>k</math> の個数である。

<math>n = d_0n', \, k = d_0k'</math> としたときに、<math>k' \leqq n', \, (n', k') = 1</math> である。

逆に、<math>k' \leqq n', \, (n', k') = 1</math> ならば、<math>n = d_0n', \, k = d_0k'</math> であるから <math>k \leqq n, \, (n, k) = d_0</math> である。つまり、最大公約数が <math>d_0</math> となるような数の個数は <math>\varphi \left( \frac{n}{d_0} \right)</math> なのである。

<math>n</math> の約数を、<math>A = \{1, d_0, d_1, \cdots, d_m, n \}</math> とおくと、<math>n</math> 以下の任意の数 <math>k</math> について、<math>n</math> との最大公約数は <math>A</math> に含まれる数のうちのどれかである。すなわち、

<math>\begin{align}
n & = \varphi \left( \frac{n}{1} \right) + \varphi \left( \frac{n}{d_0} \right) + \cdots + \varphi \left( \frac{n}{d_m} \right) + \varphi \left( \frac{n}{n} \right) \\
\iff n & = \sum_{d \, | \, n, d > 0}^{} \varphi(d)
\end{align}</math>

<math>\sum_{d \, | \, n, d > 0}^{}</math> というのは、<math>n</math> で割り切れる全ての正の数についての和という意味である。以上より、次の定理を導いた。

====== 定理 3.4 ======
<math>n = \sum_{d \, | \, n, d > 0}^{} \varphi(d)</math>

さて、定理 3.4 が得られたわけだが、実は任意の数について <math>n = \sum_{d \, | \, n, , d > 0}^{} \psi(d)</math> を満たす数論的関数 <math>\psi</math> はオイラーのφ関数しか存在しない。つまり、先ほどの性質を満たすならば、それはオイラーのφ関数であると断言できるのである。このことを証明する前に、まずは、[[w:メビウスの関数]]というものが必要になる。

== メビウス関数 ==
'''定義'''

メビウス関数 <math>\mu(n)</math> は、以下のように定義される自然数についての関数である。

* <math>\mu(1) = 1</math>
* <math>n</math> とある素数 <math>p</math> について、<math>p^2 \, | \, n</math> のとき（平方因子を持つとき） <math>\mu(n) = 0</math>
* <math>n</math> が相異なる <math>k</math> 個の素数の積のとき <math>\mu(n) = (-1)^k</math>

====== 定理 3.5 ======
# <math>(m, n) = 1 \Rightarrow \mu(mn) = \mu(m)\mu(n)</math>
# <math>(m, n) \neq 1 \Rightarrow \mu(mn) = 0</math>

'''証明'''<br />
<math>(m, n) \neq 1</math> のとき、<math>m, n</math> もある素数 <math>p</math> で割り切れるので定義より <math>p^2 \, | \, mn \Rightarrow \mu(mn) = 0</math> となる。よって 2 は容易に証明される。


<math>(m, n) = 1</math> のとき、どちらかが平方因子を持つならば <math>\mu(m) = 0 \vee \mu(n) = 0 \Rightarrow \mu(m)\mu(n) = 0</math> となる。また <math>mn</math> も平方因子を持つので、<math>\mu(mn) = 0</math>

<math>\therefore \mu(mn) = \mu(m)\mu(n).</math>

さて、どちらも平方因子を持たないとしよう。<math>m, n</math> がどちらも相異なる奇数個の素数の積のとき、<math>\mu(m) = \mu(n) = -1 \Rightarrow \mu(m)\mu(n) = 1.</math>

奇数に奇数を加えれば偶数なので、<math>mn</math> は相異なる偶数個の素数の積であり <math>\mu(mn) = 1.</math>

<math>\therefore \mu(mn) = \mu(m)\mu(n).</math>

<math>m, n</math> がどちらも相異なる偶数個の素数の積のとき、<math>\mu(m) = \mu(n) = 1 \Rightarrow \mu(m)\mu(n) = 1.</math>

偶数に偶数を加えれば偶数なので、<math>mn</math> は相異なる偶数個の素数の積であり <math>\mu(mn) = 1.</math>

<math>\therefore \mu(mn) = \mu(m)\mu(n).</math>

<math>m, n</math> が、片方は偶数個の相異なる素数の積でもう片方は奇数個の相異なる素数の積であったとしよう。どちらが奇数で偶数であったとしても同じなので、<math>m</math> が奇数、<math>n</math> が偶数としよう。すると <math>\mu(m) = -1, \mu(n) = 1 \Rightarrow \mu(m)\mu(n) = -1.</math>

偶数に奇数を加えれば奇数なので、<math>mn</math> は相異なる奇数個の素数の積であり <math>\mu(mn) = -1.</math>

<math>\therefore \mu(mn) = \mu(m)\mu(n).</math>

以上より 1 も証明された。


----

さて、メビウス関数はオイラーのφ関数と似た性質を持っていることに気づいただろうか。これには名前がついていて、数論的関数 <math>\psi</math> について

<math>\psi(1) = 1 \ \wedge \ (m, n) = 1 \Rightarrow \psi(mn) = \psi(m)\psi(n)</math> が成り立つとき、<math>\psi</math> は'''[[w:乗法的関数|乗法的関数]]'''である、という。

また数論的関数に限らず <math>(m, n) = 1</math> という条件なしに <math>\psi(mn) = \psi(m)\psi(n)</math> が成り立つとき、これを'''完全乗法的'''であるという。

'''例'''

指数関数 : <math>(mn)^k = m^k n^k</math>


類似として、<math>\psi(1) = 1 \ \wedge \ (m, n) = 1 \Rightarrow \psi(mn) = \psi(m) + \psi(n)</math> が成り立つとき、<math>\psi</math> は'''[[w:加法的関数|加法的関数]]'''である、という。同様に <math>(m, n) = 1</math> という条件なしに成り立つときこれを'''完全加法的'''であるという。

'''例'''

<math>log_n ab = log_n a + log_n b</math>

====== 定理 3.6 ======
<math>\sum_{d \, | \, n, d > 0}^{} \mu(n) = 0 \ \ (n > 1)</math>

'''証明'''<br />
<math>n = p_0^{a_0}p_1^{a_1} \cdots p_n^{a_n}</math> と因数分解する。<math>n</math> の約数の内平方因子を持つものは 0 なので平方因子を持たないもののみを考慮する。

素因数を一つも持たないのは <math>\mu(1) = 1</math> の 1 個。

素因数を1つ持つものは、<math>p_0, p_1, \cdots, p_n</math> の n 個。

素因数を2つ持つものは、n 個のうちから異なるものを順序を考慮せず2つ選ぶ組み合わせなので、<math>\binom{n}{2}</math> 個。

素因数を3つ持つものは、n 個のうちから異なるものを順序を考慮せず2つ選ぶ組み合わせなので、<math>\binom{n}{3}</math> 個。

よって総和は、

<math>\begin{align}
\sum_{d \, | \, n, d > 0}^{} \mu(n) & = 1 - n + \binom{n}{2} - \binom{n}{3} + \cdots + (-1)^n \binom{n}{n} \\
& = \binom{n}{0} - \binom{n}{1} + \binom{n}{2} - \binom{n}{3} + \cdots + (-1)^n \binom{n}{n} \\
& = (1-1)^k \\
& = 0
\end{align}</math>

となり、証明される。（二番目の式変形には[[初等整数論/パスカルの三角形#二項定理|二項定理]]を用いた）

====== 定理 3.7 ([[w:メビウスの反転公式]]) ======
<math>g(n) = \sum_{d \, | \, n, d > 0}^{} f(n)</math> とすれば、

<math>f(n) = \sum_{d \, | \, n, d > 0}^{} \mu \left( \frac{n}{d} \right) g(n)</math>

'''証明'''<br />
<math>\begin{align}
\sum_{d \, | \, n, d > 0}^{} \mu \left( \frac{n}{d} \right) g(n) & = \sum_{d \, | \, n, d > 0}^{} \left( \mu \left( \frac{n}{d} \right) \sum_{\delta \, | \, d, \delta > 0}^{} f( \delta ) \right) \\
& = \sum_{d \, | \, n, d > 0}^{} \left( \sum_{\delta \, | \, d, \delta > 0}^{} \mu \left( \frac{n}{d} \right) f( \delta ) \right) \ \cdots (1)
\end{align}</math>

ここで、<math>\delta \, | \, d \iff \delta k = d</math> である。また <math>d \, | \, n \iff dl = n</math> とおけば、<math>\frac{n}{d} = l</math>

<math>\frac{n}{\delta} = \frac{dl}{\delta} = \frac{\delta kl}{\delta} = kl</math>

よって <math>\frac{n}{d}</math> は <math>\frac{n}{\delta}</math> の約数。したがって <math>f( \delta )</math> をくくり出すことで

<math>(1) = \sum_{\delta \, | \, n}^{} f( \delta ) \left( \sum_{e \, | \frac{n}{ \delta }}^{} \mu(e) \right)</math>

定理 3.6 によって <math>\frac{n}{e} > 1</math> は全て消えるので、<math>\delta = n</math> だけが残り、<math>f(n) \mu(1) = f(n)</math> となり、証明は終わる。

'''系'''

<math>g(n) = n, f(n) = \varphi(n)</math> とし、

{{Nav}}

[[Category:初等整数論|すうろんてきかんすう]]