索引

记号
引理1: 设 ${{x}_{0}} x0对模 m m m的指数, 则 ∀ x ∈ Z \forall x\in \mathbb{Z} ∀x∈Z满足 x ≡ x 0 m o d m x\equiv {{x}_{0}}\text{ }\bmod m x≡x0 modm, x x x对模 m m m的指数也为 d d d. 此时称集合 { x ∈ Z : x ≡ x 0 m o d m } \left\{ x\in \mathbb{Z}:x\equiv {{x}_{0}}\text{ }\bmod m \right\} {x∈Z:x≡x0 modm}为模 m m m的一个指数. 特别地, 若 d = φ ( m ) d=\varphi \left( m \right) d=φ(m), 则称集合 { x ∈ Z : x ≡ x 0 m o d m } \left\{ x\in \mathbb{Z}:x\equiv {{x}_{0}}\text{ }\bmod m \right\} {x∈Z:x≡x0 modm}为模 m m$
$m$ 的一个原根.
引理2: 若
$p$ 的原根是存在的.
引理3: 设 $\left. d \right|p-1 d∣p−1, 则一定有 X ( d ) ≠ ∅ X\left( d \right)\ne \varnothing$
$X (d) \neq = \emptyset$ .
引理4: 设 $\left. d \right|p-1 d∣p−1, 则有 ∣ X ( d ) ∣ = φ ( d ) \left| X\left( d \right) \right|=\varphi \left( d \right)$
$∣ X (d) ∣ = φ (d)$ .
推论5: 设 $\left. d \right|p-1 d∣p−1, 则有 X ( d ) = { ( a k m o d p ) : gcd ⁡ ( d , k ) = 1 } . X\left( d \right)=\left\{ \left( {{a}^{k}}\bmod p \right):\text{ }\gcd \left( d,k \right)=1 \right\}.$
$X (d) = {(a^{k} m o d p) : g cd (d, k) = 1} .$
推论6: 设 $\varphi \left( p-1 \right)$
$φ (p - 1)$ 个.
方法7: 设 $n\in \left\{ 1,2,\cdots ,p-1 \right\} n∈{1,2,⋯,p−1}对模 p p$
$p$ 的指数.
例子8 (用方法7找出一些小素数的所有原根)
方法9: 用推论5和穷举法求一个较大素数
$p$ 的所有原根.
例子10 (用方法9找出一些较大素数的所有原根)
例子11 (找出一些合数的所有原根)

关于指数和原根的基础知识参见博文《指数和原根》. 本文的部分内容也是对该博文的补充.

记号

(1)

(

)

{

∈

≤

对

模

的

指

数

}

X\left( d \right):=\left\{ n\in \mathbb{Z}:\text{ }1\le n<p,\text{ }n对模p的指数=d \right\}

$X (d) : = {n \in Z : 1 \leq n < p, n 对模 p 的指数 = d}$ , 其中

$p$ 是一个素数,

$d$ 满足

∣

−

\left. d \right|p-1

$d ∣ p - 1$ .
(2)

∥

⇔

∣

∧

∣

\left. {{p}^{i}} \right\|x\text{ }\Leftrightarrow \text{ }\left. {{p}^{i}} \right|x\text{ }\wedge \text{ }{{p}^{i+1}}\cancel{|}x.

$p^{i} ∥ ∥ x \Leftrightarrow p^{i} ∣ ∣ x \land p^{i + 1} ∣ x .$

引理1: 设 ${{x}_{0}} x0对模 m m m的指数, 则 ∀ x ∈ Z \forall x\in \mathbb{Z} ∀x∈Z满足 x ≡ x 0 m o d m x\equiv {{x}_{0}}\text{ }\bmod m x≡x0 modm, x x x对模 m m m的指数也为 d d d. 此时称集合 { x ∈ Z : x ≡ x 0 m o d m } \left\{ x\in \mathbb{Z}:x\equiv {{x}_{0}}\text{ }\bmod m \right\} {x∈Z:x≡x0 modm}为模 m m m的一个指数. 特别地, 若 d = φ ( m ) d=\varphi \left( m \right) d=φ(m), 则称集合 { x ∈ Z : x ≡ x 0 m o d m } \left\{ x\in \mathbb{Z}:x\equiv {{x}_{0}}\text{ }\bmod m \right\} {x∈Z:x≡x0 modm}为模 m m m的一个原根.$

证明记

{

∈

≡

}

{{S}_{0}}=\left\{ n\in {{\mathbb{Z}}_{>0}}:{{x}_{0}}^{n}\equiv 1\text{ }\bmod m \right\}

$S_{0} = {n \in Z_{> 0} : x_{0}^{n} \equiv 1 m o d m}$ .

∀

∈

\forall x\in \mathbb{Z}

$\forall x \in Z$ 满足

≡

x\equiv {{x}_{0}}\text{ }\bmod m

$x \equiv x_{0} m o d m$ , 记

{

∈

≡

}

{{S}_{x}}=\left\{ n\in {{\mathbb{Z}}_{>0}}:{{x}^{n}}\equiv 1\text{ }\bmod m \right\}

$S_{x} = {n \in Z_{> 0} : x^{n} \equiv 1 m o d m}$ .
由

$x$ 与

