印度亭
sukarabe＠携帯 個数に関する帰納法
sukarabe ふと，次の定理の帰納法による証明は，所謂「個数に関する帰納法」のとても良い例ではないかと思った。
自然数$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)\]
と表される。
もちろん，組合せ論で定番の包除原理でも証明できるし，数論的な証明もあるが，素因数の個数に関する帰納法による証明もすっきりしている。