在模p的既约剩余系中,阶为d的元素的个数恰好有phi(d)个
本帖最后由 mathematica 于 2019-3-24 10:18 编辑模p的既约剩余系显然是一个群,
这个群中的d阶的元素的个数,恰好等于欧拉函数d个,
以前看数论书的时候没注意这个结论,现在注意到了,
分享一下!
Clear["Global`*"];(*Clear all variables*)
n=NextPrime;
Print;(*打印出这个数*)
aa=Select,GCD==1&];(*选择既约剩余系*)
bb=MultiplicativeOrder[#,n]&/@aa;(*计算既约剩余系中的阶*)
bb=Sort;(*排序*)
cc=Tally;(*统计各个阶的个数*)
(*第一列阶,第二列阶的个数,第三列阶的欧拉函数*)
dd=Append[#,EulerPhi[#[]]]&/@cc;
Grid
输出结果
1 1 1
2 1 1
3 2 2
4 2 2
6 2 2
8 4 4
12 4 4
16 8 8
24 8 8
32 16 16
48 16 16
96 32 32
第一列是阶d, 第二列是阶的个数,第三列是阶的欧拉函数phid
根据我的计算结果,似乎只要有原根,那么就相等,而不一定非要是素数
这个结论很美,所以我就发出来,共享给大家!
所有的4k+1素数都能唯一表达成两个正整数的平方米,这个结论也很美!
Clear["Global`*"];(*Clear all variables*)
n=11*37;
Print;(*打印出这个数*)
aa=Select,GCD==1&];(*选择既约剩余系*)
bb=MultiplicativeOrder[#,n]&/@aa;(*计算既约剩余系中的阶*)
bb=Sort;(*排序*)
cc=Tally;(*统计各个阶的个数*)
(*第一列阶,第二列阶的个数,第三列阶的欧拉函数*)
dd=Append[#,EulerPhi[#[]]]&/@cc;
Grid
输出结果
1 1 1
2 3 1
3 2 2
4 4 2
5 4 4
6 6 2
9 6 6
10 12 4
12 8 4
15 8 8
18 18 6
20 16 8
30 24 8
36 24 12
45 24 24
60 32 16
90 72 24
180 96 48
假设d阶元素有m个,那么从上面的结果能得出结果m一定是phi(d)的倍数吗?
其中phi(d)是d的欧拉函数,
我不知道如何证明! 只要是有限交换群都可以 math_humanbeing 发表于 2019-3-23 19:24
翻到p238
你说的是啥书?我的是潘承洞的初等数论第三版,没你说的东西呀 math_humanbeing 发表于 2019-3-24 09:59
见下图
我说的是模为5*3这样的整数的时候,
是不是d阶元的个数是phi(d)的倍数呢?
我问的是这个问题 本帖最后由 mathematica 于 2019-3-24 11:46 编辑
假设m有原根,
那么既约剩余系模m余-1
否则的话模+1
这个结论也挺好的
有原根,那么就是循环群,
有原根的话,d阶元的个数就是phi(d)个,(数值计算表明结果是正确的,但是不知道真假)
这三个结论都很有意思!!!!!!! 这些都是数论中很基本很简单的性质，不是很难。
比如我们可以先证明有原根的情况，使用群论描述就是
i) m阶循环群<g>中，次数为m的元素正好有phi(m)个。这个很显然，所有m次的元素构成的集合就是${g^k| 1\le k\lt m 且(k,m)=1}$,根据phi(.)的定义就知道这个集合元素数目为phi(m)
ii) m阶循环群<g>中，次数为d的元素正好有phi(d)个。这个很显然，我们换成在子群$\lt g^{m/d}\gt$中考虑就退化为问题i)了。
那么如果考虑没有原根的情况，问题就是
iii)有限交换群G中，次数为d的元素数目正好是phi(d)的倍数。
如果不存在次数为d的元素，那么数目0是phi(d)的倍数，满足要求。
不然对于G中任意次数正好为d的元素x,定义$T_x={x^k| 1\le k\lt d, (k,d)=1}$,于是$|T_x|=\varphi(d)$
现在我们只要证明对于G中任意两个次数为d的元素x,y,那么$T_x$和$T_y$要么互不相交，要么相等即可。
我们假设$x^u = y^v$而且$(u,d)=1,(v,d)=1$,于是存在w使得$uw -=1(mod d)$,于是我们得出$x = x^{uw} =y^{vw}$,而且由于$(v,d)=1,(w,d)=1$，所以$(vw,d)=1$,所以得出$x \in T_y$, 同样对于任意$h$使得$(h,d)=1$,我们有$x^h = y^{uwh} \in T_y$,所以$T_x$是$T_y$的子集。同样$T_y$是$T_x$子集，所以两者相等。
所以根据上面的性质我们就得出结论iii) mathe 发表于 2019-3-24 13:14
这些都是数论中很基本很简单的性质，不是很难。
比如我们可以先证明有原根的情况，使用群论描述就是
i) m ...
模是m,元素个数是phi(m), 元素的阶是d, d是phi(m)的约数,
d阶元的个数的phi(d)个
这是m有原根的情况下的情况
页:
[1]