{{x}_{0}}

$x_{0}$ 对模

$m$ 的同余关系, 显然有

{{S}_{0}}={{S}_{x}}

$S_{0} = S_{x}$ , 则

min

⁡

min

⁡

\min {{S}_{x}}=\min {{S}_{0}}=d

$min S_{x} = min S_{0} = d$ , 即

$d$ 也是

$x$ 对模

$m$ 的指数.

引理2: 若

证明由于

$p$ 是奇素数, 因此

∀

∈

{

⋯

−

}

\forall x\in \left\{ 1,2,\cdots ,p-1 \right\}

$\forall x \in {1, 2, \dots, p - 1}$ ,

gcd

⁡

(

)

\gcd \left( x,p \right)=1

$g cd (x, p) = 1$ . 根据博文《指数和原根》命题2,

$x$ 对模

$p$ 的指数存在. 基于此, 从这

−

p-1

$p - 1$ 个指数中取出所有不同的指数, 记作

⋯

(2.1)

{{\delta }_{1}},{{\delta }_{2}},\cdots ,{{\delta }_{r}}. \tag{2.1}

$δ_{1}, δ_{2}, \dots, δ_{r} . (2.1)$
令

(

⋯

)

\tau =lcm\left( {{\delta }_{1}},{{\delta }_{2}},\cdots ,{{\delta }_{r}} \right)

$τ = l c m (δ_{1}, δ_{2}, \dots, δ_{r})$ .

第一步, 我们证明

∃

∈

\exists g\in \mathbb{Z}

$\exists g \in Z$ ,

$g$ 对模

$p$ 的指数是

\tau

$τ$ .
设

⋯

\tau ={{q}_{1}}^{{{\alpha }_{1}}}{{q}_{2}}^{{{\alpha }_{2}}}\cdots {{q}_{k}}^{{{\alpha }_{k}}}

$τ = q_{1}^{α_{1}} q_{2}^{α_{2}} \dots q_{k}^{α_{k}}$ 是

\tau

$τ$ 的标准分解式.

∀

∈

{

⋯

}

\forall s\in \left\{ 1,2,\cdots ,k \right\}

$\forall s \in {1, 2, \dots, k}$ , 设

∥

⋯

∥

\left. {{q}_{s}}^{{{\beta }_{s1}}} \right\|{{\delta }_{1}},\text{ }\left. {{q}_{s}}^{{{\beta }_{s2}}} \right\|{{\delta }_{2}},\text{ }\cdots ,\text{ }\left. {{q}_{s}}^{{{\beta }_{sr}}} \right\|{{\delta }_{r}}

$q_{s}^{β_{s 1}} ∥ ∥ δ_{1}, q_{s}^{β_{s 2}} ∥ ∥ δ_{2}, \dots, q_{s}^{β_{s r}} ∥ ∥ δ_{r}$ . 则成立

max

⁡

{

⋯

}

{{\alpha }_{s}}=\max \left\{ {{\beta }_{s1}},{{\beta }_{s2}},\cdots ,{{\beta }_{sr}} \right\},

$α_{s} = max {β_{s 1}, β_{s 2}, \dots, β_{s r}},$
即

∃

∈

{

⋯

}

\exists \delta \in \left\{ {{\delta }_{1}},{{\delta }_{2}},\cdots ,{{\delta }_{r}} \right\}

$\exists δ \in {δ_{1}, δ_{2}, \dots, δ_{r}}$ , 使得

∥

\left. {{q}_{s}}^{{{\alpha }_{s}}} \right\|\delta

$q_{s}^{α_{s}} ∥ δ$ , 即

∃

∈

\exists t\in \mathbb{Z}

$\exists t \in Z$ , 使得

\delta =t{{q}_{s}}^{{{\alpha }_{s}}}

$δ = t q_{s}^{α_{s}}$ . 根据式(2.1)的定义,

∃

∈

{

⋯

−

}

\exists x\in \left\{ 1,2,\cdots ,p-1 \right\}

$\exists x \in {1, 2, \dots, p - 1}$ , 使得

$x$ 对模

$p$ 的指数为

\delta

$δ$ . 根据博文《指数和原根》定理7,

{{x}_{s}}={{x}^{t}}

$x_{s} = x^{t}$ 对模

$p$ 的指数为

{{q}_{s}}^{{{\alpha }_{s}}}

$q_{s}^{α_{s}}$ . 依照上面方法分别找出模

$p$ 指数为

⋯

{{q}_{1}}^{{{\alpha }_{1}}},\text{ }{{q}_{2}}^{{{\alpha }_{2}}},\text{ }\cdots ,\text{ }{{q}_{k}}^{{{\alpha }_{k}}}

$q_{1}^{α_{1}}, q_{2}^{α_{2}}, \dots, q_{k}^{α_{k}}$ 的整数

⋯

{{x}_{1}},\text{ }{{x}_{2}},\text{ }\cdots ,\text{ }{{x}_{k}}

$x_{1}, x_{2}, \dots, x_{k}$ . 由于

gcd

⁡

(

⋯

)

\gcd \left( {{q}_{1}}^{{{\alpha }_{1}}},{{q}_{2}}^{{{\alpha }_{2}}},\cdots ,{{q}_{k}}^{{{\alpha }_{k}}} \right)=1

