青岛大学数学科学院.docVIP

引言 初等数论是一门古老而又常新的学科，是典型的纯粹数学，也是日益得到广泛应用的新“应用数学”。它是以整数理论为基础，研究数的规律，特别是整数性质的数学分支。数论函数，也称算术函数是自变量是整数的函数，它们的取值通常是整数，但也可以是实数或复数。研究这些数论函数是初等数论这门学科的一个重要分支。许多数论和组合数学中的问题往往都可以归为数论函数，研究这些数论函数的性质是研究各种数论问题不可或缺的工具。 欧拉函数是一种基本的数论函数 第一章 相关知识介绍 1.1 欧拉函数的由来 在数论，对正整数n，欧拉函数是少于或等于n的数中与n互质的数的数目。此函数以其首名研究者欧拉命名，它又称为Eulers totient function、?函数、欧拉商数等。 用数轮的知识，不难得知，?(8)=4，因为1,3,5,7均和8互素. 1.2 欧拉函数的定义及证明 定义1.1 设n≥1，我们用φ?n?表示不大于n并且与n互素的正整数的个数，通常φ?n?就叫做欧拉函数. 欧拉函数的证明 设A, B, C是跟m, n, mn互质的数的集，据中国剩余定理，A*B和C可建立一一对应的关系。因此?(n)的值使用算术基本定理便知， 　　若 , 则 , 　　例如?(72)=?(23×32)=(2-1)2(3-1×(3-1)3(2-1)=24 . 欧拉函数与欧拉定理、费马小定理的关系 对任何两个互质的正整数a, m, m=2有 aφ(m)≡1(mod m) 即欧拉定理 . 　　当m是质数p时，此式则为： a(p-1)≡1(mod m) 即费马小定理. 1.3 欧拉函数的相关定理及性质 定理1.1 如果n≥1，我们有 证明 设集合S={1,2,3，…，n}，我们把S中的整数分为下面的一些互不相交的集合，对于n的每一个约数d，令 A(d)={k：（k，n）=d，1≤k≤n}， 于是，A（d）包含了S中与n的最大公约数为d的那些元素，这些集合A（d）互不相交且它们的并集就是S。因此，如果?(d)表示A（d）中整数的个数，我们就有 （1.1） 但是（k，n）-d，当且仅当(k/d,n/d)-1，而当0≤k≤n时，0≤k/d≤n/d.因此，如果我们令q=k/n，则在A(d)中的元素与满足0?q≤n/d,(q,n/d)=1的整数之间有一个一一对应的关系。这样的q的个数就是φ?n/d?,于是?(d)=φ?n/d?,则有,而当d取遍n的所有约数时，n/d也取遍n的所有约数，即,这就完成了定理1.1的证明. 定理1.2 如果n1,我们有 （1.2） 证明 设p1，p2，p3，…，pr是n的不同约数，乘积可写为 （1.3） 注意到（1.3）式的右端每一项都是±1/d的形式，这里d是n的约数，它为1或者为不同的素数的乘积，分子±1恰好就是u?d?，这是因为如果d能被任意素数p （i=1,2,3，…，r） 的平方整除，则u?d?=0。这时，（1.3）式中的和恰好是 ，从而我们证明了定理1.2. 定理1.3 欧拉函数的性质： 性质1 对于素数p与a≥1，有. 性质2 ,这里d=（m，n）.特别地，如果（m，n）=1，则. 性质3 如果a/b，则. 性质4 如果n≥3，则φ（n）为偶数，并且如果n有r个不同的奇素因子，则. 证明 第二章 欧拉函数的相关计算及编程实现 2.1 欧拉函数的求和公式 2.2初等渐进公式 2.3 欧拉函数的编程实现 利用欧拉函数和它本身不同质因数的关系，用筛法计算出某个范围内所有数的欧拉函数值。 　　欧拉函数和它本身不同质因数的关系：欧拉函数ψ（Ｎ）＝Ｎ｛∏ｐ｜Ｎ｝（１－１/ｐ）。（Ｐ是数Ｎ的质因数） 　　 第三章 欧拉函数在实际当中的应用 3.1 在离散数学中求循环群的生成元 3.2 在计算机网络安全中的应用 3.3 在渗流力学中的应用 3.4 基于欧拉函数的一种筛选方法 注意的一些问题： 1 设计的终稿的格式是有要求的，问一下同学，搞清楚排版的格式，必须按照要求排版； 2 设计中的数学符号一律使用公式编辑器； 3 设计的基本框架可以，中间的措辞还需斟酌； 4 行文的语言尽量严谨，摘抄教科书上的叙述是一个保持语言严谨的好办法，尽量避免用自己的话表达； 5 附上一篇别人的论文，行文的风格可以以此为例； 6 抓紧时间完成设计。