数论是一门研究整数的学科。
我们来对初等数论作一个简单的入门。
我们先来介绍整除。
定义1 如果存在整数c使得 a=bc，那么我们称b整除a,记作b|a。我们把b叫做a的因数，a叫做b的倍数。
引理1 整除具有如下性质：
1.(反身性) a|a
证：a=1*a，故a|a。
2.(传递性) 如果a|b,b|c,那么a|c
证：由定义，设b=am，c=bn，则c=(mn)a。故c|a
3.(反对称性) 若a|b，b|a,那么a=b
证：设b=am，a=bn=amn显然mn=1即m=n=1，a=b
4.(线性性)如果a|b,a|c，则a|mb+nc
证：设b=ak，c=al，那么mb+nc=(mk+nl)a。故a|mb+nc
5.ab|c，则a|c，b|c
证：设c=(ma)b=(mb)a，故a|c,b|c。
6.若a|b，则a|bc
证：b=am，bc=(mc)a，故a|bc
定义2 一个正整数p>1，如果它除了1和p以外，没有别的因数，我们就称这个p叫做素数。否则这个p>1称为合数。
例1 2,3,5,7,11,13都是素数。4,6,8,9,10,12,14,15都是合数。1既不是素数也不是合数。
定义3 如果对于a，b，存在一个d,使得d|a,d|b,我们就称d是a与b的公因数。如果这个d是所有公因数中最大的，我们就称这个d叫做a与b的最大公因数，记作(a,b)。
定义4 如果(a,b)=1，那么我们称a与b互质（互素）。或者称a与b既约。
例2 (3,15)=3,(7,3)=1,即7与3互质，而3与15不互质。
例3 若(a,b)=1,c|a,d|b,那么(c,d)=1 证:如果不是，设(c,d)=D>1.那么 D|c,c|a故D|a,D|d,d|b故D|b,故D为a,b的公因数但不一定是最大公因数，那么(a,b)≥D>1，而这与(a,b)=1矛盾。所以(c,d)=1。
这说明了互质的数的约数也是互质的。
引理2 任何一个自然数n>1，一定可以写成素数的乘积。(单独一个素数也视为素数的乘积。)
证：如果命题是错的，设最小的使命题不成立的n>1为N，那么N一定不是素数，因此N是合数，我们设N=kl,其中N>k>1,N>l>1，由于N是使命题不成立的最小数，那么k和l一定能写成素数之积，这是一个矛盾。
定理1（算术基本定理）：如果不计素因数的顺序，那么引理2中的素因数分解式是唯一的。
这个定理并不像它看起来那么容易证明，我们必须先证明一些其他引理。
欲知后事如何，请听下回分解。
-----------------------------------------------
上一节里我们向大家介绍了整除性与素数，这里我们将利用整除，建立更多的基本理论，来更深入地探讨初等数论。本节的主题是：最大公因数理论、带余数除法、算术基本定理。
符号声明：本文中如未声明，字母总表示整数。p总表示素数。由于在这里打字不能打出公式，我们约定p1,p2,p3…,pk以及q1,q2……总表示编了号的数字，而不是p乘以什么。p乘以k我们总写成kp而不是pk。
证明算术基本定理的关键步骤在于下面这两个引理：
引理3 如果素数p|ab，那么p|a或p|b至少有一个成立。
有时候这被称为算术基本引理。但我们之前建立的理论还不足以直接证明它。
引理4 (带余数除法) 对于任意的整数a和b≠0，存在唯一的整数q,r使得 a = bq + r。其中0≤r＜b。这里r叫做最小非负剩余。
证：
考虑形如a-xb的所有非负整数，其中x为整数。在这些非负整数中，我们把最小的记为r。我们一定有r<b。否则，r≥b，那么r-b也是形如a-xb的非负整数，这与r的最小性矛盾。因此我们有a-xb=r，(0≤r＜b)，即a=bx+r,(0≤r＜b)
为了进一步说明整除的一些深刻性质，我们暂时引进一个新记号，记所有形如ax+by的整数集合为T。(a和b不同时为0。x,y是整数)
引理5 对任意c,d∈T，我们有mc+nd∈T。其中m,n都是整数。
证：由T的定义，设c=ax+by,d=aX+bY,那么mc+nd=(mx+nX)a+(my+nY)b，其中mx+nX，my+nY都是整数。
引理6 存在这样一个正整数d∈T，对任意的n∈T都有d|n。
证：考虑Q中的最小正整数d，我们来证明Q中所有元素都被d整除。否则，存在这样一个s∈T，且d不整除s。根据引理4，一定存在唯一的q,r使s=dq+r,0＜r＜d。根据引理5，r=s-dq∈T，这与d是T中的最小正整数矛盾。
引理7 T中的最小正整数d=(a,b)
证：由于a,b∈T，根据引理6我们有d|a，d|b。这说明d是a,b的公因数但不一定是最大的。我们有d≤(a,b)。
设d=ax+by,我们有(a,b)|a，(a,b)|b，故(a,b)|ax+by=d，这说明了(a,b)≤d。所以d=(a,b)
引理8 如果s|a,s|b那么s|(a,b)。即公因数一定是最大公因数的因数。
证：由引理7知可设(a,b)=ax+by，那么s|a,s|b可得s|ax+by=(a,b)。
引理9 如果(a,b)=1，且a|bc那么a|c。
证：设ax+by=1，那么acx+bcy=c，由于a|acx，a|bcy故a|c
引理3的证明
证：设p|ab，且p不整除b，设(p,b)=d，我们来证明d=1。否则设d>1,d|p,因为p是素数,d=p。由于d|b得p|b。矛盾。故(p,b)=1，
由引理9得p|a。
引理10 设p|abcd…，那么p|a，p|b,…至少有一个成立。
证：这可由引理3立刻推得。
现在我们已经有足够的能力证明：
定理1（算术基本定理）：如果不计素因数的顺序，那么自然数n>1的素因数分解式是唯一的。
证：设n=p1 p2 p3 … pm （这里pm表示某个素因数，不是p乘以m）
n=q1 q2 q3 … qk 是n的两个素因数分解式。我们来证明：k=l，而且这两种分解式其实是相同的。
由于p1 p2 p3 … pm = q1 q2 q3 … qk
显然p1|q1 q2 q3 … qk，由引理10得p1一定整除右边那些素数中的某一个。由于右边的都是素数，所以在右边一定存在某一个素数与p1相等。不妨设这个素数是q1，那么约去它们，得到：
p2 p3 … pm = q2 q3 … qk
用相同的办法，约来约去，最后某一边只剩下数字1，不妨设m≥k,那么左边只剩下1。
1 = q(m+1) q(m+2) … qk （这里q(m+1),q(m+2),qk都表示某个素因数，不是q乘以(m+1)。）
而右边的都是素数，素数必须大于1，所以只有一种可能性：k=m。上式成为：1=1
由于我们在约去时，每次两边都约去了相同的素数，故每个素因数在两边出现的次数都是相同的。因此，自然数n>1素因数分解式是唯一的。
通过收集相同的素数，我们有n=p1^a1 * p2^a2 * … * pk^ak ，且p1<p2<…<pk，这个式子叫做n的标准分解式。
最主要的定理我们已经证明完成，接下来我们将向大家介绍最大公因数理论的一些更有趣的部分。
定义4 如果a|L,b|L,我们就称L是a,b的公倍数。如果这个L是最小的，而且L>0，我们就称L是a,b的最小公倍数，记作[a,b]
引理11 我们有(ma,mb)=m(a,b)
证：设D=(ma,mb),d=(a,b)=ax+by，那么md=max+mby,D|ma,D|mb得D|md。d|a,d|b得md|ma,md|mb,故md|D。因此D=md。
引理12 (a,b)=1，那么(c,ab)=(c,a)(c,b)
证明在最下面。
引理13 我们有(a,b)[a,b]=ab
证法一：设ord(p,n)表示p^k|n但p^(k+1)不整除n中的k。例如ord(2,12)=2，ord(2,7)=0。
我们用min{i,j}表示i,j中的最小值。max{i,j}意义与此相反。
那么我们显然有ord(p,ab)=ord(p,a)+ord(p,b),
ord(p,(a,b))=min{ord(p,a),ord(p,b)}，ord(p,[a,b])=max{ord(p,a),ord(p,b)}
那么我们只要证明min{i,j}+max{i,j}=i+j即可。但这是显然的，无需证明。
证法二：……由你来补充。
引理14 如果(a,b)=1，a|c,b|c,则ab|c.
证明在最下面。
时间不够，暂时先写到这里吧。
给你来点练习题：
1.给出证明引理13的另一种方法。
2.若(a,b)=1，则(a+b,a-b) = 1 或 2.
3.若(a,b)=1，d|(a+b)，则(a,d)=(b,d)=1.
4.请证明引理12.
5.请证明引理14.
做出来了把证法回复给我，我帮你批改作业。
下一课：http://www.51hei.com/bbs/dpj-52251-1.html
|
QQ好友和群
QQ空间
腾讯微博
腾讯朋友
收藏
淘帖
顶
踩
