In mathematics you don't understand things, you just get used to them.

阶(multiplicative order)

$\textbf{Def.}$:$\delta_m(a)$ 为最小的 $n$ 使得 $a^n\equiv 1\pmod m$,其中 $(a,m)=1$。

Observation 1:$\boxed{a^0\not\equiv a^1\not\equiv\dots\not\equiv a^{\delta_m(a)-1}\pmod m}$。

$\textbf{Proof}$:若 $\exists i,j,s.t.0\leqslant i<j<\delta_m(a),a^i\equiv a^j\pmod m$,则 $a^{i-j}\equiv 1\pmod m$,又 $i-j<\delta_m(a)$,矛盾。

$\blacksquare$

Observation 2:$\boxed{\delta_m(a)\mid\varphi(m)}$。

$\textbf{Proof}$:由欧拉定理: $a^{\varphi(m)}\equiv 1\pmod m$,因为 $1^x=1$,所以如果存在 $x_0$ 使得 $a^{x_0}\equiv 1\pmod m$,那么 $x_0$ 倍数也一定可以,也就是说存在周期性,所以 $\delta_m(a)\mid\varphi(m)$。BTW,同时也有若 $a^n\equiv 1\pmod m$,则 $\delta_m(a)\mid n$。

$\blacksquare$

顺便可以知道若 $a^p\equiv a^q\pmod m$,则 $p\equiv q\pmod{\delta_m(a)}$。

Lemma 1:设 $m\in\mathbb{N}^*$,$a,b\in\mathbb{Z}$,$(a,m)=(b,m)=1$,则 $\boxed{\delta_m(ab)=\delta_m(a)\delta_m(b)}$ 的重要条件是 $(\delta_m(a),\delta_m(b))=1$。

$\textbf{Proof}$:略,具体见此处。

Lemma 2:设 $k\in\mathbb{N}$,$m\in\mathbb{N}^*$,$a\in\mathbb{Z}$,$(a,m)=1$,则 $\boxed{\delta_m(a^k)=\frac{\delta_m(a)}{(\delta_m(a),k)}}$。

$\textbf{Proof}$:略,具体见此处。

原根(primitive root)

$\textbf{Def.}$:对于 $(a,m)=1$,若 $\delta_m(a)=\varphi(m)$,则称 $a$ 是模 $m$ 的原根。

Lemma 1(判定定理):设 $m\geqslant3$,$(a,m)=1$,则 $a$ 为模 $m$ 的原根当且仅当 $\boxed{\forall p\in\mathbb{P},p\mid\varphi(m),a^{\frac{\varphi(m)}{p}}\not\equiv1\pmod m}$。

$\textbf{Proof}$:必要性显然,充分性证明见此处。

Lemma 2(数量定理):若 $m$ 存在原根,则其原根数量为 $\boxed{\varphi(\varphi(m))}$。

$\textbf{Proof}$:略,具体见此处。

Lemma 3(存在定理):$m$ 存在原根当且仅当 $\boxed{m=2,4,p^\alpha,2p^\alpha}$,其中 $p$ 为奇素数,$a\in\mathbb{N}^*$。

$\textbf{Proof}$:略,具体见此处。

若 $m$ 存在原根,则最小原根 $\leqslant m^\frac{1}{4}$。

maths number theory

「tricks」平凡二分幻术
上一篇 «
「codechef - STRQUER」Strange Queries
» 下一篇