数论基础及应用 1 数论 是研究数的性质的学 科是一门古老而充满现 代魅力的数学学科。数 论基本上可分为初等数 论、解析数论、代数数 论等几个较大的分支。 2 在古代，我国对数论的研究曾有 过辉煌的成就 ,如孙子定理（国 外文献一般称为中国剩余定理） 、商高定理 (勾股数 )、圆周率的 计算等等。在现代，我国一些著 名的数学家，如华罗庚、王元、 陈景润、潘承洞、丁夏畦等都在 数论领域做出了一些举世公认的 重要成果。 3 过去，人们把数论归类为纯粹数学， 但现在在许多领域，数论的原理和定 理都得到了广泛的应用。例如计算机 的计算模型、硬件体系结构和软件的 设计与实现、代数编码、计算机通信 安全与密码学等方面 , 都有着数论知 识的广泛应用。近年来发展起来的一 门新兴学科 “ 算法数论 ” 就是用计算 机算法来研究和深化数论的理论。一 个高层次的计算机专业人员，应该掌 握数论的一些基础知识 。 4 1欧几里德 转辗 相除法 利用 gcd(a,b)=gcd(b,a mod b)求 a， b的最 大公 约 数： Function gcd(a,b:longint):longint; begin
