元祖ワシ的日記

wikipediaより

オイラーのトーシェント関数（オイラーのトーシェントかんすう、英: Euler's totient function）は各正の整数 n に対して、1 から n までの自然数のうち n と互いに素なものの個数を φ(n) として与えることによって定まる数論的関数 φ である。慣例的に φ(n) と表記されるため、オイラーの φ 関数（ファイかんすう、phi function）とも呼ばれる。また、簡略的にオイラーの関数と呼ぶこともある。

計算方法概略

簡単にするためまず$n$の素因数分解を$p_1 p_2 p_3 \cdots p_n$とし因子に平方数を含まないとします。 (つまり素数 $p_1, p_2, p_3, \cdots$の羃は1)

$1$から$n$のうち$p_1$の倍数の数が $n / p_1$個あり、 $p_2$の倍数が $n / p_2$あり……ということでこれらの数を$n$から引きます。しかし、これでは $p_1 p_2$など2つの素数の積の数を2回引いてしまうのでそれらを足します。しかし、これでは $p_1 p_2 p_3$のような3つの素数の積になってる数を足しすぎてしまうのでそれらをまた引きます……と考えていけば……

例

平方数を含む場合ですが例えば $12$のときを考えれば$2$の倍数を除去したときに12の因数である$4$の倍数は既に除去されています。つまり、平方因子をもつ約数は考慮しなくてもよいのです。（つまり、素因数が何種類あるか？が重要）これはそのまま一般に拡張出来ます。実際上記の式は $n$の素因数分解を$p_1^{e_1} p_2^{e_2} p_3^{e_3} \cdots p_n^{e_n}$と分解される場合でも成立します。

$n = p_1^{e_1} p_2^{e_2} p_3^{e_3} \cdots p_n^{e_n}$の素因数をそれぞれの項に配分していけば

なお、上記の式はメビウス関数を使えば $$\begin{eqnarray} \phi(n) = \sum_{d|n}\mu({d}){\frac{n}{d}} \end{eqnarray}$$ とも表わすことができます。メビウス関数$\mu({n})$は

• $n$が平方因数を含む場合は$\mu({n})=0$
• $n$が因数を偶数個含む場合は$\mu({n})=1$
• $n$が因数を奇数個含む場合は$\mu({n})=-1$

ここからメビウスの反転公式を使って

以上Mathjaxのリハビリでした

相当前にエントリに書いた$4n+1$の素数を平方の和にするアルゴリズムですがガウス整数を使ったもっとスマートな解法を紹介します。

まず前回同様 $p$を$4n+1$の素数として $$A^2 + 1 = 0 (\mod p)$$ なる$A$を求めます。

$$A^2 + 1 = k p$$ です。

左辺はガウス整数を使うとさらに因数分解できて $$(A + i)(A - i) = k p$$ となります。

ここでガウス整数は通常の整数と同様、素因数分解等素数の性質があることを踏まえて等式を見てみます。

$p$はあきらかに$A+i$および$A-i$を割きりません。ということは$p$はガウス整数の世界ではさらなる素数に分解できることを意味します。すなわち最大公約数$(A+i, p)$は1ではなく、$x+iy$の形をしたガウス整数となります。

$(A+i, p) = x + iy$ ならば共役の関係から $(A-i, p) = x - iy$がまた成立します。 一方$(x + iy)(x - iy)$を考えるとこれは有理整数$x^2+y^2$となりこれは$p$を割り切らないといけませんが、 $p$は素数ですから結局これは$p$に等しく$p = x^2 + y^2$となります。

つまり$p$と$A+i$の最大公約数を求めればそこから解は自動的に求まることになります。

最大公約数はガウス整数の世界でもユークリッドの互除法で簡単に求めることができます。

例として、素数$p=120710677$を二つの和にしてみます

$$46505545^2 + 1^2 = 17916938 \times 120710677$$

ですから最初は$46505545+i$と$120710677$の最大公約数を求めればよいことになります。

$$A_0 = 46505545+i\\ B_0 = 120710677$$ とします。

