摘  要: 本文主要介绍C语言在初等数论中的应用,如求解最大公因数、Euler函数的计算、剩余定理等.结合初等数论的相关理论,分析解决问题的算法,利用C语言编程降低问题解决的难度,从而更快捷、更方便、更有效地处理数学问题.63115

毕业论文关键词: C语言,最大公因数,Euler函数,剩余定理

Abstract: This paper mainly introduces the application of C language in elementary number theory, such as solving the greatest common factor, Euler function calculation and remainder theorem, etc. Based on the relevant theory of elementary number theory, analysis of the algorithm to solve the problem, the use of C language programming to reduce the difficulty of problem solving, thus faster and more convenient, more effectively deal with math problems. 

Keywords: C language, the greatest common factor, Euler function, remainder theorem 

目  录

0 引言 …4

1 C语言简介…4

2 C语言在初等数论中的应用4

2.1求解最大公因数5

2.2 计算Euler函数…8

2.3 剩余定理…11

结论14

参考文献15

致谢16 

0 引言

数论是研究整数性质的一门很古老的数学分支,按照研究方法来说,可以分为初等数论、解析数论、代数数论与几何数论四个部分. 初等数论是以整数的整除性为中心的,包括整除性、不定方程、同余式、连分数、素数分布以及数论函数等内容,统称初等数论.初等数论以算术方法为主要研究方法,主要内容有整除理论,同余理论,连分理论和某些特殊不定方程;初等数论是用朴素的方法去研究数论.

由于信息时代的影响,C语言与初等数论的关系越来越密切.c语言可以通过自身的编程语言简化复杂的数学计算过程,使得数学问题更加容易的解决.其中C语言在初等数论中的应用就是一个很好的证明.本文只是通过论证初等数论中的几个重要理论,介绍C语言在初等数论中的应用,对给出的初等数论中的具体问题,用相关的C语言编程运行出来.同时介绍C语言对最大公因数,Euler函数,剩余定理进行求解.因此,研究C语言在初等数论中的应用有着非常重要的实际意义.

1 C语言简介

C语言是国际上广泛流传的计算机高级语言.C语言的祖先是BCPL语言.1967年英国剑桥大学的Martin Richards推出了没有类型的BCPL语言.1970年美国AT&T贝尔实验室的Ken Thompson以BCPL语言为基础,设计出了简单很接近硬件的B语言.但B语言过于简单,功能有限.最后,美国科学家D.M Ritchie在B语言的基础上设计出了C语言[1].

C语言的新特点主要表现在具有多种数据类型（如字符、数值、数组、结构体和指针等）,开发C语言的目的在于尽可能降低用它所写的软件对硬件平台的依赖程度,使之具有可移植性.C语言是一种用途广泛、功能强大、使用灵活的过程性编程语言,既可以用于编写应用软件,又能用于编写系统软件.

C语言的主要特点主要有语言简洁、紧凑使用方便、灵活,运算符丰富,数据类型丰富,具有结构化的控制语句（如if…else语句、while语句、do…while语句、switch语句和for语句）,语法限制不太严格,程序设计自由度大,C语言允许直接访问物理地址,能进行位（bit）操作,能实现汇编语言的大部分功能,可以直接对硬件进行操作,编写的程序可移植性好和 生成目标代码质量高,程序执行率高.

2 C语言在初等数论中的应用

2.1 求解最大公因数

所谓最大公因数,也称最大公约数或公因子,指两个或多个整数共有约数中最大的一个[2].

如果数a能被数b整除,a就叫做b的倍数,b就叫做a的约数.严格来说,对两个正整数a,b如果能在区间[0,a]或[0,b]内能找到一个整数Y能同时被a和b所整除,则Y即为最大公因数.整除理论是初等数论的基础,而最大公约数理论是整除理论的核心内容,其中求自然数的最大公因数是一个很实际的问题.辗转相除法是求最大公因数的最简单最有效的方法.