初等整数論/数論的関数
オイラーのφ関数

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

φ ( n ) = {\displaystyle \varphi (n)=} ( n 以下の自然数のうち n と互いに素な数の個数 )
オイラーのφ関数

より厳密に定義するならば、
オイラーのφ関数

ψ ( d , n ) = { 1 ( g c m ( d , n ) = 1 ) 0 ( o t h e r w i s e ) {\displaystyle \psi (d,n)={\begin{cases}1\ \ (\ gcm(d,n)=1\ )\\0\ \ (otherwise)\end{cases}}}
オイラーのφ関数

とし、 φ ( n ) = ∑ d = 1 n ψ ( d , n ) {\displaystyle \varphi (n)=\sum _{d=1}^{n}\psi (d,n)} とすればよい。このように、値が整数や自然数のときにしか意味を持たない関数を数論的関数という。広義には値が整数や自然数のときに意味を持つ関数をそう呼ぶ。
オイラーのφ関数

例
オイラーのφ関数

φ ( 1 ) = 1 { 1 } φ ( 2 ) = 1 { 1 } φ ( 3 ) = 2 { 1 , 2 } φ ( 4 ) = 2 { 1 , 3 } φ ( 5 ) = 4 { 1 , 2 , 3 , 4 } φ ( 6 ) = 2 { 1 , 5 } φ ( 7 ) = 6 { 1 , 2 , 3 , 4 , 5 , 6 } φ ( 8 ) = 4 { 1 , 3 , 5 , 7 } φ ( 9 ) = 6 { 1 , 2 , 4 , 5 , 7 , 8 } φ ( 10 ) = 4 { 1 , 3 , 7 , 9 } {\displaystyle {\begin{aligned}\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{aligned}}}
オイラーのφ関数

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

p {\displaystyle p} が素数のとき、
オイラーのφ関数

φ ( p ) = p − 1 ( { 1 , 2 , ⋯ , p − 1 } ) φ ( p n ) = p n − 1 ( p − 1 ) {\displaystyle {\begin{aligned}\varphi (p)&=p-1\ \ (\,\{1,2,\cdots ,p-1\}\,)\\\varphi (p^{n})&=p^{n-1}(p-1)\end{aligned}}}
オイラーのφ関数

第二の式について、互いに素でないものは 1 ⋅ p , 2 ⋅ p , ⋯ , p n − 1 p {\displaystyle 1\cdot p,2\cdot p,\cdots ,p^{n-1}p} の p n − 1 {\displaystyle p^{n-1}} 個であるから、 p n {\displaystyle p^{n}} から引いて p n − 1 {\displaystyle p^{n-1}} をくくりだして式を得る。
オイラーのφ関数

a , b {\displaystyle a,b} が互いに素ならば φ ( a b ) = φ ( a ) φ ( b ) {\displaystyle \varphi (ab)=\varphi (a)\varphi (b)}
オイラーのφ関数

証明 1 証明の前に、φ関数の意味を広げる。
オイラーのφ関数

n {\displaystyle n} は、 n {\displaystyle n} を法とするある類の任意の数 a {\displaystyle a} と一定の最大公約数を持つ。つまり、
オイラーのφ関数

( n , r ) = ( n , a + n t ) {\displaystyle (n,r)=(n,a+nt)} である。まずはこのことを証明しよう。
オイラーのφ関数

( n , a ) = 1 {\displaystyle (n,a)=1} とする。任意の自然数 t {\displaystyle t} について ( n , a + n t ) = 1 {\displaystyle (n,a+nt)=1} であることを証明する。
オイラーのφ関数

仮にある数 k {\displaystyle k} においてこれが成り立たず ( n , a + n k ) = d > 2 {\displaystyle (n,a+nk)=d>2} であるとする。仮定より n = d n ′ , a + n k = d a ′ {\displaystyle n=dn',a+nk=da'} とすれば、
オイラーのφ関数

( a + n k ) − n k = d n ′ − d a ′ ⟺ a = d ( n ′ − a ′ ) {\displaystyle (a+nk)-nk=dn'-da'\iff a=d(n'-a')} となり n , a {\displaystyle n,a} は公約数 d > 2 {\displaystyle d>2} を持つことになるが、これは矛盾である。
オイラーのφ関数

次に、 ( n , a ) = d > 2 {\displaystyle (n,a)=d>2} とする。仮定より、 n = d n ′′ , a = d a ′′ , ( n ′′ , a ′′ ) = 1 {\displaystyle n=dn'',a=da'',(n'',a'')=1} となる。
オイラーのφ関数

a + n t = d a ′′ + d n ′′ t = d ( a ′′ + n ′′ t ) {\displaystyle a+nt=da''+dn''t=d(a''+n''t)} となる。 ( n ′′ , a ′′ ) = 1 {\displaystyle (n'',a'')=1} なので、先ほど証明した互いに素の場合を適用して、 ( n ′′ , a ′′ + n ′′ t ) = 1 {\displaystyle (n'',a''+n''t)=1} となるので、 ( d n ′′ , d a ′′ + d n ′′ t ) = d ⟺ ( n , a + n t ) = d . {\displaystyle (dn'',da''+dn''t)=d\iff (n,a+nt)=d.}
オイラーのφ関数

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

さて、 a , b {\displaystyle a,b} は互いに素なので、定理 1.9 から、任意の数を a x + b y = k {\displaystyle ax+by=k} という形に表せる。 x , y {\displaystyle x,y} をそれぞれ b , a {\displaystyle b,a} の倍数だけ増減しても、それらは a b {\displaystyle ab} を法として合同である。そこで、 y {\displaystyle y} に a {\displaystyle a} を法とする類の a {\displaystyle a} 個の代表の元を与え、 x {\displaystyle x} に b {\displaystyle b} を法とする類の b {\displaystyle b} 個の代表の元を与えるときに、 a x + b y {\displaystyle ax+by} の式から出る a b {\displaystyle ab} 個の数は、 a b {\displaystyle ab} を法とした剰余系にならなければならない。
オイラーのφ関数

なぜかというと、同じ類の数を与えても a x + b y {\displaystyle ax+by} から出てくる数は同じ類に属すことは先ほどの通りで、逆に a x + b y {\displaystyle ax+by} から出てくる数が同じ類に属せば x , y {\displaystyle x,y} は同じ類に属すからである。後者については、出てくる数は a b {\displaystyle ab} 同じ類に属するので a x ′ + b y ′ = k , a x ′′ + b y ′′ = k + a b t {\displaystyle ax'+by'=k,ax''+by''=k+abt} と表せ、
オイラーのφ関数

a b t = a ( x ′ − x ′′ ) + b ( y ′ − y ′′ ) ⟺ b { a t − ( y ′ − y ′′ ) } = a ( x ′ − x ′′ ) {\displaystyle abt=a(x'-x'')+b(y'-y'')\iff b\{at-(y'-y'')\}=a(x'-x'')} となるので、 ( a , b ) = 1 {\displaystyle (a,b)=1} から、定理 1.6 より a t − ( y ′ − y ′′ ) {\displaystyle at-(y'-y'')} は a {\displaystyle a} の倍数だと分かる。したがって y − y ′ {\displaystyle y-y'} は a {\displaystyle a} の倍数、すなわち
オイラーのφ関数

y ′ ≡ y ′′ ( mod a ) {\displaystyle y'\equiv y''{\pmod {a}}} となる。同様にして
オイラーのφ関数

a b t = a ( x ′ − x ′′ ) + b ( y ′ − y ′′ ) ⟺ a { b t − ( x ′ − x ′′ ) } = b ( y ′ − y ′′ ) {\displaystyle abt=a(x'-x'')+b(y'-y'')\iff a\{bt-(x'-x'')\}=b(y'-y'')} として、 x ′ ≡ x ′′ ( mod b ) {\displaystyle x'\equiv x''{\pmod {b}}} が分かる。つまり、 a , b {\displaystyle a,b} をそれぞれ方とした類の組合わせと、 a b {\displaystyle ab} 法とした類は、 a x + b y {\displaystyle ax+by} によって一対一の対応ができている。
オイラーのφ関数

( x , b ) = 1 , ( y , a ) = 1 {\displaystyle (x,b)=1,(y,a)=1} とすれば、 ( a , b ) = 1 ⇒ ( a , b y ) = 1 ⇒ ( a , a x + b y ) = 1 {\displaystyle (a,b)=1\Rightarrow (a,by)=1\Rightarrow (a,ax+by)=1} となる(最後には冒頭で証明した事項を用いた)。
オイラーのφ関数

また同様にして ( b , a x + b y ) = 1 {\displaystyle (b,ax+by)=1} より、定理 1.13 から ( a b , a x + b y ) = 1 {\displaystyle (ab,ax+by)=1} となる。
オイラーのφ関数

以上によって、 x {\displaystyle x} に b {\displaystyle b} を法とした φ ( b ) {\displaystyle \varphi (b)} 個の既約剰余系の代表元、 y {\displaystyle y} に a {\displaystyle a} を法とした φ ( a ) {\displaystyle \varphi (a)} 既約剰余系の代表元、を与えれば、 a b {\displaystyle ab} を法とする φ ( a b ) {\displaystyle \varphi (ab)} 個の既約剰余系が得られるのだが、ここに一対一の対応ができているため、 φ ( a ) φ ( b ) = φ ( a b ) . {\displaystyle \varphi (a)\varphi (b)=\varphi (ab).}
オイラーのφ関数

証明 2 α 1 , α 2 , ⋯ , α m ( m = φ ( a ) ) , β 1 , β 2 , ⋯ , β n ( n = φ ( b ) ) {\displaystyle \alpha _{1},\alpha _{2},\cdots ,\alpha _{m}\ \ (\,m=\varphi (a)\,),\ \ \beta _{1},\beta _{2},\cdots ,\beta _{n}\ \ (\,n=\varphi (b)\,)} をそれぞれ a , b {\displaystyle a,b} を法としたときの既約剰余系とすれば、
オイラーのφ関数

α k , β l {\displaystyle \alpha _{k},\beta _{l}} の m n {\displaystyle mn} 個の組み合わせについて、 ( a , b ) = 1 {\displaystyle (a,b)=1} より中国の剰余定理から
オイラーのφ関数

{ γ ≡ α k ( mod a ) γ ≡ β l ( mod b ) {\displaystyle {\begin{cases}\gamma \equiv \alpha _{k}{\pmod {a}}\\\gamma \equiv \beta _{l}{\pmod {b}}\\\end{cases}}}
オイラーのφ関数

となる γ {\displaystyle \gamma } が a b {\displaystyle ab} を法としてただひとつ存在する。
オイラーのφ関数

γ ≡ α k ( mod a ) {\displaystyle \gamma \equiv \alpha _{k}{\pmod {a}}} より、 γ = α k + a t {\displaystyle \gamma =\alpha _{k}+at} となる。 ( a , γ ) = ( a , α k + a t ) {\displaystyle (a,\gamma )=(a,\alpha _{k}+at)}
オイラーのφ関数

ここで、証明 1 の冒頭に証明されたことから、 ( a , α k + a t ) = ( a , α ) = 1 {\displaystyle (a,\alpha _{k}+at)=(a,\alpha )=1} となり、つまり ( a , γ ) = 1. {\displaystyle (a,\gamma )=1.}
オイラーのφ関数

同様に ( b , γ ) = 1 {\displaystyle (b,\gamma )=1} したがって定理 1.13 より ( a b , γ ) = 1. {\displaystyle (ab,\gamma )=1.}
オイラーのφ関数

逆に、 ( γ , a b ) = 1 {\displaystyle (\gamma ,ab)=1} とすれば、 ( γ , a ) = 1 , ( γ , b ) = 1 {\displaystyle (\gamma ,a)=1,(\gamma ,b)=1} より、
オイラーのφ関数

{ γ ≡ α ( mod a ) γ ≡ β ( mod b ) {\displaystyle {\begin{cases}\gamma \equiv \alpha {\pmod {a}}\\\gamma \equiv \beta {\pmod {b}}\\\end{cases}}}
オイラーのφ関数

なる α , β {\displaystyle \alpha ,\beta } がただひとつ定まる。つまり、 a b {\displaystyle ab} を法とする既約剰余系は a {\displaystyle a} を法とする既約剰余系と b {\displaystyle b} を法とする既約剰余系の組み合わせと一対一対応ができている。すなわち、
オイラーのφ関数

φ ( a b ) = φ ( a ) φ ( b ) . {\displaystyle \varphi (ab)=\varphi (a)\varphi (b).}
オイラーのφ関数

( a , n ) = 1 {\displaystyle (a,n)=1} としたときに
オイラーのφ関数

a φ ( n ) ≡ 1 ( mod n ) {\displaystyle a^{\varphi (n)}\equiv 1{\pmod {n}}}
オイラーのφ関数

証明 φ {\displaystyle \varphi } 関数は既約剰余系の数を表す関数だった。ここで x 1 , x 2 , ⋯ , x φ ( n ) {\displaystyle x_{1},x_{2},\cdots ,x_{\varphi (n)}} を既約剰余系とおく。このとき、 ( a , n ) = 1 {\displaystyle (a,n)=1} より a x 1 , a x 2 , ⋯ , a x φ ( n ) ⋯ ( 1 ) {\displaystyle ax_{1},ax_{2},\cdots ,ax_{\varphi (n)}\cdots (1)} は n {\displaystyle n} で割り切れない。
オイラーのφ関数

a x k ≡ a x l ⇒ x k ≡ x l ( mod n ) {\displaystyle ax_{k}\equiv ax_{l}\Rightarrow x_{k}\equiv x_{l}{\pmod {n}}} である。対偶をとって x k ≢ x l ⇒ a x k ≡ a x l ( mod n ) {\displaystyle x_{k}\not \equiv x_{l}\Rightarrow ax_{k}\equiv ax_{l}{\pmod {n}}}
オイラーのφ関数

よって (1) は既約剰余系をなす。
オイラーのφ関数

よってどちらも合同な一対一対応ができるので、全てをかけ合わせて
オイラーのφ関数

a x 1 a x 2 ⋯ a x φ ( n ) ≡ x 1 x 2 ⋯ x φ ( n ) ( mod n ) {\displaystyle ax_{1}\,ax_{2}\cdots ax_{\varphi (n)}\equiv x_{1}\,x_{2}\cdots x_{\varphi (n)}{\pmod {n}}}
オイラーのφ関数

x 1 , x 2 , ⋯ , x φ ( n ) {\displaystyle x_{1},x_{2},\cdots ,x_{\varphi (n)}} は既約剰余系なので
オイラーのφ関数

a φ ( n ) ( mod 1 ) ( mod m ) {\displaystyle a^{\varphi (n)}{\pmod {1}}{\pmod {m}}} となり目的の式を得た。
オイラーのφ関数

a = p 0 a 0 p 1 a 1 ⋯ p n a n {\displaystyle a=p_{0}^{a_{0}}p_{1}^{a_{1}}\cdots p_{n}{a_{n}}} と素因数分解したとき、
オイラーのφ関数

φ ( a ) = a ( 1 − 1 p 0 ) ( 1 − 1 p 1 ) ⋯ ( 1 − 1 p n ) {\displaystyle \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)}
オイラーのφ関数

証明 φ ( a ) = φ ( p 0 a 0 p 1 a 1 ⋯ p n a n ) ⋯ ( 1 ) {\displaystyle \varphi (a)=\varphi (p_{0}^{a_{0}}p_{1}^{a_{1}}\cdots p_{n}{a_{n}})\cdots (1)}
オイラーのφ関数

ここで、 p 0 a 0 , p 1 a 1 ⋯ p n a n {\displaystyle p_{0}^{a_{0}},p_{1}^{a_{1}}\cdots p_{n}{a_{n}}} は同じ素因数を持たず互いに素なので、定理 3.1 より、
オイラーのφ関数

( 1 ) ⟺ φ ( a ) = φ ( p 0 a 0 ) φ ( p 1 a 1 ⋯ p n a n ) {\displaystyle (1)\iff \varphi (a)=\varphi (p_{0}^{a_{0}})\varphi (p_{1}^{a_{1}}\cdots p_{n}{a_{n}})} となる。これを繰り返し行えば、
オイラーのφ関数

φ ( a ) = φ ( p 0 a 0 ) φ ( p 1 a 1 ) ⋯ φ ( p n a n ) = ( p 0 a 0 − p 0 a 0 − 1 ) ( p 1 a 1 − p 1 a 1 − 1 ) ⋯ ( p n a n − p n a n − 1 ) = p 0 a 0 p 1 a 1 ⋯ p n a n ( 1 − 1 p 0 ) ( 1 − 1 p 1 ) ⋯ ( 1 − 1 p n ) = a ( 1 − 1 p 0 ) ( 1 − 1 p 1 ) ⋯ ( 1 − 1 p n ) {\displaystyle {\begin{aligned}\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{aligned}}}
オイラーのφ関数

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

ある数 n {\displaystyle n} とその1つの約数を d 0 {\displaystyle d_{0}} とおき、 n {\displaystyle n} 以下の数のうち、最大公約数が d 0 {\displaystyle d_{0}} であるものの個数について考慮しよう。任意の数 k ≦ n {\displaystyle k\leqq n} をおき、 ( n , k ) = d 0 {\displaystyle (n,k)=d_{0}} となるような自然数 k {\displaystyle k} の個数である。
オイラーのφ関数

n = d 0 n ′ , k = d 0 k ′ {\displaystyle n=d_{0}n',\,k=d_{0}k'} としたときに、 k ′ ≦ n ′ , ( n ′ , k ′ ) = 1 {\displaystyle k'\leqq n',\,(n',k')=1} である。
オイラーのφ関数

逆に、 k ′ ≦ n ′ , ( n ′ , k ′ ) = 1 {\displaystyle k'\leqq n',\,(n',k')=1} ならば、 n = d 0 n ′ , k = d 0 k ′ {\displaystyle n=d_{0}n',\,k=d_{0}k'} であるから k ≦ n , ( n , k ) = d 0 {\displaystyle k\leqq n,\,(n,k)=d_{0}} である。つまり、最大公約数が d 0 {\displaystyle d_{0}} となるような数の個数は φ ( n d 0 ) {\displaystyle \varphi \left({\frac {n}{d_{0}}}\right)} なのである。
オイラーのφ関数

n {\displaystyle n} の約数を、 A = { 1 , d 0 , d 1 , ⋯ , d m , n } {\displaystyle A=\{1,d_{0},d_{1},\cdots ,d_{m},n\}} とおくと、 n {\displaystyle n} 以下の任意の数 k {\displaystyle k} について、 n {\displaystyle n} との最大公約数は A {\displaystyle A} に含まれる数のうちのどれかである。すなわち、
オイラーのφ関数

n = φ ( n 1 ) + φ ( n d 0 ) + ⋯ + φ ( n d m ) + φ ( n n ) ⟺ n = ∑ d | n , d > 0 φ ( d ) {\displaystyle {\begin{aligned}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{aligned}}}
オイラーのφ関数

∑ d | n , d > 0 {\displaystyle \sum _{d\,|\,n,d>0}^{}} というのは、 n {\displaystyle n} で割り切れる全ての正の数についての和という意味である。以上より、次の定理を導いた。
オイラーのφ関数

n = ∑ d | n , d > 0 φ ( d ) {\displaystyle n=\sum _{d\,|\,n,d>0}^{}\varphi (d)}
オイラーのφ関数

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

定義
メビウス関数

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

証明 ( m , n ) ≠ 1 {\displaystyle (m,n)\neq 1} のとき、 m , n {\displaystyle m,n} もある素数 p {\displaystyle p} で割り切れるので定義より p 2 | m n ⇒ μ ( m n ) = 0 {\displaystyle p^{2}\,|\,mn\Rightarrow \mu (mn)=0} となる。よって 2 は容易に証明される。
メビウス関数

( m , n ) = 1 {\displaystyle (m,n)=1} のとき、どちらかが平方因子を持つならば μ ( m ) = 0 ∨ μ ( n ) = 0 ⇒ μ ( m ) μ ( n ) = 0 {\displaystyle \mu (m)=0\vee \mu (n)=0\Rightarrow \mu (m)\mu (n)=0} となる。また m n {\displaystyle mn} も平方因子を持つので、 μ ( m n ) = 0 {\displaystyle \mu (mn)=0}
メビウス関数

∴ μ ( m n ) = μ ( m ) μ ( n ) . {\displaystyle \therefore \mu (mn)=\mu (m)\mu (n).}
メビウス関数

さて、どちらも平方因子を持たないとしよう。 m , n {\displaystyle m,n} がどちらも相異なる奇数個の素数の積のとき、 μ ( m ) = μ ( n ) = − 1 ⇒ μ ( m ) μ ( n ) = 1. {\displaystyle \mu (m)=\mu (n)=-1\Rightarrow \mu (m)\mu (n)=1.}
メビウス関数

奇数に奇数を加えれば偶数なので、 m n {\displaystyle mn} は相異なる偶数個の素数の積であり μ ( m n ) = 1. {\displaystyle \mu (mn)=1.}
メビウス関数

∴ μ ( m n ) = μ ( m ) μ ( n ) . {\displaystyle \therefore \mu (mn)=\mu (m)\mu (n).}
メビウス関数

m , n {\displaystyle m,n} がどちらも相異なる偶数個の素数の積のとき、 μ ( m ) = μ ( n ) = 1 ⇒ μ ( m ) μ ( n ) = 1. {\displaystyle \mu (m)=\mu (n)=1\Rightarrow \mu (m)\mu (n)=1.}
メビウス関数

偶数に偶数を加えれば偶数なので、 m n {\displaystyle mn} は相異なる偶数個の素数の積であり μ ( m n ) = 1. {\displaystyle \mu (mn)=1.}
メビウス関数

∴ μ ( m n ) = μ ( m ) μ ( n ) . {\displaystyle \therefore \mu (mn)=\mu (m)\mu (n).}
メビウス関数

m , n {\displaystyle m,n} が、片方は偶数個の相異なる素数の積でもう片方は奇数個の相異なる素数の積であったとしよう。どちらが奇数で偶数であったとしても同じなので、 m {\displaystyle m} が奇数、 n {\displaystyle n} が偶数としよう。すると μ ( m ) = − 1 , μ ( n ) = 1 ⇒ μ ( m ) μ ( n ) = − 1. {\displaystyle \mu (m)=-1,\mu (n)=1\Rightarrow \mu (m)\mu (n)=-1.}
メビウス関数

偶数に奇数を加えれば奇数なので、 m n {\displaystyle mn} は相異なる奇数個の素数の積であり μ ( m n ) = − 1. {\displaystyle \mu (mn)=-1.}
メビウス関数

∴ μ ( m n ) = μ ( m ) μ ( n ) . {\displaystyle \therefore \mu (mn)=\mu (m)\mu (n).}
メビウス関数

以上より 1 も証明された。
メビウス関数

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

ψ ( 1 ) = 1 ∧ ( m , n ) = 1 ⇒ ψ ( m n ) = ψ ( m ) ψ ( n ) {\displaystyle \psi (1)=1\ \wedge \ (m,n)=1\Rightarrow \psi (mn)=\psi (m)\psi (n)} が成り立つとき、 ψ {\displaystyle \psi } は乗法的関数である、という。
メビウス関数

また数論的関数に限らず ( m , n ) = 1 {\displaystyle (m,n)=1} という条件なしに ψ ( m n ) = ψ ( m ) ψ ( n ) {\displaystyle \psi (mn)=\psi (m)\psi (n)} が成り立つとき、これを完全乗法的であるという。
メビウス関数

例
メビウス関数

指数関数 : ( m n ) k = m k n k {\displaystyle (mn)^{k}=m^{k}n^{k}}
メビウス関数

類似として、 ψ ( 1 ) = 1 ∧ ( m , n ) = 1 ⇒ ψ ( m n ) = ψ ( m ) + ψ ( n ) {\displaystyle \psi (1)=1\ \wedge \ (m,n)=1\Rightarrow \psi (mn)=\psi (m)+\psi (n)} が成り立つとき、 ψ {\displaystyle \psi } は加法的関数である、という。同様に ( m , n ) = 1 {\displaystyle (m,n)=1} という条件なしに成り立つときこれを完全加法的であるという。
メビウス関数

例
メビウス関数

l o g n a b = l o g n a + l o g n b {\displaystyle log_{n}ab=log_{n}a+log_{n}b}
メビウス関数

∑ d | n , d > 0 μ ( n ) = 0 ( n > 1 ) {\displaystyle \sum _{d\,|\,n,d>0}^{}\mu (n)=0\ \ (n>1)}
メビウス関数

証明 n = p 0 a 0 p 1 a 1 ⋯ p n a n {\displaystyle n=p_{0}^{a_{0}}p_{1}^{a_{1}}\cdots p_{n}^{a_{n}}} と因数分解する。 n {\displaystyle n} の約数の内平方因子を持つものは 0 なので平方因子を持たないもののみを考慮する。
メビウス関数

素因数を一つも持たないのは μ ( 1 ) = 1 {\displaystyle \mu (1)=1} の 1 個。
メビウス関数

素因数を1つ持つものは、 p 0 , p 1 , ⋯ , p n {\displaystyle p_{0},p_{1},\cdots ,p_{n}} の n 個。
メビウス関数

素因数を2つ持つものは、n 個のうちから異なるものを順序を考慮せず2つ選ぶ組み合わせなので、 ( n 2 ) {\displaystyle {\binom {n}{2}}} 個。
メビウス関数

素因数を3つ持つものは、n 個のうちから異なるものを順序を考慮せず2つ選ぶ組み合わせなので、 ( n 3 ) {\displaystyle {\binom {n}{3}}} 個。
メビウス関数

よって総和は、
メビウス関数

∑ d | n , d > 0 μ ( n ) = 1 − n + ( n 2 ) − ( n 3 ) + ⋯ + ( − 1 ) n ( n n ) = ( n 0 ) − ( n 1 ) + ( n 2 ) − ( n 3 ) + ⋯ + ( − 1 ) n ( n n ) = ( 1 − 1 ) k = 0 {\displaystyle {\begin{aligned}\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{aligned}}}
メビウス関数

となり、証明される。(二番目の式変形には二項定理を用いた)
メビウス関数

g ( n ) = ∑ d | n , d > 0 f ( n ) {\displaystyle g(n)=\sum _{d\,|\,n,d>0}^{}f(n)} とすれば、
メビウス関数

f ( n ) = ∑ d | n , d > 0 μ ( n d ) g ( n ) {\displaystyle f(n)=\sum _{d\,|\,n,d>0}^{}\mu \left({\frac {n}{d}}\right)g(n)}
メビウス関数

証明 ∑ d | n , d > 0 μ ( n d ) g ( n ) = ∑ d | n , d > 0 ( μ ( n d ) ∑ δ | d , δ > 0 f ( δ ) ) = ∑ d | n , d > 0 ( ∑ δ | d , δ > 0 μ ( n d ) f ( δ ) ) ⋯ ( 1 ) {\displaystyle {\begin{aligned}\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{aligned}}}
メビウス関数

ここで、 δ | d ⟺ δ k = d {\displaystyle \delta \,|\,d\iff \delta k=d} である。また d | n ⟺ d l = n {\displaystyle d\,|\,n\iff dl=n} とおけば、 n d = l {\displaystyle {\frac {n}{d}}=l}
メビウス関数

n δ = d l δ = δ k l δ = k l {\displaystyle {\frac {n}{\delta }}={\frac {dl}{\delta }}={\frac {\delta kl}{\delta }}=kl}
メビウス関数

よって n d {\displaystyle {\frac {n}{d}}} は n δ {\displaystyle {\frac {n}{\delta }}} の約数。したがって f ( δ ) {\displaystyle f(\delta )} をくくり出すことで
メビウス関数

( 1 ) = ∑ δ | n f ( δ ) ( ∑ e | n δ μ ( e ) ) {\displaystyle (1)=\sum _{\delta \,|\,n}^{}f(\delta )\left(\sum _{e\,|{\frac {n}{\delta }}}^{}\mu (e)\right)}
メビウス関数

定理 3.6 によって n e > 1 {\displaystyle {\frac {n}{e}}>1} は全て消えるので、 δ = n {\displaystyle \delta =n} だけが残り、 f ( n ) μ ( 1 ) = f ( n ) {\displaystyle f(n)\mu (1)=f(n)} となり、証明は終わる。
メビウス関数

系
メビウス関数

g ( n ) = n , f ( n ) = φ ( n ) {\displaystyle g(n)=n,f(n)=\varphi (n)} とし、