ノルムを比較すると$|A_0| < |B_0|$で $A_0 = 3 * |B_0| + ...$ ですから最初の計算では $A_1 = A_0, B_1 = B_0 - 3A_0$とすればよいことがわかります。 実際計算してみると $$A_1 = 46505545+i\\ B_1 = -18805958-3i$$ となります。以下同様にして計算していくと

$$\begin{align} A_2&=&8893629-5i, B_2&=&-18805958-3i\\ A_3&=&8893629-5i, B_3&=&-1018700-13i\\ A_4&=&-274671-122i, B_4&=&-1018700-13i\\ A_5&=&-274671-122i, B_5&=&79984+475i\\ A_6&=&-34719+1303i, B_6&=&79984+475i\\ A_7&=&-34719+1303i, B_7&=&10546+3081i \end{align}$$ ここで$B_7$が求める答えになります。実際 $$10546^2+3081^2 = 120710677$$ です

注意

ユークリッドの互除法ではノルムの大きいほうをノルムの小さいほうで割ってその余りに置き換えるという手順を踏むのですが、それは以下のようにして求めます。

$a+ib$を$c+id$で割る場合は $$\frac{a+ib}{c+id} = \frac{(a+ib)(c-id)}{c^2+d^2} = \frac{ac+bd}{c^2+d^2} + \frac{bc-ad}{c^2+d^2}i$$ ここで、有理数 $$\frac{ac+bd}{c^2+d^2}, \frac{bc-ad}{c^2+d^2}$$ に最も近い整数を$n$, $m$とすれば $$(a+ib) = (n+im)(c+id) + (r+is)$$ と書いたときに、$r+is$のノルムは$c+id$より小さくなります。よって$r+is$を余りとみなして計算を進めていくことができます。

別の考察

この例では$(A+i, p)$を考えましたが、$(A+i, k)$を考えても同様に計算をすることができることがわかります。

$$a^2 + b^2 = 0 (\mod k)$$ であることを考えると $a' = a(\mod k), b' = b(\mod k)$とおけば $$a'^2 + b'^2 = 0 (\mod k)$$ もまた成立します。つまり$a'^2 + b'^2$は$k$を割りきります。つまり $$\frac{(a+ib)(a-ib)}{(a'+ib')(a'-ib')} = \frac{k}{a'^2 + b'^2}p = k'p$$ が成立します。右辺は整数ですから左辺は共役なガウス整数の積にならなければなりません。 よって $$\frac{a+ib}{a'+ib'}または\frac{a+ib}{a'-ib'}$$ のどちらかがガウス整数になります。ここで $$\begin{align} -k/2 &<& a' &<& k/2\\ -k/2 &<& b' &<& k/2 \end{align}$$ なるように a', b'を選べば kより小さい k'が見つかることになります。 この手順を繰替えせば kより始めていつかは1になるので求める解を見付けることができます。

これが前回解説したアルゴリズムと同じものになります。

さらりと流した部分の補足

有理整数がガウス整数の積で表わされる必要条件は共役の因子を含むことである。

ガウス整数をそれぞれ $a+ib$と$c+id$とする。$c\ne 0$, $d\ne 0$, $(a,b)=1, (c,d)=1$と仮定して問題ない。 なぜならもし$(a,b)=k > 1$ならば$a' = a/k, b' = b/k$として $k(a' + ib')(c+id)$を考えればよいからである。 $$(a+ib)(c+id) = (ac-bd) + i(ad+bc)$$ が有理整数なのだから$ad+bc=0$すなわち $ad=-bc$が成立する。 よって、$a$と$b$と互いに素だから$c$が$d$を割り切りかつ$d$が$c$を割きらなければならないが、 これは $c=d$または$c=-d$を意味する。$c=d$とすれば$a=-b$であり$c=-d$とすれば $a=b$である。 いずれにしても共役の因子を含まなくてはならない。

有理整数が共役の数の積で表わされているのなら、その数はガウス整数でなければならない。

$a/b$および$c/d$を考える。$(a,b)=1, (c,d)=1$と仮定して問題ない $$(\frac{a}{b}+i\frac{c}{d})(\frac{a}{b}-i\frac{c}{d}) = \frac{a^2c^2}{b^2d^2}$$ から $$b^2d^2 = 1$$ これは$b=\pm 1, d=\pm 1$を意味する。