オイラー関数

オイラー関数を講義でしたのでメモ書き。

でもその前に、TeX練習

$\varphi(42) = 42(1 - \frac{1}{2})(1 - \frac{1}{3})(1 - \frac{1}{7})\\=42(\frac{1}{2})(\frac{2}{3})(\frac{6}{7})\\ = \cancel{42}^{{\cancel{21}}^{\cancel{7}}} (\frac{1}{\cancel{2}})(\frac{2}{\cancel{3}})(\frac{6}{\cancel{7}})\\ = 12$

1と2、互いに素な整数は {1} の1つ
2以下の整数と3、互いに素な整数は {1,2} の2つ
3以下の整数と4、互いに素な整数は {1,3} の2つ
4以下の整数と5、互いに素な整数は {1,2,3,4} の4つ
5以下の整数と6、互いに素な整数は {1,5} の2つ
6以下の整数と7、互いに素な整数は {1,2,3,4,5,6} の6つ
...

となる。

ここである数 n があるとする。
$n = p_{1}^{m1} p_{2}^{m2} ... p_{j}^{mj}$
となる。(p1,p2,...,pj)は素数とする。
するとnは
$n = \prod_{k=1}^{j}p_{k}^{mj}$
になる。

nと、n-1以下の整数と互いに素な整数の数を知るばあいは、nが素数の場合 (n -1) ですぐにわかる。

$\varphi(n) = n - 1$

nがa,bに因数分解でき、かつa,bがともに素数の場合だと、
$\varphi(ab) = \varphi(a) \varphi(b) \\ = ab \left(\frac{a-1}{a}\right)\left(\frac{b-1}{a}\right) \\ = (a-1)(b-1)$
となる。

さらに、一般形？では、
$\varphi(n) = n \prod_{k=1}^{j} \left( 1 - \frac{1}{p_{j}} \right)$
となる。

何かまだ突っ込めばもっとあるみたい。つっこも。

at_yasu's blog

ロード的なことを