nを法とする1の平方根

• x がnを法とするk乗根である場合、xは単位元 (可逆) であり、その逆元は${\displaystyle x^{k-1}}$つまり、xとnは互いに素である。
• xが単位元である場合、それはnを法とする1の（原始） k乗根であり、kはnを法とするxの乗法次数である。
• xが1の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}}.}$

広く受け入れられている記号がないため、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}$素早く。

させて${\displaystyle n=7}$そして${\displaystyle k=3}$この場合、1の立方根が3つあります（1、2、4）。${\displaystyle n=11}$しかし、1の立方根は1つしかなく、それは1そのものです。この性質は、すべての非ゼロ数がk乗根を持つ複素数の世界とは大きく異なり ます。

• 原始根の法則における最大可能な基数指数${\displaystyle n}$は${\displaystyle \lambda (n)}$ここで、λはカーマイケル関数を表す。
• 1の原始根の基数指数は、${\displaystyle \lambda (n)}$。
• すべての約数${\displaystyle k}$の${\displaystyle \lambda (n)}$プリミティブを生成する${\displaystyle k}$1のn乗根。このような根は、${\displaystyle \lambda (n)}$λの定義により必ず存在する、 番目の原始根は、${\displaystyle x}$そしてパワーを計算する${\displaystyle x^{\lambda (n)/k}}$。
• x が原始k乗根であり、かつ (必ずしも原始的ではない) ℓ乗根でもある場合、 kは ℓ の約数である。これは、ベズーの恒等式により、 kとℓの整数線形結合が次のように得られるためである。${\displaystyle \gcd(k,\ell )}$kは最小なので、${\displaystyle k=\gcd(k,\ell )}$そして${\displaystyle \gcd(k,\ell )}$はℓの約数である。 

広く受け入れられている記号がないため、 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}$のために${\displaystyle n\geq 3}$-1は常に1の平方根であるため。
• ${\displaystyle g(2^{n},2^{k})=2^{k}}$のために${\displaystyle k\in [2,n-1)}$
• ${\displaystyle g(n,2)=1}$のために${\displaystyle n\geq 3}$そして${\displaystyle n}$（OEISの配列A033948）
• ${\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}$この式はメビウス反転式と同等です。

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

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

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

原始的なk乗根の中で、原始的な${\displaystyle \lambda (n)}$の平方根が最も頻繁に出現します。したがって、いくつかの整数を原始数として試してみることをお勧めします。${\displaystyle \lambda (n)}$th ルート、すぐに成功するもの。原始的な${\displaystyle \lambda (n)}$数√x、その数${\displaystyle x^{\lambda (n)/k}}$プリミティブです${\displaystyle k}$1の 乗根。kが割り切れない場合${\displaystyle \lambda (n)}$そうすれば、1のk乗根は全く存在しなくなる。

原始的なk乗根xが得られれば、すべてのべき乗は${\displaystyle x^{\ell }}$は${\displaystyle k}$統一の根源だが、必ずしも原始的な根源ではない。${\displaystyle x^{\ell }}$プリミティブです${\displaystyle k}$1の 乗根は、${\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}}}$、

つまり${\displaystyle x}$プリミティブではありません${\displaystyle k}$1の平方根は、指数が小さいため${\displaystyle m}$。

つまり、xを指数化することで、${\displaystyle \varphi (k)}$これらは異なるk乗根であるが、これらがすべての根であるとは限らない。しかし、それらすべてを見つけるのはそう簡単ではない。

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

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

モジュラスを求めるには${\displaystyle n}$原始的な${\displaystyle k_{1}{\text{th}},k_{2}{\text{th}},\ldots ,k_{m}{\text{th}}}$1の法則の根${\displaystyle n}$次の定理は、問題をより単純な問題に還元する。

与えられた${\displaystyle n}$原始的な${\displaystyle k_{1}{\text{th}},\ldots ,k_{m}{\text{th}}}$1の法則の根${\displaystyle n}$原始的な要素が存在する場合に限る${\displaystyle \operatorname {lcm} (k_{1},\ldots ,k_{m})}$nを法とする 1 の 乗根。 

証拠

逆方向: プリミティブがある場合${\displaystyle \operatorname {lcm} (k_{1},\ldots ,k_{m})}$1の法則の 乗根${\displaystyle n}$呼ばれる${\displaystyle x}$、 それから${\displaystyle x^{\operatorname {lcm} (k_{1},\ldots ,k_{m})/k_{l}}}$は${\displaystyle k_{l}}$1の法則の 乗根${\displaystyle n}$。

前方方向: 原始的な${\displaystyle k_{1}{\text{th}},\ldots ,k_{m}{\text{th}}}$1の法則の根${\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})}$1の法則の 乗根${\displaystyle n}$。