初等数论/整数的基本性质

维基教科书,自由的教学读本

数论 > 初等数论 > 初等数论/整数的基本性质


数论是奠基于算术之上的,所以在学习数论之前,要先知道以下关于整数的性质:

整数集合[编辑]

整数集合,即所有的整数,像0,1,-1,2,-2,......这一些整数形成的集合,就叫整数集合,或以表示,自然数为其子集,但奇怪的是,整数集合和正整数集合内部的元素数量竟相等


整数集合的性质符合环的性质,意即其加减乘法皆自封(若对一种定义在X上的运算Y,当a和b皆为X的元素时,aYb亦为X的元素,则称运算Y自封),以下将说明整数集合的性质

数学归纳法[编辑]

若有一个命题,若能证明或其他给定的起始正整数成立,且在假设对一个正整数(或前面给定的正整数),命题成立时,亦能证明时命题成立,则命题对所有皆成立,除了本法以外,尚有第二种数学归纳法,第二种数学归纳法将在稍后说明

加法篇[编辑]

加法使用符号+,,或称相加可记为

整数集合的加法(和减法)是封闭的(若里面的元素透过一个定义在上的运算,所得的结果的元素依然存在于,且对所有的元素都是如此,那么这个二元运算就是在上封闭的),以下为加法(和减法)的性质:

  • 加法有结合律,即对于任意整数,,
  • 加法有交换律,即对于任意整数,
  • 加法有相消律,即对于任意整数,,,若,则可推出
  • 减法,若对整数,,c有,则亦可记做,但是减法无交换律
  • 在整数中有一个元素0,使得对任意整数

乘法篇[编辑]

乘法使用符号‧,,或称相乘可记为,但是若至少有一个为未知数,则乘号‧可省略(但若皆为已知数,且皆以数字(非英文字母)表示,则乘号“‧”不可省略

整数集合的乘法也是封闭的,以下为它的性质:

  • 乘法有结合律,即对于任意整数,,
  • 乘法有交换律,即对于任意整数,
  • 乘法有相消律,即对于任意整数,,,若,则可推出 (a不能为零)
  • 在整数中有一元素1,使得对任意整数
  • 任意整数和0相乘为0

大小关系[编辑]

整数集合是一个有序集合,以下为整数中的序的关系(即一般所说的大小关系)

  • ,则必有正整数,使
  • ,且,则
  • ,且,为正整数,则必有正整数,使得
  • ,则
  • 对于任意整数,有
  • 对于两个整数有且仅有一个成立

最大自然数原理与最小自然数原理[编辑]

  • 最小自然数原理:对于任意自然数的非空子集,存在一元素,使得任意的,都有

事实上,对于任意有下界的非空集合,若为整数集合Z的一个子集,则在中必存在一最小的数n,使得任意的,都有

  • 最大自然数原理:对于任意有上界的非空子集,存在一元素,使得任意的,都有


除法篇[编辑]

除法使用符号,若除以,或,记做

  • 可被整除,则记做,或
  • 若不能整除,即会剩余某数,则记做
  • 不能整除,但是能找得到一数,使,则此,,可记做(),后者亦可称除以同余于

其他的一些名词的定义[编辑]

  • 因数:若成立,则的因数
  • 倍数:若,则的倍数
  • 质数:若一个大于1的正数的正因数只有1,,则称这个数为质数

第二种数学归纳法[编辑]

虽然比起前面所说的数学归纳法,第二种数学归纳法比较少用,但是第二种数学归纳法仍然为重要的证明方法,兹将之说明如下: 若对一个命题,在(或指定的正整数)时成立,在假设对所有符合的正整数都成立时,能证明亦成立,则对所有正整数(或正整数集合)都成立

第二种数学归纳法可以用最小自然数原理和反证法证明其为真

算术基本定理[编辑]

任意大于1的正整数都能唯一地表示成由指定数量的特定质数的乘积

标准分解式[编辑]

根据算术基本定理,任意正整数皆可表为唯一的若干个正质数的乘积,且因为这些质数没有次序上的问题,因此,可将相同的质数写成该质数的幂方也是没问题的,意即上面的a可改写为: a=

算术基本定理的证明[编辑]

先证明几个引理:

  • 引理1:每个大于一的数都可以表示成质数的乘积,或本身为质数

引理1证明:用第二种数学归纳来证明,设正整数时,2为质数,故成立,再假设当时此引理成立,则当时,若为质数,则引理成立,若不为质数时,为合数,因此,其中,因而由假设知可表为质数的乘积,因而亦可表为质数的乘积,因此引理亦对成立,因此由数学归纳法得知,此引理对所有的正整数成立

  • 引理2:若,且是质数,则p|a或p|b至少有一个成立,另一方面,若是质数,且若成立,则、......至少有一成立

引理2证明:

  • 由引理2引出的引理3:若皆为质数,且则至少有一个使

引理3证明:

算术基本定理证明:存在性由引理1可得知,现在来证唯一性:设有一数n,它的分解式为,其中皆为质数,再设n存在另一个分解式,设,且亦皆为质数,而且,则很明显地有,由引理3知,必有一些相等,且可推知这个关系是唯一的,因此现在将和相等的数设为,其他的也照做,意即、‧‧‧、,而剩下来的则记为,则由此及可推出意即此两个分解式之中所有的质数相等,与原假设矛盾,故n的分解式为唯一的

最大公因数与最小公倍数[编辑]

最大公因数[编辑]

假若对两个整数,有一整数,使,则称公因数,若在的公因数所形成的集合中,是为其中最大的数字,则称这个最大公因数,或记做,若,则称互质

最小公倍数[编辑]

若有整数,使得,则称公倍数,若在所有的正公倍数所形成的集合中,是其中最小的数字,则称最小公倍数,或记做,且若,则


最大公因数和最小公倍数的性质[编辑]

  • 最大公因数:
    • ,且在此为任意整数,为任意正整数
    • ,且在此为任意整数,为任意正整数

辗转相除法[编辑]

对于两个数,有以下算法:

我们可以表示的公约数则并且
所以并且
也就是说当时,的最大公约数和相等。于是我们有:

......

其中(,)=(,)=......=(,)

习题[编辑]

第一部分─基础题[编辑]

第二部分─进阶题[编辑]