nを法とする単位根

整数論において、正の整数k（n  ≥ 2 ）に対するnを法とするk乗根は、nを法とする整数環における単位根、すなわち方程式（または合同式）の解xである。kがxのそのような最小の指数である場合、x はnを法とする原始k乗根と呼ばれる。^[1]表記法と用語についてはモジュラー算術を参照。 ${\displaystyle x^{k}\equiv 1{\pmod {n}}}$

nを法とする単位根は、 nと互いに素な整数です。実際、これらの整数はオイラーの定理によりnを法とする単位根であり、その他の整数は n を法とする零約数であるため、nを法とする単位根にはなり得ません。

nを法とする原始根は、 nを法とする整数環の単位群の生成元である。nを法とする原始根が存在する場合、かつその場合のみ、となる。ここで、 とはそれぞれカーマイケル関数とオイラーのトーシェント関数である。^{[説明が必要]} ${\displaystyle \lambda (n)=\varphi (n),}$ ${\displaystyle \lambda }$ ${\displaystyle \varphi }$

nを法とする単位根は、ある約数kに対してnを法とする原始k乗単位根であり、逆に、kが約数である場合に限り、nを法とする原始k乗単位根が存在する。 ${\displaystyle \lambda (n),}$ ${\displaystyle \lambda (n).}$

団結の根源

プロパティ

• x がnを法とするk乗根である場合、xは 1 乗根（逆根）であり、その逆根は である。つまり、xとnは互いに素である。 ${\displaystyle x^{k-1}}$
• x が単位元である場合、それはnを法とするk乗根 (原始) です。ここで、kはnを法とするxの乗法次数です。
• xがk乗根で零因子でない場合、 ${\displaystyle x-1}$ ${\displaystyle \sum _{j=0}^{k-1}x^{j}\equiv 0{\pmod {n}}}$

${\displaystyle (x-1)\cdot \sum _{j=0}^{k-1}x^{j}\equiv x^{k}-1\equiv 0{\pmod {n}}.}$

数けth ルート

広く受け入れられている記号がないため、nを法とするk乗根の個数を と表記する。これはいくつかの性質を満たす。 ${\displaystyle f(n,k)}$

• ${\displaystyle f(n,1)=1}$のために ${\displaystyle n\geq 2}$
• ${\displaystyle f(n,\lambda (n))=\varphi (n)}$ここでλはカーマイケル関数、はオイラーのトーシェント関数を表す。 ${\displaystyle \varphi }$
• ${\displaystyle n\mapsto f(n,k)}$乗法関数である
• ${\displaystyle k\mid \ell \implies f(n,k)\mid f(n,\ell )}$バーは割り切れることを示す
• ${\displaystyle f(n,\operatorname {lcm} (a,b))=\operatorname {lcm} (f(n,a),f(n,b))}$ここで最小公倍数を表す ${\displaystyle \operatorname {lcm} }$
• 素数 の場合、からへの正確な写像は未知である。もしそれが既知であれば、前の法則と合わせて迅速に評価する方法が得られるであろう。 ${\displaystyle p}$ ${\displaystyle \forall i\in \mathbb {N} \ \exists j\in \mathbb {N} \ f(n,p^{i})=p^{j}}$ ${\displaystyle i}$ ${\displaystyle j}$ ${\displaystyle f}$

例

ととします。この場合、1 の立方根は 3 つ（1、2、4）あります。しかし、 の場合は、1 の立方根は 1 つ、つまり 1 自身だけです。この振る舞いは、すべての非零数がk乗根を持つ複素数体とは全く異なります。 ${\displaystyle n=7}$ ${\displaystyle k=3}$ ${\displaystyle n=11}$

統一の原始的ルーツ

プロパティ

• 原始根を法とする最大可能基数指数はであり、ここで λ はカーマイケル関数を表します。 ${\displaystyle n}$ ${\displaystyle \lambda (n)}$
• 原始的な 1 の根の基数指数はの約数です。 ${\displaystyle \lambda (n)}$
• の任意の約数は原始平方根（λの定義により必ず存在する）を与えます。このような平方根は、平方根（λの定義により必ず存在する）を選び、その平方根のべき乗を計算することで得られます。 ${\displaystyle k}$ ${\displaystyle \lambda (n)}$ ${\displaystyle k}$ ${\displaystyle \lambda (n)}$ ${\displaystyle x}$ ${\displaystyle x^{\lambda (n)/k}}$
• x が原始k乗根であり、かつ（必ずしも原始的ではない）ℓ乗根でもある場合、 kは ℓ の約数です。これは真です。なぜなら、ベズーの恒等式により、 kとℓの整数線型結合が に等しいからです。kは最小値であるため、 であり、はℓの約数です 。 ${\displaystyle \gcd(k,\ell )}$ ${\displaystyle k=\gcd(k,\ell )}$ ${\displaystyle \gcd(k,\ell )}$

