免費論壇 繁體 | 簡體
Sclub交友聊天~加入聊天室當版主
分享
返回列表 发帖

[数论] 关于欧拉定理的疑问

本帖最后由 longzaifei 于 2014-3-26 08:44 编辑

欧拉定理:若 $n,a$为正整数且互素,则 $ a^{\varphi(n)} \equiv 1 (\mod n ) $。

$\varphi(n)$不一定是最小的使上式成立的正整数。
我想问的是:如果使上式成立的最小正整数不是$\varphi(n)$,那么一定是$\varphi(n)$的二分之一,或者四分之一,或者八分之一。。???
分享到: QQ空间QQ空间 腾讯微博腾讯微博 腾讯朋友腾讯朋友

本原根?

TOP

老问题了, 这个问题可以用简单的群论基本讲透. 我们大致分为这么几步进行.

Step 1. $(\mathbb Z_n,+)$ 对加法构成群, 但对乘法不一定. 我们记 $\mathbb Z_n^*:=\{a:\gcd(a,n)=1\}$, 则 $(\mathbb Z_n^*,\cdot)$ 构成群.

所谓群就是带有某一二元运算 $\ast$ 的集合 $S$ 满足 $\forall x,y\in S$ 都有 $x\ast y\in S$, 即二元运算封闭性. 此外存在单位元 $e\in S$ 使得 $\forall x\in S$ 都有 $xe=ex=x$. 对任意 $x\in S$ 存在逆元 $y$ 使得 $xy=yx=e$. 此处易证明单位元和逆元均唯一.

Step 2. 记 $p_i$ 为第 $i$ 个质数, 设 $n$ 的准素分解为 $n=\prod_{i\geq 1}p_i^{n_i}$. 根据中国剩余定理有

$$
\mathbb Z_n^*=\oplus_{i\geq 1}\mathbb Z_{p_i^{n_i}}^*
$$

此处 $\oplus$ 为直和, 即 $\mathbb Z_n^*$ 可以和 $\{(x_1,x_2,\ldots):x_i\in \mathbb Z_{p_i^{n_i}}^*\}$ 一一对应.

Step 3. 由群论知识可得
1. $(\mathbb Z_2^*,\cdot )\cong (\{0\},+)$.
2. $(\mathbb Z_{2^{n+2}}^*,\cdot)\cong (\mathbb Z_{2^n}\oplus \mathbb Z_2,+)$ for any $n=0,1,2,\ldots$.
3. $(\mathbb Z_{p^n}^*,\cdot)\cong (\mathbb Z_{p^n-p^{n-1}},\cdot)$ for any prime number except $2$.

例如对 $\mathbb Z_8^*=\{1,3,5,7\}$ 而言, 有对应
$$
\begin{align*}
\cdot\quad&\Leftrightarrow &&+\\
\mathbb Z_8^*\quad&\Leftrightarrow &&\mathbb Z_2\oplus\mathbb Z_2\\
1\quad&\Leftrightarrow &&(0,0)\\
3\quad&\Leftrightarrow &&(1,0)\\
5\quad&\Leftrightarrow &&(0,1)\\
7\quad&\Leftrightarrow &&(1,1)\\
3\cdot 5\equiv 7\quad&\Leftrightarrow && (1,0)+(0,1)=(1,1)
\end{align*}
$$
Step 4. 由有限 Abel 群分类定理知, 对任意互质的整数 $a,b$, 均有 $\mathbb Z_{ab}\cong\mathbb Z_a\times \mathbb Z_b$. 于是我们可得到以下结论:

Ex 1. 以 $n=360$ 为例, 所有与 $360$ 互质的元素同构于群
$$
\begin{align*}
\mathbb Z_{360}^*\cong & \mathbb Z_{8}^*\oplus \mathbb Z_{9}^*\oplus \mathbb Z_{5}^*\\
\cong&(\mathbb Z_2\oplus\mathbb Z_2)\oplus \mathbb Z_6\oplus\mathbb Z_4\\
\cong& \mathbb Z_2\oplus \mathbb Z_2\oplus \mathbb Z_2\oplus \mathbb Z_3\oplus \mathbb Z_4
\end{align*}
$$
从而与 $360$ 互质的元素可以写作 $(a,b,c,d,f)$ 的形式, 其中 $a,b,c\in\mathbb Z_2$, $d\in\mathbb Z_3$, $f\in\mathbb Z_4$. 由于有限群 $G$ 中任意元素 $x$ 满足 $x^{|G|}=e$, 从而
$$
a^{12}\equiv 1\mod 360.
$$
是不是远小于 $\varphi(360)=96$?

求出这些数也简单, 观察 $\mathbb Z_2\oplus \mathbb Z_2\oplus \mathbb Z_2\oplus \mathbb Z_3\oplus \mathbb Z_4$, 每个群的循环阶数为 $(2,2,2,3,4)$, 其中 $3$ 与 $4$ 为主要的循环阶数. 顺着往前, 即是$\mathbb Z_9^*$ 中的 $3$ 阶或 $6$ 阶元 $\{2,4,5,7\}$ 与 $\mathbb Z_5^*$ 中的 $4$ 阶元 $\{2,4\}$ 了. 从而使得 $a^{12}\equiv 1\mod 360$ 取等的 $a$ 为
$$
\{a:a\equiv 2,4,5,7\mod 9\}\cap \{a:a\equiv 2,4\mod 5\}
$$
共 $64$ 个元素.

Prop. 由上述步骤可知, 不等式中指数 $\varphi(n)$ 能取到若且仅若 $n$ 为以下中的一者: $1$, $2$, $4$, 奇素数幂, 或两倍奇素数幂. 此时 $\mathbb Z_n^*$ 无非 $\varphi(p)$ 阶循环群. 循环群生成元数量即原根数量, 为 $\varphi(\varphi(n))$.
1

评分人数

无钱佮歹看、无样佮歹生、无汉草佮无文采、无学历佮无能力、无高度无速度无力度共闲无代记。(闽南话)
口号:珍爱生命,远离内卷。

TOP

返回列表 回复 发帖