初等数论第一章

a b
例1:设 x, y 为整数,且5 | x 9 y 则 5 | 8x 7 y
证:因为 8x 7 y
8( x 9 y) 65y
因为5 | x 9 y
所以有
又
5 | 65y
5 | 8x 7 y
例2:证明若3|n,7|n,则21|n
证:因为3|n,所以n= 3n1 又因为7|n,所以 7 | 3n1 显然有 7 | 7n 1 则有 7 | 7n1 2 3n1 即 7 | n1 有 n1 ห้องสมุดไป่ตู้7n2 即有 n 21n2 所以有21|n
注： （1）连续n个整数中必有一个数被n整除。 可作为一个定理，在证明整除问题时非常 有用。 （2）注意整数的各种表示。 例2: 证明若a不是5的倍数，则
与
中有且仅有一个数被5整除
证明: 这四个数有一个是5的倍数 若 5 | a 1或 又 所以 即 a 1, a 1 有且仅有一个数被5整除
n 是整数，所以 3

n2 2

n3 6
是
注:这里用了连续n个整数的乘积是n！的 倍数的结论.
注：连续n个整数的乘积是n！的倍数。 a、当n个整数都大于零时,由
m( m1)( m n1) n!
C
n m n1
而组合数为整数，可知连续n个整数的乘积是n！ 的倍数。 b、当n个整数中有一个为零时，显然成立。
n 注：1、
2、
a b (a b)M1
n
n
a b (a b)M 2 , 2†n
n
3、
(a b) aM3 b ,
n n
例5、试证明任意一个整数与它的各位数 字和的差必能被9整除。

例5 写出不超过100的所有的素数.
解 1 11 21 31 41 51 61 71 81 91 将不超过100的正整数排列如下： 2 3 4 5 6 7 8 9 10 12 13 14 15 16 17 18 19 20 22 23 24 25 26 27 28 29 30 32 33 34 35 36 37 38 39 40 42 43 44 45 46 47 48 49 50 52 53 54 55 56 57 58 59 60 62 63 64 65 66 67 68 69 70 72 73 74 75 76 77 78 79 80 82 83 84 85 86 87 88 89 90 92 93 94 95 96 97 98 99 100
数论的基本内容
按照研究方法的不同，数论可分为
初等数论 解析数论 代数数论 几何数论
参考书目
1、南基洙主编《初等数论》； 2、柯召、孙琦编著《数论讲义》，高等教育 出版社； 3、闵嗣鹤、严士健编《初等数论》，高等教 育出版社；
4、郑克明主编《初等数论》，西南师范大学
出版社。
初等数论
第一章 整除 §1 自然数与整数
按以下步骤进行：
(ⅰ) 删去1，剩下的后面的第一个数是2，2是素数； (ⅱ) 删去2后面的被2整除的数，剩下的2后面的第 一个数是3，3是素数； (ⅲ) 再删去3后面的被3整除的数，剩下的3后面的 第一个数是5，5是素数； (ⅳ) 再删去5后面的被5整除的数，剩下的5后面的 第一个数是7，7是素数； 照以上步骤可以依次得到素数2, 3, 5, 7, 11, . 由定理2推论可知，不超过100的合数必有一个不超 过10的素约数，因此在删去7后面被7整除的数以后， 就得到了不超过100的全部素数.

则11(n 1)2，因此，由定理4的推论1得到
11n 1，112(n 1)2。
再由式(3)得到
11211，
这是不可能的。所以式(3)不能成立。
第三节 最大公约数
注：这个例题的一般形式是： 设p是素数，a，b是整数，则
Pk b)k pk 1c， |(an
其中c是不被p整除的任意整数，k是任意的大于1
3，
于是b = a = 1，这是不可能的，所以式(6)不成
立。
第三节 最大公约数
(ⅲ) 若a > b，记a = kb r，0 r < b，此时
2kb1=(2b1)(2(k 1)b2(k 2)b1)=(2b 1)Q,
其中Q是整数。所以 2a 1 = 2kb + r 1 = 2r(2kb 1 1) 1 = 2r((2b 1)Q 1) 1 = (2b 1)Q (2r 1), 其中Q是整数。因此 2b 12a 1 2b 12r 1， 在(ⅰ)中已经证明这是不可能的,所以式(6)不能成
的整数。
第三节 最大公约数
例3 设a，b是整数，且
9a2 ab b2，
则3(a, b)。 证明 由式(4)得到 9(a b)2 3ab 3(a b)2 3ab
(4)
3(a b)2 3a b
9(a b)2。
(5)
第三节 最大公约数
再由式(4)得到 93ab 3ab。 3a或3b。
a1x1 a2x2 … akxk = 1。
证明 必要性 由定理2得到。
(1)
充分性 若式(1)成立，如果 (a1, a2, …, ak) = d > 1， 那么由dai（1 i k）推出da1x1 a2x2 … akxk = 1，这是不可能的。所以有(a1, a2, …,

第五节 辗转相除法
因此对于任意的自然数k，有 1 m(x kn) = n(km y)， 这样，当k充分大时，总可找出正整数x0，y0 ，使 得 1 mx0 = ny0 。 上式说明，如果放y0次（每次放n个），那么在使 m个盒子中各放x0个后，还多出一个硬币。把这 个硬币放入含硬币最少的盒子中（这是可以做 到的），就使它与含有最多硬币的盒子所含硬 币数量之差减少1。因此经过若干次放硬币后， 必可使所有盒子中的硬币数目相同。
求出整数x，y，使得
ax by = (a, b) 。
(4)
为此所需要的除法次数是O(log10b)。但是如果只
需要计算(a, b)而不需要求出使式(4)成立的整
数x与y，则所需要的除法次数还可更少一些。
第五节 辗转相除法
例1 设a和b是正整数，那么只使用被2除的除法
运算和减法运算就可以计算出(a, b)。
P0 =1，P1 =q1，Pk =qkPk 1 Pk 2，k 2，
Q0 =0，Q1 =1，Qk =qkQk 1 Qk 2，k 2，
则
aQk bPk = (1)k 1rk，k = 1, 2, , n . 证明 当k = 1时，式(3)成立。 当k = 2时，有 Q2 = q2Q1 Q0 = q2，P2 = q2P1 P0 = q2q1 1， (3)
Fk > k 2，k n，
则
第五节 辗转相除法
Fn + 1 = Fn Fn 1 > n 2 n 3 = n 3( 1) =
n 3 2 = n 1，
即当k = n 1时式(2)也成立。由归纳法知式(2)
对一切n 3成立。 证毕。