プリミティブの数けth ルート

広く受け入れられている記号がないため、nを法とする原始k乗根の個数を と表記する。これは以下の性質を満たす。 ${\displaystyle g(n,k)}$

• ${\displaystyle g(n,k)={\begin{cases}>0&{\text{if }}k\mid \lambda (n),\\0&{\text{otherwise}}.\end{cases}}}$
• その結果、関数はゼロとは異なる値を持ち、約数の個数を計算します。 ${\displaystyle k\mapsto g(n,k)}$ ${\displaystyle d(\lambda (n))}$ ${\displaystyle d}$
• ${\displaystyle g(n,1)=1}$
• ${\displaystyle g(4,2)=1}$
• ${\displaystyle g(2^{n},2)=3}$なぜなら、-1 は常に1 の平方根だからです。 ${\displaystyle n\geq 3}$
• ${\displaystyle g(2^{n},2^{k})=2^{k}}$のために ${\displaystyle k\in [2,n-1)}$
• ${\displaystyle g(n,2)=1}$および（OEISのシーケンスA033948） ${\displaystyle n\geq 3}$ ${\displaystyle n}$
• ${\displaystyle \sum _{k\in \mathbb {N} }g(n,k)=f(n,\lambda (n))=\varphi (n)}$オイラーのトーティエント関数である ${\displaystyle \varphi }$
• と の関係は、ディリクレ畳み込みを使用して簡潔に記述できます。 ${\displaystyle f}$ ${\displaystyle g}$

${\displaystyle f=\mathbf {1} *g}$つまり ${\displaystyle f(n,k)=\sum _{d\mid k}g(n,d)}$

この式を使用して の値を再帰的に計算することができ、これはメビウスの反転式と同等です。 ${\displaystyle g}$ ${\displaystyle f}$

テスト×原始的なけ1の法の累乗根n

高速べき乗法を用いることで、 であることが確認できます。もしこれが真であれば、xはnを法とするk乗根ですが、必ずしも原始根であるとは限りません。もし原始根でなければ、kの約数 ℓ が存在し、 となります。この可能性を排除するには、 kを素数で割った値に 等しいℓがいくつかあるかどうかを確認すれば十分です。 ${\displaystyle x^{k}\equiv 1{\pmod {n}}}$ ${\displaystyle x^{\ell }\equiv 1{\pmod {n}}}$

つまり、nのすべての素因数pに対して、 x がn を法とする原始k乗根である場合に限ります。 ${\textstyle x^{k}\equiv 1{\pmod {n}}}$ $${\displaystyle x^{k/p}\not \equiv 1{\pmod {n}}}$$

例えば、17未満のすべての正の整数が17を法とする16乗根であり、17を法とする原始16乗根となる整数は、 ${\displaystyle n=17,}$ $${\displaystyle x^{16/2}\not \equiv 1{\pmod {17}}.}$$

原始的な発見け1の法の累乗根n

原始k乗根の中で、原始k乗根が最も多く見られます。そのため、原始k乗根となる整数をいくつか試してみることをお勧めします。そうすれば、すぐに成功します。原始k乗根xは、原始k乗根です。kがkを割り切れない場合、 k乗根は全く存在しません。 ${\displaystyle \lambda (n)}$ ${\displaystyle \lambda (n)}$ ${\displaystyle \lambda (n)}$ ${\displaystyle x^{\lambda (n)/k}}$ ${\displaystyle k}$ ${\displaystyle \lambda (n)}$

複数のプリミティブを見つけるけ法の累乗根n

原始k乗根xが得られれば、すべてのべき乗は1乗のa乗根となるが、必ずしも原始的である必要はない。べき乗が原始的1乗根となるのは、とが互いに素である場合に限る。証明は以下の通りである。もしが原始的でないならば、の約数が存在し、とが互いに素であるので、となる整数が存在する。これは次式を与える 。 ${\displaystyle x^{\ell }}$ ${\displaystyle k}$ ${\displaystyle x^{\ell }}$ ${\displaystyle k}$ ${\displaystyle k}$ ${\displaystyle \ell }$ ${\displaystyle x^{\ell }}$ ${\displaystyle m}$ ${\displaystyle k}$ ${\displaystyle (x^{\ell })^{m}\equiv 1{\pmod {n}}}$ ${\displaystyle k}$ ${\displaystyle \ell }$ ${\displaystyle a,b}$ ${\displaystyle ak+b\ell =1}$

