初等数论

序言

数论是研究整数性质的一门很古老的数学分支, 其初等部分是以整数的整除性为中心的,包括整除性、不定方程、同余式、连分数、素数(即整数)分布 以及数论函数等内容,统称初等数论(Elementary Number Theory)。

初等数论的大部份内容早在古希腊欧几里德的《 几何原本》中就已出现。欧几里得证明了素数有无穷多个,他还给出求两个自然数的最大公约数的方法, 即所谓欧几里得算法。我国古代在数论方面亦有杰出之贡献,现在一般数论书中的“中国剩余定理”正是我国古代《孙子算经》中的下卷第26题,我国称之为“孙子定理”。

近代初等数论的发展得益于费马、欧拉、拉格朗日、勒让德和高斯等人的工作。1801年,高斯的《算术探究》是数论的划时代杰作。 “数学是科学之王,数论是数学之王”。 -----高斯

由于自20世纪以来引进了抽象数学和高等分析的巧妙工具,数论得到进一步的发展,从而开阔了新的研究领域,出现了代数数论、解析数论、几何数论等 新分支。而且近年来初等数论在计算器科学、组合数学、密码学、代数编码、计算方法等领域内更得到了 广泛的应用,无疑同时间促进着数论的发展。 数论是以严格和简洁著称,内容既丰富又深刻。我将会介绍数论中最基本的概念和理论,希望大家能对这门学问产生兴趣,并且对中小学时代学习过的一些基本概念,例如整除性、最大公因子、最小公倍数、辗转相除法等,有较深入的了解。

第一章 整数的整除性

§1.1整除的概念

一、基本概念

1、自然数、整数 2、正整数、负整数 3、奇数、偶数 一个性质:

整数+整数=整数 整数-整数=整数 整数*整数=整数

二、整除

1、定义:设a,b是整数,b≠0。如果存在一个整数q使得等式: a=bq

成立,则称b能整除a或a能被b整除,记作 b∣a;如果这样的q不存在,则称b不能整除a。

2、整除的性质

(1)如果b∣a, c∣b,则c∣a. (2)如果b∣a,则cb∣ca.

(3)如果c∣a,则对任何整数d, c∣da.

(4)如果c∣a, c∣b,则对任意整数m,n,有 c∣ma+nb.

(5)如果a∣b, b∣a,则a=±b.

3、质数、合数

质数(素数)是指在大于1的自然数中,除了1和它本身外,不能被其他自然数整除(除0以外)

的数称之为素数(质数)。 合数 :比1大但不是素数的数称为合数,1和0既非素数也非合数。 质因数 :质因数(素因数或质因子)在数论里是指能整除给定正整数的质数。每个合数都可以写成几个质数(也可称为素数)相乘的形式,这几个质数就都叫做这个合数的质因数。如果一个质数是某个数的因数,那么就说这个质数是这个数的质因数。而这个因数一定是一个质数。 分解质因数 :任何一个合数都可以写成几个质数相乘的形式。其中每个质数都是这个合数的因数,叫做这个合数的分解质因数。分解质因数只针对合数。 算术基本定理: 任何一个大于1的自然数N,都可以唯一分解成有限个质数的乘积 , 这里P1

定理:

设a,b是两个整数,其中b>0,则存在两个唯一的整数q及r,使得 a=bq+r,0?r<b

成立.我们称r是b除a的余数。

可以看出:b整除a的充要条件是r=0。

§1.2最大公因数和辗转相除法

一、最大公因数 1、定义

设a1,a2,?,an是n个不全为零的整数,若整数d是它们之中每一个的因数,那么d就叫做a1,a2,?,an的一个公因数。整数的公因数中最大的一个叫做它们的最大公因数,记作(a1,a2,?,an) 。 2、互质

设a1,a2,?,an是n个不全为零的整数,若 (a1,a2,?,an) =1, 则称a1,a2,?,an 是互质的。 注:三个互质比一定两两互质。

比如(3,4,6)=1,但(3,6)=3,(4,6)=2. 3、最大公因数的性质

(1)当b∣a时,(a,b)=b.

(2)a,b的一切公因数都是(a,b)的因数. (3)若a,b是正整数,m是任一正整数,则有 (am,bm)=(a,b)m.

(4)若(a,b)=1,c为任一正整数,则有 (ac,b)=(c,b) (5)若(a,b)=1, b∣ac,则有b∣c.

(ab,)?1dd (6)若a,b,c是任意三个正整数,则(a,b)=d的充分必要条件是:4、辗转相除法

1、定理: 设a,b是任意两个正整数,且a>b,且有 a?bq?r, 0<r<b, 其中q,r都是正整数,则有 (a,b)?(b,r)

2、辗转相除法 定理: 若a,b是任意两个正整数,且a>b,由带余除法,有下列等式 a?bq?r, 0<r<b, b?rq1?r1, 0<r1<r, r?r1q2?r2, 0<r2<r1, … … rn?2?rn?1qn?rn, 0<rn<rn?1, rn?1?rnqn?1?rn?1, rn?1?0, 则有(a,b)?rn.

一个推论

若a,b是正整数,且(a,b)=d,则必存在整数m和n,使得 d=ma+nb

注:证明可由带余除法逆向代入证得。

联系客服:779662525#qq.com(#替换为@) 苏ICP备20003344号-4