$g cd (q_{1}^{α_{1}}, q_{2}^{α_{2}}, \dots, q_{k}^{α_{k}}) = 1$ , 根据博文《指数和原根》定理8,

⋯

g:={{x}_{1}}{{x}_{2}}\cdots {{x}_{k}}

$g : = x_{1} x_{2} \dots x_{k}$ 对模

$p$ 的指数即为

∏

\prod\limits_{s=1}^{k}{{{q}_{s}}^{{{\alpha }_{s}}}}=\tau

$s = 1 \prod k q_{s}^{α_{s}} = τ$ .

第二步, 我们证明

−

\tau =p-1

$τ = p - 1$ .
一方面,

⋯

−

1,2,\cdots ,p-1

$1, 2, \dots, p - 1$ 中任一数的指数都在式(2.1)中出现, 而

∀

∈

{

⋯

}

\forall s\in \left\{ 1,2,\cdots ,r \right\}

$\forall s \in {1, 2, \dots, r}$ ,

∣

\left. {{\delta }_{s}} \right|\tau

$δ_{s} ∣ τ$ , 故成立

≡

∀

∈

{

⋯

−

}

{{x}^{\tau }}\equiv 1\text{ }\bmod p,\text{ }\forall x\in \left\{ 1,2,\cdots ,p-1 \right\},

$x^{τ} \equiv 1 m o d p, \forall x \in {1, 2, \dots, p - 1},$
即同余式

≡

{{x}^{\tau }}\equiv 1\text{ }\bmod p

$x^{τ} \equiv 1 m o d p$ 至少有

−

p-1

$p - 1$ 个解. 由博文《素数模同余式次数与其解数的关系》定理5,

≥

−

\tau \ge p-1

$τ \geq p - 1$ .
另一方面, 由于

$p$ 是奇素数,

∀

∈

{

⋯

−

}

\forall x\in \left\{ 1,2,\cdots ,p-1 \right\}

$\forall x \in {1, 2, \dots, p - 1}$ ,

gcd

⁡

(

)

\gcd \left( x,p \right)=1

$g cd (x, p) = 1$ . 由欧拉定理, 成立

(

)

−

≡

{{x}^{\varphi \left( p \right)}}={{x}^{p-1}}\equiv 1\text{ }\bmod p

$x^{φ (p)} = x^{p - 1} \equiv 1 m o d p$ . 再由博文《指数和原根》定理5, 有

∀

∈

{

⋯

}

\forall s\in \left\{ 1,2,\cdots ,r \right\}

$\forall s \in {1, 2, \dots, r}$ ,

∣

−

\left. {{\delta }_{s}} \right|p-1

$δ_{s} ∣ p - 1$ . 再由最小公倍数的性质, 有

(

⋯

)

∣

−

\tau =\left. lcm\left( {{\delta }_{1}},{{\delta }_{2}},\cdots ,{{\delta }_{r}} \right) \right|p-1

$τ = l c m (δ_{1}, δ_{2}, \dots, δ_{r}) ∣ p - 1$ , 由此得

≤

−

\tau \le p-1

$τ \leq p - 1$ .
综上有

−

\tau =p-1

$τ = p - 1$ .

基于前两步,

∃

∈

\exists g\in \mathbb{Z}

$\exists g \in Z$ 使得

$g$ 对模

$p$ 的指数为

−

(

)

p-1=\varphi \left( p \right)

$p - 1 = φ (p)$ ,

$g$ 即为模

$p$ 的一个原根. 至此引理2证明完毕.

引理3: 设 $\left. d \right|p-1 d∣p−1, 则一定有 X ( d ) ≠ ∅ X\left( d \right)\ne \varnothing X(d)=∅.$

证明

∣

−

⇒

∃

∈

\left. d \right|p-1\text{ }\Rightarrow \text{ }\exists k\in \mathbb{Z}

$d ∣ p - 1 \Rightarrow \exists k \in Z$ 使得

−

p-1=kd

$p - 1 = k d$ 。由引理2,

∃

∈

\exists g\in \mathbb{Z}

$\exists g \in Z$ 使得

$g$ 是模

$p$ 的原根, 即

$g$ 对模

$p$ 的指数为

(

)

−

\varphi \left( p \right)=p-1=kd

$φ (p) = p - 1 = k d$ . 由博文《指数和原根》定理7,

{{g}^{k}}

$g^{k}$ 对模

$p$ 的指数即为

$d$ , 即有

(

)

∈

(

)

\left( {{g}^{k}}\text{ }\bmod p \right)\in X\left( d \right)

$(g^{k} m o d p) \in X (d)$ ,

(

)

≠

∅

X\left( d \right)\ne \varnothing

$X (d) \neq = \emptyset$ .

引理4: 设 $\left. d \right|p-1 d∣p−1, 则有 ∣ X ( d ) ∣ = φ ( d ) \left| X\left( d \right) \right|=\varphi \left( d \right) ∣X(d)∣=φ(d).$

证明
第一步, 由引理3,

(

)

≠

∅

X\left( d \right)\ne \varnothing

$X (d) \neq = \emptyset$ ,

∃

∈

(

)

\exists a\in X\left( d \right)

$\exists a \in X (d)$ . 则

