最大公因数与最小公倍数
10/7/2018
20:28
定义3 最大公因数
设al ,a2 ,…, ak和d都是整数, k≥2. 若d|ai， 1≤i≤k, 则称d是al , a2 ,…, ak的公因数. 所有公因数中最大的那一个数，称为 al , a2 ,…, ak的最大公因数, 记为 (al , a2 ,…, ak). 由于每个非零整数的约数的个数是有限的，
10/7/2018
20:28
定理 11
(ⅰ) [a1 , a2]=[a2 , a1]=[-a1 , a2] . 一般地有, [a1 , a2 , , ai , , ak]= [ai , a2 , , a1 , , ak] = [-a1 , a2 , , ai ,, ak] (ⅱ) 若a2|a1 , 则[a1 , a2]=|a1|； (ⅲ) 对任意的d|a1
10/7/2018
20:28
定理5 设整数a≥2, 那么a一定可表为素数的乘积
(包括a本身是素数)，即 a=p1p2 ps其中pj（1≤j ≤s) 是素数. 证明 当a = 2时，结论显然成立。 假设对于2 ≤ a ≤ k，式(1)成立，我们来证明式(1) 对于a = k 1也成立，若k 1是素数，式(1)显成立.
(ⅱ) 若diA，即din，则
n n (ⅲ) 若di dj，则 d d . i j
10/7/2018 20:28
n di
| n，反之亦然；
定理3
(ⅰ) a>1是合数的充要条件是 a=de,1<d<a,1<e<a; (ⅱ)若d>1, q是不可约数且d|q, 则d=q.
定理4 若a是合数，则必有不可约数p|a.
10/7/2018
20:28
定理2 最小自然数原理 设T是N的一个非空子集. 那么，必有t0 ∈T, 使对任意的t ∈T有t0≤t，即t0是T中的最小 自然数.
10/7/2018
20:28
定理3 最大自然数原理 设M是N的非空子集.若M有上界，即存在 a∈N, 使对任意的m ∈M有m ≤ a, 那么必 有m0 ∈M，使对任意的m ∈M有m ≤ m0， 即m0是M中的最大自然数。
推论
任何大于1的合数a必有一个不超过a1/2的素 因数。 证明 由于 a是合数，故存在整数 b和 c使 a＝bc, 其中: 1<b<a, 1<c<a. 若b和c均大于 a1/2 , 则a＝bc＞a1/2· a1/2＝a, 这是不可能的. 因此b和c中必有一个小于或等于a1/2.
10/7/2018
20:28
所以最大公约数是存在的，并且是正整数。
显然，(a , 1) = 1，(a , 0) = |a|，(a , a) = |a|；
10/7/2018 20:28
定理8 下面的等式成立：
(ⅰ) （a1 , a2)=(a2 , a1)=(-a1 , a2) ；一般地 (a1 , a2 , , ai , , ak) = (ai , a2 , , a1 , , ak) = (-a1 , a2 , , ak)=(|a1| , |a2| , , |ak|)； (ⅱ) 若a1|aj , j = 2, , k,则（a1 , a2)=(a1 , a2, , ak) =(a1)=|a1| (ⅲ) 对任意整数x ，(a1 , a2)=(a1 , a2 , a1x) (a1 , , ak)=(a1 , , ak , a1x)； (ⅳ)对任意整数x ,（a1 , a2)=(a1 , a2+a1x) (a1 , a2 , a3 , , ak)=(a1 , a2+a1x , a3 , , ak) ； (ⅴ)若p是素数, 则(p , a) = 1或pa；一般地 （p , a1 , , ak)=1或pa .
10/7/2018 20:28
在例5中所使用的寻找素数的方法,称为 Eratosthenes筛法.它可以用来求出不超 过任何固定整数的所有素数.在理论上这 是可行的；但在实际应用中，这种列出 素数的方法需要大量的计算时间，是不
可取的.
10/7/2018
20:28
定理7. (Euclid) 素数有无穷多个.
所以有(a1, a2, , ak) = 1 . 证毕 .
10/7/2018
20:28
ห้องสมุดไป่ตู้
定理 10
设正整数m| (a1 , a2 , , ak) . 我们有 m (a1/m, a2/m, , ak/m) = (a1 , a2 ,, ak) 特别地有
ak a1 ( , , )=1. (a1 ,, ak ) (a1 ,, ak )
如果k 1是合数，则存在素数p与整数d，使得k 1
= pd.由于2 ≤ d ≤ k，由归纳假定知存在素数q1 , q2 , , ql，使得d = q1q2ql，从而k 1 = pq1q2ql . 从而由归纳法推出式(1)对任何大于1的整数a成立。 证毕。
10/7/2018 20:28
20:28
定理5 鸽巢原理 设n是一个自然数.现有n个盒子和n+1个物体. 无论怎样把这n+1个物体放入这n个盒子中， 一定有一个盒子中被放了两个或两个以上的 物体。
10/7/2018
20:28
§2 整除
10/7/2018
20:28
定义1
设a，b是整数，a 0，如果存在整数q， 使得b = aq，则称b可被a整除，记作ab ， 且称b是a的倍数，a是b的约数(因数、除数)； 如果不存在整数q使得b = aq成立，则称b不被
其中Z[x]表示全体一元整系数多项式组成的
集合. 若d|b-c, 则 d|f(b)-f(c).
10/7/2018
20:28
定义2
显然每个非零整数a都有约数 1，a，称 这四个数为a的显然因数，a的另外的因数 称为非显然因数。
若整数a 0，1，并且只有约数 1和 a， 则称a是素数（或质数）；否则称a为合数。
10/7/2018
20:28
例1 证明：若3|n且7|n，则21|n. 例2 设a=2t-1. 若a|2n, 则a|n.
例3 设a 、b是两个给定的非零整数，且有整数
x、 y，使得 ax+by=1. 证明：若a|n且b|n, 则ab|n.
例4 设f(x)=anxn+an-1xn-1++a1x+a0 ∈Z[x],
10/7/2018
20:28
定理4 第二数学归纳法 设 P(n) 是关于自然数 n 的一种性质或命题. 如果(ⅰ) 当 n=1 时， P(1) 成立； (ⅱ)设 n>1. 若对所有的自然数 m<n, P(m)成立， 则必可推出P(n)成立，那么, P(n) 对所有 自然数 n 成立.
10/7/2018
10/7/2018 20:28
初等数论
第一章 整除 §1 自然数与整数
10/7/2018
20:28
归纳原理 设S是N的一个子集，满足条件： (ⅰ)1∈S; (ⅱ)如果n ∈S，则n+1 ∈S, 那么，S=N.
10/7/2018
20:28
定理1 数学归纳法 设P(n)是关于自然数n的一种性质或命题.如果 (ⅰ)当n=1时，P(1)成立； (ⅱ)由P(n)成立必可推出P(n+1)成立， 那么， P(n)对所有自然数n成立.
10/7/2018 20:28
例5
10/7/2018
20:28
定义5 互素
如果(a1 , a2 ,, ak) = 1，则称a1 , a2 ,, ak是互 素的（或互质的）； 如果(ai , aj) = 1，1 ≤ i, j ≤ k，i j，则称a1 , a2 , , ak是两两互素的（或两两互质的）. 显然，a1 , a2 , , ak两两互素可以推出
证明：(反证法)假设素数是有限多个, 共有n个, 令它们是p1 , p2 ,…, pn, 并令a= p1p2…pn+1. 若 a 是素数, 则因a≠pi ，其中1<i<n, 故素数个数 最少是n+1个, 这与假设素数个数为n个矛盾. 若a 不是素数, 则由定理4知, a 的大于 1的最 小因数b是素数. 由于pi| p1p2…pn , 但 pi 不能整 除1, 故pi不能整除a, 因此 b≠pi , 其中1≤i≤n, 那么a也为素数. 所以在p1 , p2 ,…, pn ,还有素数, 这也与已知共有n个素数矛盾 . 20:28 10/7/2018
| b。 a整除，记为a
被2整除的数称为偶数，不被2整除的称为奇数
10/7/2018
20:28
定理1 下面的结论成立：
(ⅰ) a|b (-a)|b a|(-b) (-a)|(-b) |a|||b|； (ⅱ) ab，bc ac； (ⅲ) ab, ac 对任意 x、y , 有abx+cy ,一般地， abi，i = 1, 2, , k ab1x1 b2x2 bkxk， 此处xi（i = 1, 2, , k）是任意的整数； ( ⅳ ) a b acbc，c是任意的非零整数； (ⅴ ) a b且 b a a= b； (ⅵ) ab，b 0 |a| ≤|b|；ab且|b| < |a| b = 0.
数论的基本内容
按照研究方法的不同，数论可分为
初等数论 解析数论 代数数论 几何数论
10/7/2018
20:28
参考书目
1、南基洙主编《初等数论》； 2、柯召、孙琦编著《数论讲义》，高等教育 出版社； 3、闵嗣鹤、严士健编《初等数论》，高等教 育出版社；
4、郑克明主编《初等数论》，西南师范大学
出版社。
以后在本书中若无特别说明，素数总是指 正素数。
10/7/2018 20:28
定理2