${\displaystyle x^{m}\equiv (x^{m})^{ak+b\ell }\equiv (x^{k})^{ma}((x^{\ell })^{m})^{b}\equiv 1{\pmod {n}}}$、

つまり、より小さい指数 があるため、は原始の th 根ではないことになります。 ${\displaystyle x}$ ${\displaystyle k}$ ${\displaystyle m}$

つまり、xをべき乗すると、異なる原始k乗根が得られますが、これらがすべてそのような根であるとは限らないのです。しかし、それらすべてを見つけるのはそれほど簡単ではありません。 ${\displaystyle \varphi (k)}$

見つけるn原始的なけ1の法の累乗根n

どのような整数留数環に原始k乗根が存在するでしょうか？これは、次元整数ベクトルの離散フーリエ変換（より正確には数論的変換）を計算するために使用できます。逆変換を実行するには、 で割ります。つまり、kは を法とする単位元です。 ${\displaystyle k}$ ${\displaystyle k}$ ${\displaystyle n.}$

そのようなnを見つける簡単な方法は、等差数列の法に関して原始k乗根を調べることです。これらの法はすべてkと互いに素であるため、kは単位元です。等差数列に関するディリクレの定理によれば、数列には無限個の素数が存在し、素数 に対してが成り立ちます。したがって、 が素数である場合、 となり、単位元 の原始k乗根が存在します。しかし、素数かどうかの判定は厳しすぎるため、他に適切な法が存在する可能性があります。 ${\displaystyle k+1,2k+1,3k+1,\dots }$ ${\displaystyle p}$ ${\displaystyle \lambda (p)=p-1}$ ${\displaystyle mk+1}$ ${\displaystyle \lambda (mk+1)=mk}$

見つけるn1を法とする多重原始根を持つn

を法とする原始根が存在するような係数を求めるために、次の定理によって問題が簡素化されます。 ${\displaystyle n}$ ${\displaystyle k_{1}{\text{th}},k_{2}{\text{th}},\ldots ,k_{m}{\text{th}}}$ ${\displaystyle n}$

与えられた場合、 n を法とした原始 1 の根が存在する場合のみ、nを法とした原始 1 の根 が存在する。 ${\displaystyle n}$ ${\displaystyle k_{1}{\text{th}},\ldots ,k_{m}{\text{th}}}$ ${\displaystyle n}$ ${\displaystyle \operatorname {lcm} (k_{1},\ldots ,k_{m})}$

証拠

逆方向:と呼ばれる を法とした原始的な分の 1 根がある場合、 はを法とした 分の 1 根になります。 ${\displaystyle \operatorname {lcm} (k_{1},\ldots ,k_{m})}$ ${\displaystyle n}$ ${\displaystyle x}$ ${\displaystyle x^{\operatorname {lcm} (k_{1},\ldots ,k_{m})/k_{l}}}$ ${\displaystyle k_{l}}$ ${\displaystyle n}$

順方向：を法とする原始根が存在する場合、すべての指数は の約数です。これは を意味し、これは を法とする原始根が存在することを意味します。 ${\displaystyle k_{1}{\text{th}},\ldots ,k_{m}{\text{th}}}$ ${\displaystyle n}$ ${\displaystyle k_{1},\dots ,k_{m}}$ ${\displaystyle \lambda (n)}$ ${\displaystyle \operatorname {lcm} (k_{1},\dots ,k_{m})\mid \lambda (n)}$ ${\displaystyle \operatorname {lcm} (k_{1},\ldots ,k_{m})}$ ${\displaystyle n}$

参考文献

1. フィンチ, スティーブン; マーティン, グレッグ; セバ, パスカル (2010). 「nを法とする単位元と零元の根」(PDF) .アメリカ数学会報. 138 (8): 2729– 2743. doi : 10.1090/s0002-9939-10-10341-4 . 2011年2月20日閲覧.

Retrieved from "https://en.wikipedia.org/w/index.php?title=Root_of_unity_modulo_n&oldid=1285554896"