$a$ 对模

$p$ 的指数为

$d$ , 有

≡

(4.1)

{{a}^{d}}\equiv 1\text{ }\bmod p. \tag{4.1}

$a^{d} \equiv 1 m o d p . (4.1)$
记

{

≤

≡

}

S=\left\{ 1\le x<p:\text{ }{{x}^{d}}\equiv 1\text{ }\bmod p \right\}.

$S = {1 \leq x < p : x^{d} \equiv 1 m o d p} .$
显然有

(

)

⊆

X\left( d \right)\subseteq S

$X (d) \subseteq S$ . 由于

∣

−

\left. d \right|p-1

$d ∣ p - 1$ , 因此

∃

∈

\exists k\in \mathbb{Z}

$\exists k \in Z$ , 使得

−

p-1=kd

$p - 1 = k d$ . 成立

−

(

−

)

(

−

)

(

)

−

)

(

−

)

(

)

−

(

)

−

⋯

(

)

\begin{aligned} & {{x}^{p}}-x=x\left( {{x}^{p-1}}-1 \right)=x\left( {{x}^{kd}}-1 \right) \\ & =x\left( {{\left( {{x}^{d}} \right)}^{k}}-1 \right)=x\left( {{x}^{d}}-1 \right)\left( {{\left( {{x}^{d}} \right)}^{k-1}}+{{\left( {{x}^{d}} \right)}^{k-2}}+\cdots +{{\left( {{x}^{d}} \right)}^{1}}+1 \right). \\ \end{aligned}

$x^{p} - x = x (x^{p - 1} - 1) = x (x^{k d} - 1) = x ((x^{d})^{k} - 1) = x (x^{d} - 1) ((x^{d})^{k - 1} + (x^{d})^{k - 2} + \dots + (x^{d})^{1} + 1) .$
即有

−

∣

−

\left. {{x}^{d}}-1 \right|{{x}^{p}}-x

$x^{d} - 1 ∣ ∣ x^{p} - x$ ,

−

{{x}^{d}}-1

$x^{d} - 1$ 除

−

{{x}^{p}}-x

$x^{p} - x$ 得到的余式是

$0$ , 由博文《素数模同余式次数与其解数的关系》定理6, 同余式

≡

{{x}^{d}}\equiv 1\text{ }\bmod p

$x^{d} \equiv 1 m o d p$ 恰好有

$d$ 个根.
另一方面, 由式(4.1), 成立

(

)

(

)

≡

{{\left( {{a}^{k}} \right)}^{d}}={{\left( {{a}^{d}} \right)}^{k}}\equiv 1\text{ }\bmod p

$(a^{k})^{d} = (a^{d})^{k} \equiv 1 m o d p$ , 因此

⋯

−

1,a,{{a}^{2}},\cdots ,{{a}^{d-1}}

$1, a, a^{2}, \dots, a^{d - 1}$ 这

$d$ 个数均为同余式

≡

{{x}^{d}}\equiv 1\text{ }\bmod p

$x^{d} \equiv 1 m o d p$ 的根. 且根据博文《指数和原根》定理5(1),

⋯

−

1,a,{{a}^{2}},\cdots ,{{a}^{d-1}}

$1, a, a^{2}, \dots, a^{d - 1}$ 两两不同余, 因此

$S$ 可表示为

