原根

hbghlyj

$\gcd(a,m)=1$时，定义$a$模$m$的阶$δ_m(a)$为使$a^d≡1\pmod{m}$成立的最小的正整数$d$。
由欧拉定理知$δ_m(a)\le φ(m)$，若取等，则称$a$是$\bmod m$的原根。
原根的存在性(Gauss,1801)
模$m$有原根的充要条件是$m=1,2,4,p^k,2p^k$，其中$p$是奇质数，$k$是任意正整数。
必要性证明见2#
充分性证明见3.5. Existence of primitive roots
One of our main aims in this chapter is to prove the following result.
Proposition 3.2. Let $p$ be a prime. Then there is an element $g \in(\mathbb{Z} / p \mathbb{Z})^{\times}$ with $\operatorname{ord}_p(g)=p-1$. Equivalently, $(\mathbb{Z} / p \mathbb{Z})^{\times}$is a cyclic group.

Remarks

An element $g$ with this property is called a primitive root modulo $p$. For some reason, use of the letter $g$ in this context is quite common. If $a$ is an integer whose reduction modulo $p$ has this property then we also call $g$ a primitive root modulo $p$; in fact this usage is more common. If $g$ is a primitive root then, by definition, a complete list of the elements of $(\mathbb{Z} / p \mathbb{Z})^{\times}$is $\left\{1+p \mathbb{Z}, g+p \mathbb{Z}, g^2+\right.$ $\left.p \mathbb{Z}, \ldots, g^{p-2}+p \mathbb{Z}\right\}$. For example, working $\bmod 11$ we have $\left\{1,2,2^2, 2^3, \ldots, 2^9\right\} \equiv$ $\{1,2,4,8,5,10,9,7,3,6\}$, so 2 is a primitive root modulo 11. Let us remark in passing that it is an unsolved problem (Artin's Conjecture) whethe 2 is a primitive root for infinitely many primes $p$.

Proposition 3.3. Let $f(X) \in R[X]$ be a polynomial of degree $d \geqslant 0$ over an integral domain $R$. Then $f$ has at most $d$ roots in $R$.

Proof

If $f$ has no roots we are done, so let's suppose $\alpha \in R$ is a root.
By the division algorithm for polynomials $f(X)=(X-\alpha) q(X)+c$ for some $c \in R$. (See Prelims for polynomials over the reals; the same works for a general integral domain.) Thus $0=(\alpha-\alpha) q(\alpha)+c$ so $c=0$. Now let $\beta \in R$ be any other root of $f(x)$. Then $0=f(\beta)=(\alpha-\beta) q(\beta)$ and since $\alpha-\beta \neq 0$ and $R$ is an integral domain, we deduce that $q(\beta)=0$. But $q$ is a polynomial of degree $d-1$ and so by induction has $\leqslant d-1$ roots. Hence $f$ has at most $1+(d-1)=d$ roots.

LEMMA 3.4. Let $p$ be a prime, and suppose that $d \mid p-1$. Then there are exactly $d$ values of $x \in \mathbb{Z} / p \mathbb{Z}$ such that $x^d \equiv 1\pmod p$.

Proof

The polynomial $X^d-1$ is a factor of $X^{p-1}-1$ :
$$
X^{p-1}-1=\left(X^d-1\right) g(X)
$$
where
$$
g(X)=1+X^d+X^{2 d}+\cdots+X^{\left(\frac{p-1}{d}-1\right) d}
$$
By Fermat's Little Theorem, every $x \in(\mathbb{Z} / p \mathbb{Z})^{\times}$is a root of the left hand side. By Proposition 3.3 , at most $\operatorname{deg} g=p-1-d$ of these can be roots of $g$. The other $d$ values of $x$ must therefore be roots of $X^d-1$. By Proposition 3.3, this polynomial cannot have more than these $d$ roots.

LEMMA 3.5. Suppose that $p$ is a prime. Let $q$ be another prime and suppose that $q^c \mid p-1$ for some integer $c$. Then there is some $a \in(\mathbb{Z} / p \mathbb{Z})^{\times}$with $\operatorname{ord}_p(a)=q^c$.

Proof

By Lemma 3.4, there are $q^c$ values of $x \in(\mathbb{Z} / p \mathbb{Z})^{\times}$with $x^{q^c} \equiv 1\pmod p$. have $\operatorname{ord}_p(x) \mid q^{c-1}$ and hence $x^{q^{c-1}} \equiv 1\pmod p$. By Lemma 3.4 again, the number of elements with this property is $q^{c-1}$. Therefore there are $q^c-q^{c-1}>0$ elements $x$ with $\operatorname{ord}_p(x)=q^c$.

Proof of Proposition 3.2

Factor $p-1=q_1^{c_1} \ldots q_k^{c_k}$ as a product of primes. By Lemma 3.5, there are elements $a_i \in(\mathbb{Z} / p \mathbb{Z})^{\times}$with $\operatorname{ord}_p\left(a_i\right)=q_i^{c_i}$. Set $a:=a_1 \cdots a_k$. By Lemma $3.3, \operatorname{ord}_p(a)=q_1^{c_1} \cdots q_k^{c_k}=p-1$

hbghlyj

该证明分为几个部分，能够涵盖所有情况。

2和4有原根
1是2的原根
3是4的原根,因为$\phi \left({4}\right) = 2$和$3^2  \equiv 1 \pmod 4$
比4大的2的幂没有原根
设$n = 2^k$其中$k \ge 3$.注意到$\phi \left({2^k}\right) = 2^{k - 1}$.
要证明,对任意奇数$a$存在正整数$r < 2^{k-1}$使$a^r \equiv 1 \pmod {2^k}$.
我们要证明$r = 2^{k - 2}$具有这个性质,用归纳法:
对任意$k \inN_+$,设$P \left({k}\right)$为命题:$a^{{2^{k - 2} }} \equiv 1 \pmod {2^k}$
P(3)为真,证明如下:
$k = 3 \implies 2^k = 8, 2^{k - 2} = 2^1 = 2$
<8的奇数为1,3,5,7.它们的平方$\equiv1\pmod8$
所以P(3)为真.

归纳假设:$P \left({h}\right)$:$a^{{2^{h - 2} }} \equiv 1 \pmod {2^h}$,其中$h \ge 3$,
要证明$P \left({h + 1}\right)$:$a^{{2^{h - 1} }} \equiv 1 \pmod {2^{h + 1} }$.

归纳步骤:
归纳假设可以写成:$\exists m \inZ: a^{{2^{h - 2} }} = 1 + m 2^h$
因此$ \left({a^{{2^{h - 2} }} }\right)^2 = \left({1 + m 2^h}\right)^2= 1 + 2 \left({m 2^h}\right) + \left({m 2^h}\right)^2
= 1 + 2^{h + 1} \left({m + m^2 2^{h - 1} }\right) \equiv1\pmod {2^{h + 1} }$
但$ \left({a^{{2^{h - 2} }} }\right)^2 = a^{{2^{h - 2} }} a^{{2^{h - 2} }} = a^{\left({2^{h - 2} + 2^{h - 2} }\right)}= a^{2 \left({2^{h - 2} }\right)}= a^{{2^{h - 1} }}$
所以$P \left({h}\right) \implies P \left({h+1}\right)$.
所以$\forall k \ge 3: a^{{2^{k-2} }} \equiv 1 \pmod {2^k}$
有两个奇质因数的整数无原根
取n=rs其中r>2,s>2,$r \perp s$.
设$a \perp r s$.
因为>2的整数的欧拉函数都是偶数,所以$\phi \left({r}\right)$和$\phi \left({s}\right)$都是偶数.
令$k =\dfrac {\phi(r)\phi(s)} 2$,显然$k$是整数.
因为$a \perp r s$我们有$a \perp r$,由欧拉定理$a^{\phi \left({r}\right)} \equiv 1 \pmod r$
$a^k= \left({a^{\phi \left({r}\right)} }\right)^{\frac {\phi \left({s}\right)} 2} \equiv
\left({1}\right)^{\frac {\phi \left({s}\right)} 2} \pmod r\equiv1\pmod r$
交换r和s的角色,同理有$a^k \equiv 1 \pmod s$
又n=rs,所以$a^k \equiv 1 \pmod n$.
其中$k = \dfrac {\phi \left({n}\right)} 2 < \phi \left({n}\right)$.
所以n无原根.

hbghlyj

2#是从proofwiki翻译的. 相关的中文网页: 数论阶–百度百科 孔坛杏门 具体数学 _________________ 抄一下bilibili.com/read/cv15627069:
隐藏/显示

（本文适合高中） 初等数论中的阶是一个十分重要的概念，有许多数学竞赛题目是依此而出的。与阶相对应的，还有“半阶”这个概念。所谓半阶，顾名思义，其实就是“阶的一半”。但是现有的竞赛辅导书上大多没有关于半阶这方面的知识，所以写下这篇关于半阶的学习笔记。 下面首先给出半阶的严格定义。 定义1：当$m\geq 3,(a,m)=1$时，若存在正整数$x$使得$a^x\equiv -1\pmod p$，我们将满足该式的最小的正整数$\tau $称为$a$关于模$m $的半阶。 注：半阶不一定总存在。例如，2关于模7的半阶就不存在。 下面给出几个关于半阶的基本性质。这些性质是平凡的，但在解决某些问题中可以发挥出巨大无比的作用。 性质1（半阶为阶的一半）：若$a$关于模$m$的阶为$\lambda $，半阶为$\tau $，则$\lambda =2\tau $。 证明：$a^\tau \equiv -1\pmod m\Rightarrow a^{2\tau}\equiv 1\pmod m\Rightarrow \lambda \vert 2\tau $（阶的性质） 若$\tau >\lambda $，则$a^{\tau -\lambda }\equiv a^{\tau -\lambda }a^\lambda \equiv a^\tau \equiv -1\pmod m$， 而$0<\tau -\lambda <\tau $，这与$\tau $的最小性矛盾。所以$\tau <\lambda $，从而$\tau =\lambda $。$□$ 注：若$a$关于模$m$的阶为奇数，则$a$关于模$m$一定不存在半阶；若$a$关于模$m$的阶为偶数，则$a$关于模$m$也不一定存在半阶（例如，考虑2关于模15的阶和半阶）。 性质2（常用）：设$a$关于模$m$的半阶为$\tau $，若正整数$x$使得$a^x\equiv -1\pmod m$则$\tau $为$m$的奇数倍。 证明：$a^x\equiv -1\pmod m\Rightarrow a^{2x}\equiv 1\pmod m\Rightarrow 2\tau \vert 2x\Rightarrow \tau \vert x$ 且$-1\equiv a^x\equiv (a^\tau )^{\frac{x}{\tau } }\equiv (-1)^{\frac{x }{\tau}}\pmod m \Rightarrow \frac{x}{\tau} $为奇数。$□$ 由上面的性质2，容易证明下面的一个重要推论。该推论在解题过程中常可作为引理给出。 推论3：设正整数$v >1$，$p$为$v^{2^n}+1$的一个素因子，则$2^{n+1}\vert (p-1)$。 证明：设$v$关于模$p$的半阶为$\tau $，由性质2，则$\tau \vert 2^n$，且$\frac{2^n}{\tau} $为奇数，从而$\tau =2^n$。 又由Fermat小定理，$v^{p-1}\equiv 1\pmod p\Rightarrow \lambda \vert (p-1)\Rightarrow 2\tau \vert (p-1)\Rightarrow 2^{n+1}\vert (p-1)$ 这里$\lambda $表示$v$关于模$p $的阶。$□$ 下面还有推论3的一个当$v=2$时特殊情况，它给出了一个更强的结果。 推论4：设正整数$n\geq 2$，$p$为$F_n=2^{2^n}+1$（Fermat数）的一个素因子，则$2^{n+2}\vert (p-1)$。 证明：因为$F_{n-1}^{2^{n+1}}=((2^{2^{n-1}}+1)^2)^{2^n}=(F_n+2^{2^{n-1}+1})^{2^n}\equiv (2^{2^{n-1}+1})^{2^n}$ $=(2^{2^n})^{2^{n-1}+1}\equiv (-1)^{2^{n-1}+1}\equiv -1\pmod{F_n}$所以$F_n\vert (F_{n-1}^{2^{n+1}}+1)\Rightarrow p\vert (F_{n-1}^{2^{n+1}}+1)$，由推论3知$2^{n+2}\vert (p-1)$。$□$ （未完待续……）

hbghlyj

en.m.wikipedia.org/wiki/Multiplicative_group_of_integers_modulo_n
The group $(\mathbb {Z} /n\mathbb {Z} )^{\times }$ is cyclic if and only if $n$ is 1, 2, 4, $p^k$ or $2p^k$, where $p$ is an odd prime and $k > 0$. For all other values of n the group is not cyclic.[1][2][3] This was first proved by Gauss.[4]

This means that for these $n$:

$(\mathbb {Z} /n\mathbb {Z} )^{\times }\cong \mathrm {C} _{\varphi (n)},$ where $\displaystyle \varphi (p^{k})=\varphi (2p^{k})=p^{k}-p^{k-1}.$
By definition, the group is cyclic if and only if it has a generator $g$ (a generating set $\{g\}$ of size one), that is, the powers ${\displaystyle g^{0},g^{1},g^{2},\dots ,}$ give all possible residues modulo $n$ coprime to $n$ (the first ${\displaystyle \varphi (n)}$ powers ${\displaystyle g^{0},\dots ,g^{\varphi (n)-1}}$ give each exactly once). A generator of $(\mathbb{Z}/n\mathbb{Z})^\times$ is called a primitive root modulo $n$.[5] If there is any generator, then there are ${\displaystyle \varphi (\varphi (n))}$ of them.

en.m.wikipedia.org/wiki/Primitive_root_modulo_n

Czhang271828

似乎提过. 这类贴也可以考虑汇总了

hbghlyj

这份2014年讲义的第48页有一个相关的定理隐藏/显示

Theorem 163 Let $G$ be a finite group with $|G|=2 p$ where $p \geqslant 3$ is prime. Then $G$ is isomorphic to $C_{2 p}$ or $D_{2 p}$. Proof. Assume that $G$ is not cyclic. The possible orders of elements in $G$ are 1 (the identity $e)$ or 2 or $p$. As $|G|=2 p$ is even then there is an element $x \in G$ of order 2 . (Corollary 162). Further if $g^{2}=e$ for all $g \in G$ then $G \cong\left(\mathbb{Z}_{2}\right)^{n}$ for some $n$ (Exercise Sheet 4 , Question 5), which is not possible here and hence there is an element $y \in G$ of order $p$. As $x$ has order 2 and $y, y^{2}, \ldots, y^{p-1}$ have order $p$ then $x \notin\langle y\rangle$. Hence $G=\langle y\rangle \cup x\langle y\rangle$ or more expansively $$ G=\left\{e, y, y^{2}, \ldots, y^{p-1}, x, x y, x y^{2}, \ldots, x y^{p-1}\right\} $$ Now the product $y x$ is somewhere amongst $G$. If $y x=y^{i}$ we arrive at a similar contradiction to before. So $y x=x y^{j}$ for some $1 \leqslant j< p$. Then $$ (y x)^{2}=y x y x=(y x)\left(x y^{j}\right)=y^{j+1} ; \quad(y x)^{3}=\left(x y^{j}\right)(y x)^{2}=x y^{2 j+1} $$ until more generally we find that $(y x)^{2 k}=y^{k(j+1)}$ and that $(y x)^{2 k+1}=x y^{k j+k+j}$. So $y x$ has an even order and $o(y x)=2$. In particular it follows that $j=p-1$. Hence $$ G=\left\langle x, y: x^{2}=y^{p}=e, y x=x y^{p-1}\right\rangle $$ which is a presentation for $D_{2 p}$. We can think of $x$ as reflection in a given axis and $y$ as clockwise rotation through $2 \pi / p$.

hbghlyj

抄一下Brilliant wiki

Finding Primitive Roots

The proof of the theorem (part of which is presented below) is essentially non-constructive: that is, it does not give an effective way to find a primitive root when it exists. Once one primitive root $ g $ has been found, the others are easy to construct: simply take the powers $ g^a,$ where $ a$ is relatively prime to $ \phi(n)$. But finding a primitive root efficiently is a difficult computational problem in general. There are some special cases when it is easier to find them. Here is an example:

Suppose $ p $ is a prime such that $ 2p+1 $ is also prime. (Such $ p $ are called Sophie Germain primes.) Show that if $ p \equiv 1 $ mod $4$, then $2 $ is a primitive root mod $ 2p+1 $.

---

The point is that the list of possible orders of elements of $ {\mathbb Z}_{2p+1}^* $ is very short: the order of $ 2 $ divides $ \phi(2p+1) = 2p $, so it is either $ 1,2,p,$ or $2p$. It can't be $ 1 $ or $ 2 $, so we only need to rule out $ p $. But $ 2^p \equiv \left( \frac2{2p+1} \right) $ mod $ 2p+1 $, where $ \left( \frac2{2p+1} \right) $ is the Legendre symbol; this is by Euler's criterion. But by the second supplement to quadratic reciprocity, $ \left( \frac2{2p+1} \right) =-1$ because $ 2p+1 \equiv 3 $ mod $ 8 $.

So the only remaining possibility is that the order of $ 2 $ mod $ 2p+1 $ is $ 2p $. $_\square $

For instance, this shows that $ 2 $ is a primitive root mod $ 83 $.

Applications

When there is a primitive root $ g$ mod $ n $, the elements of $ {\mathbb Z}_n^* $ can be written as $ 1, g, g^2, \ldots, g^{\phi(n)-1} $. Multiplying two elements corresponds to adding their exponents mod $ \phi(n). $ That is, the multiplicative arithmetic in $ {\mathbb Z}_n^* $ reduces to additive arithmetic in $ {\mathbb Z}_{\phi(n)} $.

Let $ k $ be an integer and $ p $ an odd prime number. How many nonzero $k^\text{th}$ powers are there mod $ p?$

---

The question certainly depends on the relationship between $ k$ and $ p$. When $ k=2,$ the answer is $ \frac{p-1}2 $ (see quadratic residues), but when $ k = p-1, $ the answer is $ 1 $ (by Fermat's little theorem).

As an illustration, take $ k = 9, p = 13 $. Then it's easy to check that $ g=2 $ is a primitive root mod $ p$. The ninth powers mod $ p $ are $ 2^0, 2^9, 2^{18}, 2^{27}, \ldots $, but we can consider the exponents mod $ 12 $ because $ 2^{12} \equiv 1 $. So we get

$$2^0, 2^9, 2^6, 2^3, 2^0, \ldots,$$

so there are four $9^\text{th}$ powers mod $ 13 $. The exponents are multiples of $ 3$, which is gcd$(9,13-1)$. There are $\frac{13-1}3 = 4$ of these.

In general, since every nonzero element of $ {\mathbb Z}_p $ can be written as $ g^a $ mod $ p $ for some integer $ x $, the equation $ x^k \equiv y $ mod $ p $ can be rewritten $ (g^a)^k \equiv g^b, $ or $ g^{ak-b} \equiv 1 $ mod $ p $. Because $ g $ is a primitive root, this happens if and only if $ (p-1)|(ak-b) $, so $ ak \equiv b $ mod $ p -1 $.

So the question becomes, "As $ a $ ranges over $ {\mathbb Z}_{p-1} $, how many values can $ ak $ mod $ p-1 $ take on?" In fact, the extended Euclidean algorithm implies that $ \big\{ak+(p-1)c : k, c \in {\mathbb Z}\big\} $ is the set of multiples of gcd$(k,p-1)$. There are exactly

$$\frac{p-1}{\text{gcd}(k,p-1)}$$

such values, so this is the answer. $_\square$

Here is another problem where it can help to write the elements of $ {\mathbb Z}_p^* $ as powers of a primitive root.

Submit your answer

Find the smallest positive prime divisor of

$$1^{60}+2^{60} + 3^{60}+ \cdots + 33^{60}.$$

---

Partial Proof of the Theorem

One half of this theorem is not hard to prove: Suppose $ n = ab, $ where $ a$ and $ b$ are relatively prime and $ \ge 3 $. Suppose $ x $ is relatively prime to $ ab $. Then since $ x^{\phi(a)} \equiv 1 $ mod $ a $ and $ x^{\phi(b)} \equiv 1 $ mod $ b $, it follows that $x^{\text{lcm}\big(\phi(a),\phi(b)\big)} \equiv 1 $ mod $ ab $.

But $ \phi(a) $ and $ \phi(b) $ are both even, so their LCM is strictly less than their product. So the order of $ x $ is strictly less than $ \phi(a)\phi(b) = \phi(ab) $. So there is no primitive root mod $ ab $.

The only $ n $ that cannot be written in this way are $ 1,2,4,p^k,2p^k,$ and higher powers of $ 2 $. But for any odd $ x $,

$$x^{2^{k-2}} \equiv 1 \pmod{2^k} \ (k \ge 3),$$

which can be proved by the LTE lemma (or by induction). Since $\phi(2^k) = 2^{k-1}$, there is no primitive root mod $ 2^k $ for $ k \ge 3 $.

Some of the proof of the other direction can be found in the wiki on orders.