多语言展示
当前在线:640今日阅读:138今日分享:34

数论:完系与缩系(Mathematica)

介绍使用Mathematica处理数论中的完系,缩系这些概念,互素判断,以及简要介绍欧拉函数。
工具/原料

Mathematica

方法/步骤
1

首先,我们分别以m=3和m=5为例,看看模m的完系概念。如果每个整数都与并且只与一个集合中的一个数模m同余,就称作这个集合是模m的完系。集合{0,1,2...m-1}就是一个完系。图中的s都是模m的完系。

2

使用CoprimeQ函数判断两个数是否互素。使用Count[%,True]统计前一个输出列表中True的个数。结果为4,也就是说,在完系中有4个数与m互素。这写与m互素的数,组成的集合叫做模m的缩系。

3

下面,我们令m=1~20,比较这种互素计数结果和欧拉函数EulerPhi[m]的值,发现他们是相等的。实际上,欧拉函数就是与m互素的同余类的个数,也就是完系中与m互素的元素的个数,就是缩系中元素个数。

4

关于互素的判定,有一些约定。1和任何元素互素,于是也和0互素,也和自身互素。0与1之外的元素都不互素。所以EulerPhi[0]==1,EulerPhi[1]==1。

5

EulerPhi并不是一个可逆函数,也就是说欧拉函数多个输入值,可能对应一个输出值。但是,当输入为素数p时,输出一定是p-1。这从缩系定义易得。模素数的缩系,元素个数就是该素数-1

6

模m的完系乘以一个与m互素的数a后,得到的集合仍然是完系。下面的代码尝试验证这个。

7

验证结果如图。令m=6,我们找到一个完系,乘以a,得到的集合模m始终等于{1,2,3..m-1}

8

对于模m的缩系有同样的性质。如果一个缩系乘以与m互素的数,得到的仍然是模m的缩系。

注意事项
1

最后介绍的这个缩系的性质,可用来证明欧拉定理。

2

Select[列表,真值判定函数] 可以从一个列表中选出符合条件的组成新列表。

推荐信息