eulerPhi

オイラーのファイ関数

構文

p = eulerPhi(n)

説明

p = eulerPhi(n) は正の整数 n に対するオイラーのファイ関数 (トーシェント関数とも呼ばれる) を評価します。

例

オイラーのファイ関数の乗法的性質

整数 $$n=35$$ に対するオイラーのファイ関数 $$\varphi (n)$$ を計算します。

p = eulerPhi(35)

p = 
24

オイラーのファイ関数は 2 つの整数 $$x$$ と $$y$$ が互いに素である場合に乗法的性質 $$\varphi (xy)=\varphi (x)\varphi (y)$$ を満たします。整数 35 の因数分解は 7 と 5 であり、これらは互いに素です。$$\varphi (35)$$ が乗法的性質を満たすことを示します。

この 2 つの因数分解について $$\varphi (x)$$ と $$\varphi (y)$$ を計算します。

px = eulerPhi(7)

px = 
6

py = eulerPhi(5)

py = 
4

px と py が乗法的性質を満たしているか検証します。

p = px*py

p = 
24

オイラーの積公式

正の整数 $$n$$ が異なる素因数 $$p_1,p_2,\dots ,p_r$$ をもつ素因数分解 $$n=p_1^{k_1}{p}_2^{k_2}\dots p_r^{k_r}$$ をもつ場合、オイラーのファイ関数は次の積公式を満たします。

$$\varphi (n)=n(1-\frac{1}{p_1})(1-\frac{1}{p_2})\dots (1-\frac{1}{p_r})$$.

整数 $$n=36$$ は異なる素因数 $$2$$ と $$3$$ をもちます。$$\varphi (36)$$ がオイラーの積公式を満たすことを示します。

$$36$$ をシンボリック数として宣言し、$$\varphi (36)$$ を評価します。

n = sym(36)

n = $$36$$

p = eulerPhi(n)

p = $$12$$

$$36$$ の素因数をリストにします。

f_n = factor(n)

f_n = $$\left(\begin{array}{cccc}2& 2& 3& 3\end{array}\right)$$

素因数 $$2$$ と $$3$$ を積公式に代入します。

p_product = n*(1-1/2)*(1-1/3)

p_product = $$12$$

オイラーの定理

オイラーの定理は、2 つの正の整数 $$a$$ と $$n$$ が互いに素である場合に限り $$a^{\varphi (n)}\equiv 1(modn)$$ が成り立つとするものです。整数 $$a=15$$ と $$n=4$$ について、オイラーのファイ関数 $$\varphi (n)$$ がオイラーの定理を満たすことを示します。

a = 15;
n = 4;
isCongruent = powermod(a,eulerPhi(n),n) == mod(1,n)

isCongruent = logical
   1

a と n が互いに素であることを確認します。

g = gcd(a,n)

g = 
1

オイラーのファイ関数の結果の平均値

1 から 1000 の整数 $$n$$ について、オイラーのファイ関数 $$\varphi (n)$$ を計算します。

P = eulerPhi(1:1000);

$$\varphi (n)/n$$ の平均値を求めます。

Pave = mean(P./(1:1000))

Pave = 
0.6082

入力引数

n — 入力

数値 | ベクトル | 行列 | 配列 | シンボリック数 | シンボリック配列

入力。数値、ベクトル、行列、配列、シンボリック数またはシンボリック配列として指定します。n の要素は正の整数でなければなりません。

データ型: single | double | sym

詳細

オイラーのファイ関数

オイラーのファイ関数 $$\varphi (n)$$ は n に対して互いに素である 1 から n までの整数の数を計算します。互いに割り切る 1 より大きい整数がない場合、2 つの整数は互いに素です。言い換えれば、その最大公約数が 1 の場合です。

参照

[1] Redmond, D. Number Theory: An Introduction to Pure and Applied Mathematics. New York: Marcel Dekker, 1996.

バージョン履歴

R2020a で導入

参考

isprime | primes