{

∈

{

⋯

−

}

⊇

(

)

(4.2)

S=\left\{ x\bmod p,\text{ }x\in \left\{ 1,a,{{a}^{2}},\cdots ,{{a}^{d-1}} \right\} \right\}\supseteq X\left( d \right). \tag{4.2}

$S = {x m o d p, x \in {1, a, a^{2}, \dots, a^{d - 1}}} \supseteq X (d) . (4.2)$

第二步, 由博文《指数和原根》定理9,

{{a}^{k}}

$a^{k}$ 对模

$p$ 的指数为

gcd

⁡

(

)

\frac{d}{\gcd \left( d,k \right)}

$\frac{d}{g cd ( d , k )}$ . 因此成立推理

(

)

∈

(

)

⇒

gcd

⁡

(

)

⇒

gcd

⁡

(

)

\left( {{a}^{k}}\bmod p \right)\in X\left( d \right)\text{ }\Rightarrow \text{ }\frac{d}{\gcd \left( d,k \right)}=d\text{ }\Rightarrow \text{ }\gcd \left( d,k \right)=1.

$(a^{k} m o d p) \in X (d) \Rightarrow \frac{d}{g cd ( d , k )} = d \Rightarrow g cd (d, k) = 1 .$
由式(4.2),

(

)

X\left( d \right)

$X (d)$ 中的元素均为

(

)

\left( {{a}^{k}}\text{ }\bmod p \right)

$(a^{k} m o d p)$ 的形式, 因此有

∣

(

)

∣

≤

(

)

(4.3)

\left| X\left( d \right) \right|\le \varphi \left( d \right). \tag{4.3}

$∣ X (d) ∣ \leq φ (d) . (4.3)$

第三步, 一方面,

∀

∈

{

⋯

−

}

\forall n\in \left\{ 1,2,\cdots ,p-1 \right\}

$\forall n \in {1, 2, \dots, p - 1}$ , 由于

$p$ 是素数,

gcd

⁡

(

)

\gcd \left( n,p \right)=1

$g cd (n, p) = 1$ , 因此

$n$ 对模

$p$ 的指数存在, 设为

{{d}_{n}}

$d_{n}$ , 成立

∈

(

)

n\in X\left( {{d}_{n}} \right)

$n \in X (d_{n})$ . 由费马小定理, 成立

−

≡

{{n}^{p-1}}\equiv 1\text{ }\bmod p

$n^{p - 1} \equiv 1 m o d p$ . 根据博文《指数和原根》定理5(3), 有

∣

−

\left. {{d}_{n}} \right|p-1

$d_{n} ∣ p - 1$ .于是成立

{

∈

≤

}

⊆

⋃

∣

−

(

)

(4.4)

\left\{ n\in \mathbb{Z}:\text{ }1\le n<p \right\}\subseteq \bigcup\limits_{\left. d \right|p-1}^{{}}{X\left( d \right)}. \tag{4.4}

${n \in Z : 1 \leq n < p} \subseteq d ∣ p - 1 ⋃ X (d) . (4.4)$
另一方面, 由

(

)

X\left( d \right)

$X (d)$ 的定义, 有

∀

\forall d

$\forall d$ 满足

∣

−

\left. d \right|p-1

$d ∣ p - 1$ ,

(

)

⊆

{

∈

≤

}

X\left( d \right)\subseteq \left\{ n\in \mathbb{Z}:\text{ }1\le n<p \right\}

$X (d) \subseteq {n \in Z : 1 \leq n < p}$ , 即成立

⋃

∣

−

(

)

⊆

{

∈

≤

}

(4.5)

\bigcup\limits_{\left. d \right|p-1}^{{}}{X\left( d \right)}\subseteq \left\{ n\in \mathbb{Z}:\text{ }1\le n<p \right\}. \tag{4.5}

$d ∣ p - 1 ⋃ X (d) \subseteq {n \in Z : 1 \leq n < p} . (4.5)$
由式(4.4), 式(4.5), 成立

⋃

∣

−

(

)

{

∈

≤

}

(4.6)

\bigcup\limits_{\left. d \right|p-1}^{{}}{X\left( d \right)}=\left\{ n\in \mathbb{Z}:\text{ }1\le n<p \right\}. \tag{4.6}

$d ∣ p - 1 ⋃ X (d) = {n \in Z : 1 \leq n < p} . (4.6)$

第四步, 由博文《初等数论课堂笔记第三章 – 欧拉函数》中的定理, 成立

∑

∣

−

(

)

−

(4.7)

\sum\limits_{\left. d \right|p-1}^{{}}{\varphi \left( d \right)}=p-1. \tag{4.7}

$d ∣ p - 1 \sum φ (d) = p - 1 . (4.7)$
由式(4.6), (4.3), (4.7), 成立

−

∣

⋃

∣

−

(

)

∣

∑

∣

−

∣

(

)

∣

(

不

同

的

(

)

彼

此

互

不

相

交

)

≤

∑

∣

−

(

)

−

\begin{aligned} & p-1=\left| \bigcup\limits_{\left. d \right|p-1}^{{}}{X\left( d \right)} \right|=\sum\limits_{\left. d \right|p-1}^{{}}{\left| X\left( d \right) \right|}\text{ }\left( 不同的X\left( d \right)彼此互不相交 \right) \\ & \le \sum\limits_{\left. d \right|p-1}^{{}}{\varphi \left( d \right)}=p-1. \\ \end{aligned}

$p - 1 = ∣ ∣ ∣ ∣ ∣ ∣ d ∣ p - 1 ⋃ X (d) ∣ ∣ ∣ ∣ ∣ ∣ = d ∣ p - 1 \sum ∣ X (d) ∣ (不同的 X (d) 彼此互不相交) \leq d ∣ p - 1 \sum φ (d) = p - 1 .$
因此只能是

∀

\forall d

$\forall d$ 满足

∣

−

\left. d \right|p-1

$d ∣ p - 1$ , 成立

∣

(

)

∣

(

)

\left| X\left( d \right) \right|=\varphi \left( d \right).

$∣ X (d) ∣ = φ (d) .$

推论5: 设 $\left. d \right|p-1 d∣p−1, 则有 X ( d ) = { ( a k m o d p ) : gcd ⁡ ( d , k ) = 1 } . X\left( d \right)=\left\{ \left( {{a}^{k}}\bmod p \right):\text{ }\gcd \left( d,k \right)=1 \right\}. X(d)={(akmodp): gcd(d,k)=1}.$

证明首先, 由式(4.2),

∀

∈

(

)

\forall x\in X\left( d \right)

$\forall x \in X (d)$ ,

∃

∈

{

⋯

−

}

\exists k\in \left\{ 0,1,\cdots ,d-1 \right\}

$\exists k \in {0, 1, \dots, d - 1}$ , 使得

(

)

x=\left( {{a}^{k}}\bmod p \right).

$x = (a^{k} m o d p) .$
且在引理4第二步中已经得到推理

(

)

∈

(

)

⇒

gcd

⁡

(

)

⇒

gcd

⁡

(

)

\left( {{a}^{k}}\text{ }\bmod p \right)\in X\left( d \right)\text{ }\Rightarrow \text{ }\frac{d}{\gcd \left( d,k \right)}=d\text{ }\Rightarrow \text{ }\gcd \left( d,k \right)=1.

$(a^{k} m o d p) \in X (d) \Rightarrow \frac{d}{g cd ( d , k )} = d \Rightarrow g cd (d, k) = 1 .$
若

∃

\exists k

$\exists k$ 满足

gcd

⁡

(

)

\gcd \left( d,k \right)=1

$g cd (d, k) = 1$ , 而

∉

(

)

{{a}^{k}}\text{ }\bmod p\notin X\left( d \right)

$a^{k} m o d p \in / X (d)$ , 则有

∣

(

)

∣

(

)

\left| X\left( d \right) \right|<\varphi \left( d \right)

$∣ X (d) ∣ < φ (d)$ , 矛盾. 由反证法即可证得推论5.

推论6: 设 $\varphi \left( p-1 \right) φ(p−1)个.$

证明根据引理4, 模

$p$ 的原根个数即为

∣

(

−

)

∣

(

−

)

\left| X\left( p-1 \right) \right|=\varphi \left( p-1 \right)>0

$∣ X (p - 1) ∣ = φ (p - 1) > 0$ .

方法7: 设 $n\in \left\{ 1,2,\cdots ,p-1 \right\} n∈{1,2,⋯,p−1}对模 p p p的指数.$

由于

∀

∈

{

⋯

−

}

\forall n\in \left\{ 1,2,\cdots ,p-1 \right\}

$\forall n \in {1, 2, \dots, p - 1}$ ,

gcd

⁡

(

)

\gcd \left( n,p \right)=1

$g cd (n, p) = 1$ , 由费马小定理, 成立

−

≡

{{n}^{p-1}}\equiv 1\text{ }\bmod p.

$n^{p - 1} \equiv 1 m o d p .$
由博文《指数和原根》命题2和定理5(3),

$n$ 对

$p$ 的指数存在, 记为

\delta

$δ$ , 满足

∣

−

\left. \delta \right|p-1

$δ ∣ p - 1$ .
于是我们只需要从小到大逐个地用

−

p-1

$p - 1$ 的因数

$d$ 考察是否成立

≡

{{n}^{d}}\equiv 1\text{ }\bmod p

$n^{d} \equiv 1 m o d p$ 即可.

例子8 (用方法7找出一些小素数的所有原根)

模数

p=3

$p = 3$ ,

−

p-1=2

$p - 1 = 2$ 的所有因数是

1,\text{ }2

$1, 2$ .

≡

⇒

≤

的

指

数

\begin{matrix} {} & 1 & 2 \\ 1 & 1 & {} \\ 2 & 2 & 4\equiv 1 \\ \end{matrix}\text{ }\Rightarrow \text{ }\begin{matrix} 1\le n<3 & 1 & 2 \\ n的指数 & 1 & 2 \\ \end{matrix}

$12112 2 4 \equiv 1 \Rightarrow 1 \leq n < 3 n 的指数 1122$
模数

p=5

$p = 5$ ,

−

p-1=4

$p - 1 = 4$ 的所有因数是

1,\text{ }2,\text{ }4

$1, 2, 4$ .

≡

⇒

≤

的

指

数

\begin{matrix} {} & 1 & 2 & 4 \\ 1 & 1 & {} & {} \\ 2 & 2 & 4 & 16\equiv 1 \\ 3 & 3 & 9\equiv 4 & 81\equiv 1 \\ 4 & 4 & 16\equiv 1 & {} \\ \end{matrix}\text{ }\Rightarrow \text{ }\begin{matrix} 1\le n<5 & 1 & 2 & 3 & 4 \\ n的指数 & 1 & 4 & 4 & 2 \\ \end{matrix}

$123411234 24 9 \equiv 4 16 \equiv 1 4 16 \equiv 1 81 \equiv 1 \Rightarrow 1 \leq n < 5 n 的指数 11243442$
模数

p=7

$p = 7$ ,

−

p-1=6

$p - 1 = 6$ 的所有因数是

1,\text{ }2,\text{ }3,\text{ }6

$1, 2, 3, 6$ .

≡

−

729

≡

125

≡

−

15625

≡

⇒

≤

的

指

数

\begin{matrix} {} & 1 & 2 & 3 & 6 \\ 1 & 1 & {} & {} & {} \\ 2 & 2 & 4 & 8\equiv 1 & {} \\ 3 & 3 & 9\equiv 2 & 27\equiv -1 & 729\equiv 1 \\ 4 & 4 & 16\equiv 2 & 64\equiv 1 & {} \\ 5 & 5 & 25\equiv 4 & 125\equiv -1 & 15625\equiv 1 \\ 6 & 6 & 36\equiv 1 & {} & {} \\ \end{matrix}\text{ }\Rightarrow \text{ }\begin{matrix} 1\le n<7 & 1 & 2 & 3 & 4 & 5 & 6 \\ n的指数 & 1 & 3 & 6 & 3 & 6 & 2 \\ \end{matrix}

$1234561123456 24 9 \equiv 2 16 \equiv 2 25 \equiv 4 36 \equiv 1 3 8 \equiv 1 27 \equiv - 1 64 \equiv 1 125 \equiv - 1 6 729 \equiv 1 15625 \equiv 1 \Rightarrow 1 \leq n < 7 n 的指数 112336435662$
汇总成如下表格.

素

数

的

原

根

个

数

(

−

)

的

原

根

\begin{matrix} 素数p & 2 & 3 & 5 & 7 \\ p的原根个数\varphi \left( p-1 \right) & 1 & 1 & 2 & 2 \\ p的原根 & 1 & 2 & 2,3 & 3,5 \\ \end{matrix}

$素数 p p 的原根个数 φ (p - 1) p 的原根 211312 52 2, 3 72 3, 5$

方法9: 用推论5和穷举法求一个较大素数

令

n=2

$n = 2$ .
第一步: 用方法7求出

$n$ 模

$p$ 的指数

$d$ .
第二步: 若

(

)

−

d=\varphi \left( p \right)=p-1

$d = φ (p) = p - 1$ , 则转第三步, 否则令

n=n+1

$n = n + 1$ , 返回第一步.
第三步: 此时

$n$ 是模

$p$ 的最小原根. 找出

{

⋯

−

}

\left\{ 1,2,\cdots ,p-1 \right\}

${1, 2, \dots, p - 1}$ 中所有与

−

p-1

$p - 1$ 互素的数

$k$ .
第四步: 根据推论5的结果, 依次计算

{{n}^{k}}\bmod p

$n^{k} m o d p$ .

注 第一, 二步中最小原根的寻找也可以通过查表法.
在这里插入图片描述

例子10 (用方法9找出一些较大素数的所有原根)

$11$ 的原根: 因为下面的计算,

g=2

$g = 2$ 是最小原根, 其他原根上方的

$n$ 与

−

11-1=10

$11 - 1 = 10$ 互素.

‾

\begin{matrix} n & 1 & 2 & 3 & 4 & 5 & 6 & 7 & 8 & 9 & 10 \\ {{2}^{n}}\text{ }\bmod 11 & \underline{2} & 4 & \underline{8} & 5 & 10 & 9 & \underline{7} & 3 & \underline{6} & 1 \\ \end{matrix}

$n 2^{n} m o d 11 1 \underline{2} 24 3 \underline{8} 4551069 7 \underline{7} 83 9 \underline{6} 101$

$13$ 的原根: 因为下面的计算,

g=2

$g = 2$ 是最小原根, 其他原根上方的

$n$ 与

−

13-1=12

$13 - 1 = 12$ 互素.

‾

\begin{matrix} n & 1 & 2 & 3 & 4 & 5 & 6 & 7 & 8 & 9 & 10 & 11 & 12 \\ {{2}^{n}}\text{ }\bmod 13 & \underline{2} & 4 & 8 & 3 & \underline{6} & 12 & \underline{11} & 9 & 5 & 10 & \underline{7} & 1 \\ \end{matrix}

$n 2^{n} m o d 13 1 \underline{2} 243843 5 \underline{6} 612 7 \underline{11} 89951010 11 \underline{7} 121$

$17$ 的原根: 因为下面的计算,

g=3

$g = 3$ 是最小原根, 其他原根上方的

$n$ 与

−

17-1=16

$17 - 1 = 16$ 互素.

‾

\begin{matrix} n & 1 & 2 & 3 & 4 & 5 & 6 & 7 & 8 & 9 & 10 & 11 & 12 & 13 & 14 & 15 & 16 \\ {{2}^{n}}\text{ }\bmod 17 & 2 & 4 & 8 & 16 & 15 & 13 & 9 & 1 & {} & {} & {} & {} & {} & {} & {} & {} \\ {{3}^{n}}\text{ }\bmod 17 & \underline{3} & 9 & \underline{10} & 13 & \underline{5} & 15 & \underline{11} & 16 & \underline{14} & 8 & \underline{7} & 4 & \underline{12} & 2 & \underline{6} & 1 \\ \end{matrix}

$n 2^{n} m o d 17 3^{n} m o d 17 12 \underline{3} 249 38 \underline{10} 41613 515 \underline{5} 61315 79 \underline{11} 8116 9 \underline{14} 108 11 \underline{7} 124 13 \underline{12} 142 15 \underline{6} 161$

$19$ 的原根: 因为下面的计算,

g=2

$g = 2$ 是最小原根, 其他原根上方的

$n$ 与

−

19-1=18

$19 - 1 = 18$ 互素.

‾

\begin{matrix} n & 1 & 2 & 3 & 4 & 5 & 6 & 7 & 8 & 9 & 10 & 11 & 12 & 13 & 14 & 15 & 16 & 17 & 18 \\ {{2}^{n}}\text{ }\bmod 19 & \underline{2} & 4 & 8 & 16 & \underline{13} & 7 & \underline{14} & 9 & 18 & 17 & \underline{15} & 11 & \underline{3} & 6 & 12 & 5 & \underline{10} & 1 \\ \end{matrix}

$n 2^{n} m o d 19 1 \underline{2} 2438416 5 \underline{13} 67 7 \underline{14} 899181017 11 \underline{15} 1211 13 \underline{3} 1461512165 17 \underline{10} 181$
汇总得到如下结果.

素

数

的

原

根

个

数

(

−

)

的

原

根

\begin{matrix} 素数p & 11 & 13 & 17 & 19 \\ p的原根个数\varphi \left( p-1 \right) & 4 & 4 & 8 & 6 \\ p的原根 & 2,6,7,8 & 2,6,7,11 & 3,5,6,7,10,11,12,14 & 2,3,10,13,14,15 \\ \end{matrix}

$素数 p p 的原根个数 φ (p - 1) p 的原根 114 2, 6, 7, 8 134 2, 6, 7, 11 178 3, 5, 6, 7, 10, 11, 12, 14 196 2, 3, 10, 13, 14, 15$

例子11 (找出一些合数的所有原根)

(1)

{{2}^{2}}=4

$2^{2} = 4$ 仅有1个原根, 为3.

gcd

⁡

(

)

的

指

数

(

)

\begin{matrix} n\text{ }\bmod 4,\text{ }\gcd \left( n,4 \right)=1 & 1 & 3 \\ n的指数 & 1 & 2=\varphi \left( 4 \right) \\ \end{matrix}

$n m o d 4, g cd (n, 4) = 1 n 的指数 11 3 2 = φ (4)$
注表中只考虑

gcd

⁡

(

)

\gcd \left( n,4 \right)=1

$g cd (n, 4) = 1$ 的数

$n$ 的理论依据是博文《指数和原根》定理12, 下同.

(2)

$6$ 仅有1个原根, 为

$5$ .

gcd

⁡

(

)

的

指

数

(

)

\begin{matrix} n\text{ }\bmod 6,\text{ }\gcd \left( n,6 \right)=1 & 1 & 5 \\ n的指数 & 1 & 2=\varphi \left( 6 \right) \\ \end{matrix}

$n m o d 6, g cd (n, 6) = 1 n 的指数 11 5 2 = φ (6)$

(3)

$8$ 没有原根, 因为

(

)

\varphi \left( 8 \right)=4

$φ (8) = 4$ 且

gcd

⁡

(

)

的

指

数

\begin{matrix} n\text{ }\bmod 8,\text{ }\gcd \left( n,8 \right)=1 & 1 & 3 & 5 & 7 \\ n的指数 & 1 & 2 & 2 & 2 \\ \end{matrix}

$n m o d 8, g cd (n, 8) = 1 n 的指数 11325272$

原文链接：https://blog.csdn.net/qq_44261017/article/details/110730361

索引

记号

引理2: 若 p p p是奇素数, 则模 p p p的原根是存在的.

引理3: 设 p p p是素数, 若 d ∣ p − 1 \left. d \right|p-1 d∣p−1, 则一定有 X ( d ) ≠ ∅ X\left( d \right)\ne \varnothing X(d)​=∅.

引理4: 设 p p p为素数, 若 d ∣ p − 1 \left. d \right|p-1 d∣p−1, 则有 ∣ X ( d ) ∣ = φ ( d ) \left| X\left( d \right) \right|=\varphi \left( d \right) ∣X(d)∣=φ(d).

推论5: 设 p p p是素数, d ∣ p − 1 \left. d \right|p-1 d∣p−1, 则有 X ( d ) = { ( a k m o d p ) : gcd ⁡ ( d , k ) = 1 } . X\left( d \right)=\left\{ \left( {{a}^{k}}\bmod p \right):\text{ }\gcd \left( d,k \right)=1 \right\}. X(d)={(akmodp): gcd(d,k)=1}.

推论6: 设 p p p是素数, 则模 p p p的原根有 φ ( p − 1 ) \varphi \left( p-1 \right) φ(p−1)个.

方法7: 设 p p p是素数, 用穷举法求一个数 n ∈ { 1 , 2 , ⋯ , p − 1 } n\in \left\{ 1,2,\cdots ,p-1 \right\} n∈{1,2,⋯,p−1}对模 p p p的指数.

例子8 (用方法7找出一些小素数的所有原根)

方法9: 用推论5和穷举法求一个较大素数 p p p的所有原根.

例子10 (用方法9找出一些较大素数的所有原根)

例子11 (找出一些合数的所有原根)

你可能也喜欢

引理2: 若

引理3: 设 $\left. d \right|p-1 d∣p−1, 则一定有 X ( d ) ≠ ∅ X\left( d \right)\ne \varnothing X(d)=∅.$

引理4: 设 $\left. d \right|p-1 d∣p−1, 则有 ∣ X ( d ) ∣ = φ ( d ) \left| X\left( d \right) \right|=\varphi \left( d \right) ∣X(d)∣=φ(d).$

推论5: 设 $\left. d \right|p-1 d∣p−1, 则有 X ( d ) = { ( a k m o d p ) : gcd ⁡ ( d , k ) = 1 } . X\left( d \right)=\left\{ \left( {{a}^{k}}\bmod p \right):\text{ }\gcd \left( d,k \right)=1 \right\}. X(d)={(akmodp): gcd(d,k)=1}.$

推论6: 设 $\varphi \left( p-1 \right) φ(p−1)个.$

方法7: 设 $n\in \left\{ 1,2,\cdots ,p-1 \right\} n∈{1,2,⋯,p−1}对模 p p p的指数.$

方法9: 用推论5和穷举法求一个较大素数