找回密码
 欢迎注册
查看: 19525|回复: 13

[分享] 在模p的既约剩余系中,阶为d的元素的个数恰好有phi(d)个

[复制链接]
发表于 2019-3-23 11:41:56 | 显示全部楼层 |阅读模式

马上注册,结交更多好友,享用更多功能,让你轻松玩转社区。

您需要 登录 才可以下载或查看,没有账号?欢迎注册

×
本帖最后由 mathematica 于 2019-3-24 10:18 编辑

模p的既约剩余系显然是一个群,
这个群中的d阶的元素的个数,恰好等于欧拉函数d个,
以前看数论书的时候没注意这个结论,现在注意到了,
分享一下!
  1. Clear["Global`*"];(*Clear all variables*)
  2. n=NextPrime[96];
  3. Print[n];(*打印出这个数*)
  4. aa=Select[Range[n],GCD[n,#]==1&];(*选择既约剩余系*)
  5. bb=MultiplicativeOrder[#,n]&/@aa;(*计算既约剩余系中的阶*)
  6. bb=Sort[bb];(*排序*)
  7. cc=Tally[bb];(*统计各个阶的个数*)
  8. (*第一列阶,第二列阶的个数,第三列阶的欧拉函数*)
  9. dd=Append[#,EulerPhi[#[[1]]]]&/@cc;
  10. Grid[dd]
复制代码


输出结果

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素数都能唯一表达成两个正整数的平方米,这个结论也很美!
毋因群疑而阻独见  毋任己意而废人言
毋私小惠而伤大体  毋借公论以快私情
 楼主| 发表于 2019-3-23 11:58:03 | 显示全部楼层
  1. Clear["Global`*"];(*Clear all variables*)
  2. n=11*37;
  3. Print[n];(*打印出这个数*)
  4. aa=Select[Range[n],GCD[n,#]==1&];(*选择既约剩余系*)
  5. bb=MultiplicativeOrder[#,n]&/@aa;(*计算既约剩余系中的阶*)
  6. bb=Sort[bb];(*排序*)
  7. cc=Tally[bb];(*统计各个阶的个数*)
  8. (*第一列阶,第二列阶的个数,第三列阶的欧拉函数*)
  9. dd=Append[#,EulerPhi[#[[1]]]]&/@cc;
  10. Grid[dd]
复制代码


输出结果
  1. 1        1        1
  2. 2        3        1
  3. 3        2        2
  4. 4        4        2
  5. 5        4        4
  6. 6        6        2
  7. 9        6        6
  8. 10        12        4
  9. 12        8        4
  10. 15        8        8
  11. 18        18        6
  12. 20        16        8
  13. 30        24        8
  14. 36        24        12
  15. 45        24        24
  16. 60        32        16
  17. 90        72        24
  18. 180        96        48

复制代码

假设d阶元素有m个,那么从上面的结果能得出结果m一定是phi(d)的倍数吗?
其中phi(d)是d的欧拉函数,
我不知道如何证明!

点评

我听说过有个处理循环群的凯莱定理——就是不知道这玩意是啥以及该怎么用  发表于 2019-3-25 15:09
毋因群疑而阻独见  毋任己意而废人言
毋私小惠而伤大体  毋借公论以快私情
发表于 2019-3-23 14:58:56 来自手机 | 显示全部楼层
只要是有限交换群都可以

点评

我觉得这个结论很美,所以我发出来共享给大家  发表于 2019-3-24 09:32
我在二楼的回答看了吗  发表于 2019-3-23 16:00
毋因群疑而阻独见  毋任己意而废人言
毋私小惠而伤大体  毋借公论以快私情
 楼主| 发表于 2019-3-24 09:27:41 | 显示全部楼层

你说的是啥书?我的是潘承洞的初等数论第三版,没你说的东西呀
毋因群疑而阻独见  毋任己意而废人言
毋私小惠而伤大体  毋借公论以快私情
 楼主| 发表于 2019-3-24 10:12:55 | 显示全部楼层

我说的是模为5*3这样的整数的时候,
是不是d阶元的个数是phi(d)的倍数呢?
我问的是这个问题
毋因群疑而阻独见  毋任己意而废人言
毋私小惠而伤大体  毋借公论以快私情
 楼主| 发表于 2019-3-24 11:45:30 | 显示全部楼层
本帖最后由 mathematica 于 2019-3-24 11:46 编辑

假设m有原根,
那么既约剩余系模m余-1
否则的话模+1
这个结论也挺好的

有原根,那么就是循环群,

有原根的话,d阶元的个数就是phi(d)个,(数值计算表明结果是正确的,但是不知道真假)

这三个结论都很有意思!!!!!!!
毋因群疑而阻独见  毋任己意而废人言
毋私小惠而伤大体  毋借公论以快私情
发表于 2019-3-24 13:14:58 | 显示全部楼层
这些都是数论中很基本很简单的性质,不是很难。
比如我们可以先证明有原根的情况,使用群论描述就是
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)
毋因群疑而阻独见  毋任己意而废人言
毋私小惠而伤大体  毋借公论以快私情
 楼主| 发表于 2019-3-24 13:43:55 | 显示全部楼层
mathe 发表于 2019-3-24 13:14
这些都是数论中很基本很简单的性质,不是很难。
比如我们可以先证明有原根的情况,使用群论描述就是
i) m ...

模是m,元素个数是phi(m), 元素的阶是d, d是phi(m)的约数,
d阶元的个数的phi(d)个

这是m有原根的情况下的情况

点评

是啊,这就是我说的i)和ii)。有原根,就是对应的群是循环群<g>  发表于 2019-3-24 13:56
毋因群疑而阻独见  毋任己意而废人言
毋私小惠而伤大体  毋借公论以快私情
您需要登录后才可以回帖 登录 | 欢迎注册

本版积分规则

小黑屋|手机版|数学研发网 ( 苏ICP备07505100号 )

GMT+8, 2024-3-29 17:03 , Processed in 0.047699 second(s), 18 queries .

Powered by Discuz! X3.5

© 2001-2024 Discuz! Team.

快速回复 返回顶部 返回列表