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

mathematica

模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素数都能唯一表达成两个正整数的平方米,这个结论也很美!

mathematica

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
    
19. 
    

复制代码

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

mathe

只要是有限交换群都可以

mathematica

math_humanbeing 发表于 2019-3-23 19:24
翻到p238

你说的是啥书?我的是潘承洞的初等数论第三版,没你说的东西呀

mathematica

math_humanbeing 发表于 2019-3-24 09:59
见下图

我说的是模为5*3这样的整数的时候,
是不是d阶元的个数是phi(d)的倍数呢?
我问的是这个问题

mathematica

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

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

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

这三个结论都很有意思!!!!!!!

mathe

这些都是数论中很基本很简单的性质，不是很难。
比如我们可以先证明有原根的情况，使用群论描述就是
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)

mathematica

mathe 发表于 2019-3-24 13:14
这些都是数论中很基本很简单的性质，不是很难。
比如我们可以先证明有原根的情况，使用群论描述就是
i) m ...

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

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